Skip to Main content Skip to Navigation
Conference papers

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

Riad Aggoune 1 Marie-Claude Portmann 1
1 MACSI - Industrial system modeling, analysis and operation
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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
Document type :
Conference papers
Complete list of metadata
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 9:41:35 AM
Last modification on : Friday, February 26, 2021 - 3:28:04 PM


  • HAL Id : inria-00099826, version 1



Riad Aggoune, Marie-Claude Portmann. Flow Shop Scheduling Problem with Limited Machine Availability: A Heuristic Approach. International Conference on Industrial Engineering and Production Management - IEPM'2003, Fucam, May 2003, Porto, Portugal, pp.140-149. ⟨inria-00099826⟩



Record views