inria-00099826, version 1
Flow Shop Scheduling Problem with Limited Machine Availability: A Heuristic Approach
International Conference on Industrial Engineering and Production Management - IEPM'2003 1 (2003) 140-149
Résumé : 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
- a – CENTRE HENRI TUDOR (LUXEMBOURG)
- b – INPL
- 1 :
- INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Ecole normale supérieure de Paris - ENS Paris – Institut National Polytechnique de Lorraine (INPL)
- Domaine : Informatique/Autre
- Mots-clés : scheduling – flow shop – availability constraints – geometric approach || ordonnancement – "flow shop" – contraintes de disponibilité – approche géométrique
- Référence interne : A03-R-112 || aggoune03a
- Commentaire : Colloque avec actes et comité de lecture. internationale.
- inria-00099826, version 1
- http://hal.inria.fr/inria-00099826
- oai:hal.inria.fr:inria-00099826
- Contributeur :
- Soumis le : Mardi 26 Septembre 2006, 09:41:35
- Dernière modification le : Jeudi 28 Septembre 2006, 15:22:46




Exporter