Colloque

Ordonnancement des tâches dans un atelier de construction

Michel Florian

Membre a labase

Michel Florian

Résumé du colloque

Le problème de l'ordonnancement des tâches dans un atelier de construction équipé de M machines et devant assurer la production d'une série de P pièces, a fait l'objet d'une étude dont les résultats ont été présentés dans le mémoire de maîtrise de Philippe Trépant. Après que ce problème ait été défini mathématiquement au moyen de la notion des systèmes de potentiels, une revue des méthodes de résolution actuellement connue a été faite. Seules semblaient présenter un intérêt pratique les méthodes énumératives, particulièrement celle de E. Balas. Cependant celle-ci voyait son efficacité limitée par sa trop grande généralité. Aussi s'est-on employé à développer un algorithme de "branch and bound", plus directement adapté à la nature de ce problème. Cet algorithme s'appuie sur une idée, que Brooks et White avaient formulée pour la résolution de problèmes munis d'hypothèses restrictives. Afin de les éliminer il a fallu étudier de nouvelles bornes et systématiser le processus de génération des solutions réalisables. Les tests effectués ont permis de conclure que, même si elle ne prétend pas résoudre les problèmes de toute taille, cette nouvelle méthode constitue un progrès sur celle de BALAS.