Ce travail présente un état de l'art sur les problèmes d'ordonnancement multicritères et introduit une nouvelle définition de ces problèmes. Nous proposons également une démarche, conforme aux principes de l'aide multicritère à la décision, pour aborder les problèmes d'ordonnancement multicritères. Ces problèmes sont décomposés en trois sous-problèmes. Le premier concerne la modélisation du problème d'ordonnancement considéré. La résolution du second sous-problème conduit à répondre à des questions : comment prendre en compte les critères pour calculer des optima de Pareto ? Quel type d'algorithme faut-il mettre au point ? Le troisième sous-problème concerne la résolution du problème d'ordonnancement qui découle des deux sous-problèmes précédent. Nous proposons également dans ce travail une extension de la notation classique des problèmes d'ordonnancement au cas multicritère. Nous présentons ensuite les résultats de base de l'optimisation multicritère avant de détailler notre état de l'art sur les problèmes d'ordonnancement multicritères à une machine, à machines parallèles et de type flowshop.
This paper presents a state-of-the-art survey on multicriteria scheduling and introduces a definition of a multicriteria scheduling problem. It provides a framework that allows to tackle multicriteria scheduling problems, according to Decision Aid concepts. This problem is decomposed into three different problems. The first problem is about obtaining a model. The second one is how to take criteria into account and the third one is about solving a scheduling problem. An extension to an existing notation for scheduling problems is proposed for multicriteria scheduling problems. Then, basic results from the literature on multicriteria optimization are presented. These results are used to build the final scheduling problem to solve. Finally a survey is presented for one-machine, parallel machines and flowshop multicriteria scheduling problems.
@article{RO_2001__35_2_143_0,
author = {T'kindt, V. and Billaut, J.-C.},
title = {Multicriteria scheduling problems : a survey},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {143--163},
publisher = {EDP-Sciences},
volume = {35},
number = {2},
year = {2001},
zbl = {1014.90046},
language = {en},
url = {http://www.numdam.org/item/RO_2001__35_2_143_0/}
}
T'kindt, V.; Billaut, J.-C. Multicriteria scheduling problems : a survey. RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 2, pp. 143-163. http://www.numdam.org/item/RO_2001__35_2_143_0/
[1] and, Scheduling jobs with different job-dependent earliness and tardiness penalties using the SLK method. Eur. J. Oper. Res. 88 (1996) 336-344. | Zbl 0913.90154
[2] and, Minimizing the weighted sum of late and early completion penalties in a single machine. IEEE Trans. 22 (1990) 288-290.
[3] , and, An approach to solve bicriterion flow-shop scheduling problems, in Proc. of the 6th International Workshop on Project Management and Scheduling (PMS'98). Istanbul, Turkey (1998) 151-154.
[4] and, Two parallel machine sequencing problems involving controllable job processing times. Eur. J. Oper. Res. 70 (1993) 335-341. | Zbl 0791.90028
[5] , and, Bicriteria scheduling: Minimizing flowtime and maximum earliness on a single machine, edited by J. Climaco, Multicriteria Analysis. Springer-Verlag (1997) 279-288. | Zbl 0899.90110
[6] and, Scheduling job families about an unrestricted common due date on a single machine. Internat. J. Production Res. 35 (1997) 1321-1330. | Zbl 0942.90547
[7] , and, Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date. Naval Res. Logist. 34 (1987) 739-751. | MR 906433 | Zbl 0657.90052
[8] , and, Minimizing mean absolute deviation of completion times about a common due date. Naval Res. Logist. Quarterly 33 (1986) 227-240. | MR 841721 | Zbl 0599.90049
[9] , and, Minimizing mean squared deviation of completion times about a common due date. Management Sci. 33 (1987) 894-906. | MR 902724 | Zbl 0636.90049
[10] , Single machine scheduling to minimize weighted sum of completion times with secondary criterion - a branch and bound approach. Eur. J. Oper. Res. 5 (1980) 177-181. | Zbl 0445.90032
[11] and, Scheduling jobs with linear delay penalties and sequence dependent setup costs. Oper. Res. 29 (1981) 146-160. | MR 606863 | Zbl 0454.90037
[12] , and, Determination of an optimal common due date and optimal sequence in a single machine job shop. Internat. J. Production Res. 26 (1988) 613-628. | Zbl 0644.90047
[13] ,, and, Three exact methods and an efficient heuristic for solving a bicriteria flowshop scheduling problem, in Multiconference on Computational Engineering in Systems Applications (CESA 98), Symposium on Industrial and Manufacturing Systems, IEEE-SMC/IMACS. Nabeul-Hammamet, Tunisia (1998) 371-377.
[14] ,,, and, Scheduling computer and manufacturing processes. Springer-Verlag (1996). | Zbl 0911.90201
[15] ,, and, Problème industriel d'ordonnancement bicritère sur machine unique : modélisation et aide à la décision. APII 29 (1995) 331-341.
[16] , On the relationship of the tchebycheff norm and the efficient frontier of multiple-criteria objectives, edited by H. Thiriez and S. Zionts, Multiple Criteria Decision Making. Springer-Verlag (1976) 76-85. | Zbl 0364.90089
[17] , Scheduling to minimize the weighted sum of completion times with secondary criteria. Naval Res. Logist. Quarterly 23 (1976) 125-129. | MR 406461 | Zbl 0335.90029
[18] and, Single machine scheduling to minimize weighted completion time with maximum allowable tardiness, Research report. University of Purdue (1984).
[19] and, A note on the single machine scheduling problem with minimum weighted completion time and maximum allowable tardiness. Naval Res. Logist. Quarterly 33 (1986) 551-557. | MR 850659 | Zbl 0601.90079
[20] and, Single machine scheduling to minimize weighted earliness subject to no tardy jobs. Eur. J. Oper. Res. 34 (1988) 221-230. | MR 935237 | Zbl 0648.90036
[21] and, Scheduling unit processing time jobs on a single machine with multiple criteria. Comput. Oper. Res. 17 (1990) 1-7. | MR 1022760 | Zbl 0681.90049
[22] and, Complexity of single machine, multi-criteria scheduling problems. Eur. J. Oper. Res. 70 (1993) 115-125. | Zbl 0795.90032
[23] and, Complexity of multiple machines, multi-criteria scheduling problems, in 3rd Industrial Engineering Research Conference (IERC'94). Atlanta, USA (1994) 662-665.
[24] , Scheduling and common due date assignment with earliness and tardiness penalties and batch delivery costs. Eur. J. Oper. Res. 93 (1996) 49-60. | Zbl 0916.90147
[25] and, Parallel-machine scheduling problems with earliness and tardiness penalties. J. Oper. Res. Soc. 45 (1994) 685-695. | Zbl 0829.90077
[26] and, Multiobjective flow-shop scheduling. Naval Res. Logist. 37 (1990) 981-995. | Zbl 0825.90551
[27] and, Bicriterion static scheduling research for a single machine. Omega 16 (1998) 53-59.
[28] and, Bicriterion jobshop scheduling with total flowtime and sum of squared lateness. Engrg. Costs and Production Economics 21 (1991) 295-299.
[29] , Multiple Criteria Optimization: Classification and Methodology, Ph.D. Thesis. University of Kaiserslautern, Germany, in English (1997).
[30] , A note on a scheduling problem with dual criteria. Naval Res. Logist. Quarterly 22 (1975) 615-616. | MR 436993 | Zbl 0314.90045
[31] , One machine sequencing to minimize mean flow time with minimum number tardy. Naval Res. Logist. Quarterly 22 (1975) 585-592. | MR 403625 | Zbl 0315.90032
[32] , Scheduling to a common due date on parallel uniform processors. Naval Res. Logist. 34 (1987) 803-810. | MR 913466 | Zbl 0648.90043
[33] , An overview of techniques for solving multiobjective mathematical programs. Management Sci. 30 (1984) 1268-1282. | MR 774745 | Zbl 0551.90090
[34] , and, Minimizing weighted absolute deviation in single machine scheduling. IEEE Trans. 19 (1987) 445-450.
[35] , and, A framework for single machine multiple objective sequencing research. Omega 17 (1989) 595-607.
[36] and, Planning for idle time: A rationale for underutilization of capacity. Int. J. Prod. Res. 26 (1988) 1853-1859.
[37] and, Bi-criterion single-machine scheduling with forbidden early shipments. Engrg. Costs and Production Sci. 10 (1986) 133-137.
[38] and, A bi-criterion approach to minimizing inventory costs on a single machine when early shipments are forbidden. Comput. Operat. Res. 14 (1987) 363-368. | MR 904146 | Zbl 0624.90044
[39] , and, Single machine scheduling: A comparison of two solution procedures. Omega 15 (1987) 277-282.
[40] and, A simulated annealing heuristic for scheduling in a flowshop with bicriteria. Comput. Industrial Engrg. 27 (1994) 473-476.
[41] , and, One-processor scheduling with symmetric earliness and tardiness penalties. Math. Oper. Res. 13 (1988) 330-348. | MR 942622 | Zbl 0671.90033
[42] , Vector Optimization for Control with Performance and Parameter Sensitivity Indices, Ph.D. Thesis. Case Western Reserve University, Cleveland, USA (1973).
[43] , Proper efficiency and the theory of vector maximization. J. Math. Anal. Appl. 22 (1968) 618-630. | MR 229453 | Zbl 0181.22806
[44] , and, Single machine hierarchical scheduling with customer orders and multiple job classes. Ann. Oper. Res. 70 (1997) 127-143. | MR 1456796 | Zbl 0888.90091
[45] , and, Minimizing total flow time in a two-machine flowshop problem with minimum makespan. Internat. J. Production Economics (to appear).
[46] and, Minimizing a quadratic function of job lateness on a single machine. Engrg. Costs and Production Economic 7 (1983) 187-194.
[47] , and, On a bicriterion formulation of the problems of integrated system identification and system optimization. IEEE Trans. Systems, Man and Cybernetics 1 (1971) 296-297. | MR 300411 | Zbl 0224.93016
[48] and, A note on the extension of a result on scheduling with secondary criteria. Naval Res. Logist. Quarterly 19 (1972) 4. | MR 314446 | Zbl 0249.90033
[49] , Single-Machine Bicriteria Scheduling, Ph.D. Thesis. CWI Amsterdam (1992). | MR 1153250 | Zbl 0749.90042
[50] and, Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time. Oper. Res. Lett. 17 (1995) 205-208. | MR 1357076 | Zbl 0858.90075
[51] , Tradeoff solutions in single machine production scheduling for minimizing flow time and maximum penalty. Comput. Oper. Res. 16 (1984) 471-479. | Zbl 0673.90056
[52] , Minimizing the average deviation of job completion times about a common due date. Naval Res. Logist. Quarterly 28 (1981) 643-651. | Zbl 0548.90037
[53] , and, Scheduling of unit processing time jobs on a single machine, edited by G. Fandel and T. Gal, Multiple Criteria Decision Making. Springer-Verlag, Lecture Notes in Econom. and Math. Systems (1997) 654-660. | Zbl 0898.90066
[54] , Single-machine scheduling with time windows and earliness/tardiness penalties. Eur. J. Oper. Res. 91 (1996) 190-202. | Zbl 0947.90588
[55] ,, and, Optimal single-machine scheduling with earliness and tardiness penalties. Oper. Res. 26 (1978) 1079-1082. | MR 514876 | Zbl 0413.90031
[56] and, Complexity of single machine hierarchical scheduling: A survey, edited by P.M. Pardalos, Complexity in Numerical Optimization. World Scientific Publishing Co. (1993) 269-298. | MR 1358849 | Zbl 0968.90521
[57] and, Minimizing schedule length subject to minimum flow time. SIAM J. Comput. 18 (1989) 314-326. | MR 986670 | Zbl 0672.90070
[58] and, The parallel machine min-max weighted absolute lateness scheduling problem. Naval Res. Logist. 41 (1994) 33-46. | MR 1258731 | Zbl 0808.90082
[59] , and, Bicriterion scheduling in the two-machine flowshop. J. Oper. Res. Soc. 48 (1997) 929-935. | Zbl 0892.90106
[60] , Hybrid algorithm for sequencing with bicriteria. J. Opt. Theor. Appl. 39 (1983) 105-124. | MR 1551821 | Zbl 0479.90051
[61] and, Scheduling n independant jobs on m uniform machines with both flowtime and makespan objectives: A parametric analysis. ORSA J. Comput. 7 (1995) 63-77. | Zbl 0822.90084
[62] . On the Methodology of Multiobjective Optimization with Applications, Ph.D. Thesis. University of Jyvaskyla, Department of Mathematics (1994). | MR 1291825 | Zbl 0831.90099
[63] , One machine scheduling problem with dual criteria. J. Oper. Res. Soc. Jpn. 24 (1981) 37-50. | MR 614098 | Zbl 0453.90045
[64] , and, Multiple and bicriteria scheduling: A literature survey. Eur. J. Oper. Res. (1995) 88-104. | Zbl 0913.90178
[65] , and, A branch-and-bound approach for a two-machine flowshop scheduling problem. J. Oper. Res. Soc. 46 (1995) 721-734. | Zbl 0832.90058
[66] , and, Scheduling with multiple performance measures: The one-machine case. Management Sci. 32 (1986) 464-479. | Zbl 0603.90070
[67] , and, Genetic algorithms for the two-stage bicriteria flowshop problem. Eur. J. Oper. Res. 95 (1996) 356-373. | Zbl 0943.90584
[68] and, Filtered beam search in scheduling. Internat. J. Production Res. 26 (1988) 35-62.
[69] and, The single machine early/tardy problem. Management Sci. 35 (1989) 177-190. | MR 985231 | Zbl 0666.90043
[70] , and, Common due date assignment to minimize total penalty for the one machine scheduling problem. Oper. Res. 30 (1982) 391-399. | Zbl 0481.90042
[71] , Two-stage flowshop scheduling problem with bicriteria. J. Oper. Res. Soc. 43 (1992) 871-884. | Zbl 0757.90037
[72] , A heuristic for scheduling in flowshop and flowline-based manufacturing cell with multi-criteria. Internat. J. Production Res. 32 (1994) 2541-2558. | Zbl 0904.90076
[73] , Heuristics for scheduling in flowshop with multiple objectives. Eur. J. Oper. Res. 82 (1995) 540-555. | Zbl 0905.90107
[74] , and, Bicriteria scheduling hybrid flowshop problems, in International Conference on Industrial Engineering and Production Managment (IEPM'97). Lyon, France (1997) 34-43.
[75] , Méthodologie multicritère d'aide à la décision. Economica (1985).
[76] and, A bicriteria approach to the two-machine flow shop scheduling problem. Eur. J. Oper. Res. 113 (1999) 435-449. | Zbl 0957.90064
[77] , and, Optimal assignment of due-dates for a single processor scheduling problem. Internat. J. Production Res. 19 (1981) 393-399.
[78] and, A mixed integer goal-programming formulation of a flowshop scheduling problem. J. Oper. Res. Soc. 37 (1986) 1121-1128. | Zbl 0646.90041
[79] and, A branch-and-bound procedure to solve a bicriterion scheduling problem. IEEE Trans. 15 (1983) 84-88.
[80] , and, A branch-and-bound approach to the bicriterion scheduling problem involving total flowtime and range of lateness. Management Sci. 34 (1988) 255-260. | MR 930427 | Zbl 0638.90056
[81] and, A bicriteria two-machine permutation flowshop problem. Eur. J. Oper. Res. 107 (1998) 414-430. | Zbl 0943.90041
[82] , Scheduling jobs on one machine to minimize the maxium tardiness with minimum number tardy. Comput. Oper. Res. 10 (1983) 255-266. | MR 758165
[83] , Optimal single-machine scheduling with earliness and tardiness penalties. Oper. Res. 25 (1977) 62-69. | MR 443971 | Zbl 0383.90055
[84] , Various optimizers for single-stage production. Naval Res. Logist. Quarterly 3 (1956) 59-66. | MR 89109
[85] , Multicriteria optimization: A general characterization of efficient solutions. Decision Sci. 10 (1979) 27-38.
[86] , Multiple criteria optimization: Theory, computation and application. Wiley (1986). | MR 836977 | Zbl 0663.90085
[87] and, Minimizing the sum of absolute lateness in single-machine and multimachine scheduling. Naval Res. Logist. Quarterly 31 (1984) 325-333. | Zbl 0544.90052
[88] , Single-machine scheduling to minimize absolute deviation of completion times from a common due date. Naval Res. Logist. 36 (1989) 663-673. | MR 1016561 | Zbl 0674.90049
[89] and, L'ordonnancement multicritère. Presses de l'Université de Tours (2000).
[90] , and, A multi-criteria heuristic to solve a 2-stage hybrid flowshop scheduling problem. Eur. J. Automation (JESA) 34 (2000) 1187-1200.
[91] ,, and, Un algorithme optimal polynomial pour résoudre un problème d'ordonnancement bicritère à machines parallèles, in Conference on Automation-Computers Engineering-Image-Signal (AGIS'97). Angers, France (1997) 179-184.
[92] , and, Solving a bicriteria scheduling problem on unrelated parallel machines occuring in the glass bottle industry. Eur. J. Oper. Res. 135 (2001) 42-49. | Zbl 1077.90532
[93] ,, and, Resolution of a 2-machine bicriteria flowshop scheduling problem, in Int. Conference on Methods and Applications of Multicriteria Decision Making (MAMDM'97). Mons, Belgium (1997) 139-143.
[94] , and, in 6th International Workshop on Project Management and Scheduling (PMS'98). Istanbul, Turkey (1998).
[95] and, A bicriterion approach to time/cost trade-offs in sequencing. Eur. J. Oper. Res. 11 (1982) 48-54. | MR 671799 | Zbl 0482.90043
[96] and, Four solution techniques for a general one machine scheduling problem: A comparative study. Eur. J. Oper. Res. 2 (1978) 281-290. | MR 503705 | Zbl 0378.90044
[97] and, Solving a bicriterion scheduling problem. Eur. J. Oper. Res. 4 (1980) 42-48. | MR 549373 | Zbl 0418.90054
[98] , Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine. Oper. Res. 28 (1980) 115-167. | Zbl 0449.90054
[99] , Two single machine sequencing problems involving controllable job processing times. IEEE Trans. 12 (1980) 158-162. | MR 623328
[100] , and, Solving -stage hybrid flowshop scheduling problems, in Multiconference on Computational Engineering in Systems Applications (CESA'96), Symposium on Discrete Events and Manufacturing Systems (IEEE-SMC/IMACS). Lille, France (1996) 250-258.
[101] , and, Les flowshop hybrides : état de l'art. RAIRO: Oper. Res. 33 (1999) 117-183. | Numdam | Zbl 0960.90042
[102] , and, A genetic algorithm for scheduling job families on a single machine with arbitrary earliness/tardiness penalties and an unrestricted common due date. Internat. J. Production Res. 36 (1998) 2543-2551. | Zbl 0953.90527
[103] , The use of reference objectives in multiobjective optimization, edited by G. Fandel and T. Gal, Multiple criteria decision making, theory and application. Springer-Verlag (1990) 468-486. | MR 572784 | Zbl 0435.90098
[104] , Alternative formulations of a flow-shop scheduling problem. J. Oper. Res. Soc. 40 (1989) 395-399. | Zbl 0667.90050
[105] , and, A knowledgeable simulated annealing scheme for the early/tardy flow shop scheduling problem. Internat. J. Production Res. 33 (1995) 1449-1466. | Zbl 0909.90185
