Décomposition temporelle et caractérisation de solutions admissibles pour le problème d'ordonnancement à une machine

¹ LAAS-CNRS, 7 avenue du Colonel Roche, 31077 Toulouse Cedex 4, France
² INSA, Complexe Scientifique de Rangueil, 31077 Toulouse Cedex 4, France e-mail: lopez.pradin@laas.fr

Received: May 1996

Abstract

We propose a temporal decomposition approach for the one-machine scheduling problem with ready times and due dates. A set of feasible schedules is characterized by means of constraint-based analysis rules. They permit the determination of the feasible locations of each task in a sequence, represented by rank intervals. A decomposition procedure based on comparisons of rank intervals is developed in order to group tasks to be sequenced in the neighbourhood of each other in a feasible solution. Computational results are reported so that the capability of our approach to prepare the problem for a solution computation, achieved either by a human operator or by an automatic solving procedure, can be evaluated.

Résumé

Nous proposons une approche par caractérisation de solutions admissibles pour la décomposition temporelle du problème d'ordonnancement à une machine avec contraintes de dates limites. La technique de caractérisation repose sur l'utilisation de règles d'analyse sous contraintes. Elles permettent de déterminer les positions admissibles de chaque tâche dans une séquence, représentées par des intervalles de rangs. Une procédure de décomposition basée sur des comparaisons d'intervalles de rangs est développée pour regrouper les tâches de localisation proche dans toute solution admissible. Des résultats expérimentaux sont présentés pour valider notre approche en tant que phase de préparation à la recherche d'une solution, que celle-ci soit menée par une procédure de résolution automatique, ou par un opérateur humain dans un contexte de coopération homme-ordinateur.