Flow Shop Scheduling Problem with Limited Machine Availability: A Heuristic Approach

Abstract : 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 with minimum cost under the assumption that the machines are not available during the whole planning horizon, due in particular to a preventive maintenance activity. Since the makespan minimization is strongly NP-hard, we propose a heuristic approach to approximately solve the problem. This approach consists in scheduling the jobs two per two according to an input sequence and using a polynomial algorithm locally optimal. This algorithm is an extension of the geometric approach developed for the two-job shop-scheduling problem. As the performance of the heuristic depends on the input sequence, we use a tabu search to optimize it. Experiments are performed on randomly generated instances to test the efficiency of the proposed approach. || On s'intéresse au problème d'ordonnancement de type "flow shop" lorsque les machines ne sont pas toujours disponibles. N travaux doivent être ordonnancés sur M machines qui ont des périodes d'indisponibilité au cours du temps, dues en particulier à de la