École Nationale Supérieure de
Techniques Avancées

Résumé

Nous présentons ici la formulation d’un problème d’ordonnancement classique, le problème du Job Shop, avec ces variables ensemblistes. Le Job Shop est un problème à nbMachines machines disjonctives, c’est-à-dire ne pouvant exécuter qu’une tâche à la fois. Le problème comporte un nombre de jobs nbJobs, chacun étant divisé en nbMachines tâches qui doivent être réalisées dans un ordre donné sur chacune de machines. L’objectif consiste à minimiser le makespan, c c’est-à-dire la date de complétion de la dernière tˆache. Les variables d’intervalles représentent les plages d’exécution des tâches et les variables de liste représentent l’ordre d’exécution des tâches. Le problème du Job Shop est NP-dur (voir Garey et al. (1976)). Le problème peut être modélisé ainsi avec le langage LSP.