🏭 Planificateur d'atelier — Recuit simulé en direct

Le recuit simulé est une métaheuristique d'optimisation combinatoire inspirée du procédé métallurgique consistant à chauffer puis refroidir lentement un matériau pour réduire les défauts. L'algorithme maintient une solution candidate, propose à répétition un petit changement aléatoire (un voisin), et décide de l'accepter ou non : les mouvements améliorants sont toujours acceptés, tandis que les mouvements dégradants sont acceptés avec une probabilité exp(−Δ/T), où Δ est l'ampleur de la dégradation du candidat et T la température actuelle. Un programme de refroidissement abaisse progressivement T, de sorte que la recherche accepte de nombreux mouvements dégradants au début (favorisant l'exploration et l'échappement aux minima locaux) et presque aucun à la fin (favorisant la convergence vers un fort optimum local).

Chaque tâche est une séquence fixe d'opérations qui doivent s'exécuter sur des machines spécifiques dans un ordre spécifique ; un planning est choisi en sélectionnant un ordre pour les opérations mises en file sur chaque machine. Étant donné à la fois l'ordre des tâches et l'ordre des machines, le véritable temps de fin de chaque opération est calculé par une simulation à événements discrets : une opération ne peut démarrer qu'une fois l'opération précédente de sa tâche terminée et une fois la machine dont elle a besoin libérée de toute opération mise en file auparavant. La durée totale globale est le temps de fin de la toute dernière opération sur toutes les machines.

Échanger deux opérations adjacentes sur une machine peut, dans de rares cas, créer un véritable blocage de planification : l'ordre machine de l'opération A exige qu'elle s'exécute après B, tandis que l'ordre tâche de B exige qu'elle s'exécute après A. Ce planning candidat n'a pas de temps de fin valide (un cycle non résolu dans le graphe de précédence), il est donc traité comme ayant une durée totale infinie et est toujours rejeté par le critère de Metropolis, quelle que soit la température.

Ces sauts vers le haut sont des mouvements dégradants acceptés — tout l'intérêt du recuit simulé. Si la recherche n'acceptait jamais que des améliorations, elle se comporterait comme une simple escalade de colline et pourrait rester bloquée définitivement dans le premier minimum local atteint. En tolérant certains plannings dégradés, surtout tôt quand la température est élevée, la recherche peut traverser une zone défavorable et trouver un meilleur bassin de l'autre côté ; la courbe de la meilleure valeur jusqu'ici n'enregistre que de véritables améliorations, elle ne monte donc jamais.

Oui. Étant donné un planning complet (ordre des tâches plus l'ordre des machines choisi), l'heure de début et de fin de chaque opération est calculée en triant topologiquement le graphe de précédence combiné et en propageant les heures de début au plus tôt vers l'avant — la même approche de simulation vers l'avant utilisée dans les véritables systèmes de planification de production. Il n'y a ni raccourci ni score fabriqué : le nombre affiché est le véritable temps de fin de la véritable dernière opération sous ce planning exact.