Temporal decomposition approach and characterisation of feasible solutions for the single machine scheduling problem

Temporal decomposition approach and characterisation of feasible solutions for the single machine scheduling problem

0.00 Avg rating0 Votes
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: , ,
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.

Reviews

Required fields are marked *. Your email address will not be published.