Flow shop scheduling problem with limited machine availability: A heuristic approach

This paper addresses the flow shop scheduling problem with limited machine availability. In such a problem, n jobs has 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.