Article ID: | iaor20061690 |
Country: | Netherlands |
Volume: | 99 |
Issue: | 1/2 |
Start Page Number: | 4 |
End Page Number: | 15 |
Publication Date: | Jan 2006 |
Journal: | International Journal of Production Economics |
Authors: | Portmann M.-C., Aggoune R. |
Keywords: | heuristics |
This paper addresses the flow shop scheduling problem with limited machine availability. In such a problem, n jobs have to be scheduled on m machines under the makespan criterion and under the assumption that the machines are not available during the whole planning horizon. Since the makespan minimization is strongly NP-hard, we propose a heuristic approach to approximately solve the problem that consists in scheduling the jobs two by two according to an input sequence, and using a polynomial algorithm. This algorithm is an extension of the geometric approach developed for the two-job shop scheduling problem.