| Article ID: | iaor20127619 |
| Volume: | 33 |
| Issue: | 2 |
| Start Page Number: | 185 |
| End Page Number: | 208 |
| Publication Date: | Apr 1999 |
| Journal: | RAIRO - Operations Research |
| Authors: | Levy M-L, Lopez P, Pradin B |
| Keywords: | scheduling, combinatorial optimization |
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.