Ordonnancement de n travaux sur une machine unique avec réglages dépendant de la séquence (Scheduling single machine total tardiness problem with sequence-dependent setup times)
Objectif: Minimisation du temps total de retard/minimizing total tardiness
Problèmes de 55, 65, 75 et 85 jobs:
Problèmes de 15, 25, 35 et 45 jobs (initial instances from Rubin and Ragatz, 1995):
Meilleures solutions connues à l’aide de la recherche avec tabou ou de l’optimisation par colonie de fourmis (best known solution by taboo search or ant colony optimization)
| PROBLÈME | MEILLEURE SOLUTION CONNUE | PROBLÈME | MEILLEURE SOLUTION CONNUE | |
|---|---|---|---|---|
| PROB401.TXT | 90 * | PROB551.TXT | 185 | |
| PROB402.TXT | 0 * | PROB552.TXT | 0 * | |
| PROB403.TXT | 3418 * | PROB553.TXT | 40524 | |
| PROB404.TXT | 1067 * | PROB554.TXT | 14653 | |
| PROB405.TXT | 0 * | PROB555.TXT | 0 * | |
| PROB406.TXT | 0 * | PROB556.TXT | 0 * | |
| PROB407.TXT | 1861 * | PROB557.TXT | 35813 | |
| PROB408.TXT | 5660 * | PROB558.TXT | 19871 | |
| PROB501.TXT | 261* | PROB651.TXT | 262 | |
| PROB502.TXT | 0 * | PROB652.TXT | 0 * | |
| PROB503.TXT | 3497* | PROB653.TXT | 57565 | |
| PROB504.TXT | 0 * | PROB654.TXT | 34356 | |
| PROB505.TXT | 0 * | PROB655.TXT | 2 | |
| PROB506.TXT | 0 * | PROB656.TXT | 0 * | |
| PROB507.TXT | 7225* | PROB657.TXT | 54895 | |
| PROB508.TXT | 1915* | PROB658.TXT | 27114 | |
| PROB601.TXT | 12* | PROB751.TXT | 241 | |
| PROB602.TXT | 0 * | PROB752.TXT | 0 * | |
| PROB603.TXT | 17587* | PROB753.TXT | 77709 | |
| PROB604.TXT | 19092* | PROB754.TXT | 35256 | |
| PROB605.TXT | 228* | PROB755.TXT | 0 * | |
| PROB606.TXT | 0 * | PROB756.TXT | 0 * | |
| PROB607.TXT | 12969* | PROB757.TXT | 59702 | |
| PROB608.TXT | 4732* | PROB758.TXT | 38370 | |
| PROB701.TXT | 97* | PROB851.TXT | 375 | |
| PROB702.TXT | 0 * | PROB852.TXT | 0 * | |
| PROB703.TXT | 26506* | PROB853.TXT | 97764 | |
| PROB704.TXT | 15206* | PROB854.TXT | 79508 | |
| PROB705.TXT | 200* | PROB855.TXT | 272 | |
| PROB706.TXT | 0 * | PROB856.TXT | 0 * | |
| PROB707.TXT | 23789* | PROB857.TXT | 87219 | |
| PROB708.TXT | 22807* | PROB858.TXT | 74893 |
* Solution optimale/optimal solution
Papers
-
Gagné C., Gravel M., Price W.L., Using metaheuristics and compromise programming for the solution of multiple objective scheduling problems, (en préparation).
-
Gagné C., Price W.L., Gravel M. (2002), Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence dependent setup times, Journal of the Operational Research Society, Vol. 53 No.8 pp 895-906.
-
Tan K.C., R. Narasimhan, et al. (2000). A comparison of four methods for minimizing total tardiness on a single processor with sequence dependent setup times. Omega 28: 313-326.
-
Tan K. C. and R. Narasimhan (1997). Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach, Omega 25(6): 619-634.
-
Rubin, P. A. and G. L. Ragatz. (1995). Scheduling in a sequence dependent setup environment with genetic search. Computers and Operations Research, Vol. 22, No. 1.