Article ID: | iaor20001548 |
Country: | France |
Volume: | 33 |
Issue: | 2 |
Start Page Number: | 185 |
End Page Number: | 208 |
Publication Date: | Jan 1999 |
Journal: | RAIRO Operations Research |
Authors: | Pradin B., Lopez P., Levy M.L. |
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.