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
Type de document :
Communication dans un congrès
International Conference on Industrial Engineering and Production Management - IEPM'2003, May 2003, Porto, Portugal, 1, pp.140-149, 2003
Liste complète des métadonnées

https://hal.inria.fr/inria-00099826
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 09:41:35
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00099826, version 1

Collections

Citation

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, May 2003, Porto, Portugal, 1, pp.140-149, 2003. 〈inria-00099826〉

Partager

Métriques

Consultations de la notice

130