Ordonnancement de travaux sur une machine unique

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.

     

Professeure à l'Université du Québec à Chicoutimi