28605 articles – 22086 Notices  [english version]

inria-00099826, version 1

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

Riad Aggoune () a1, Marie-Claude Portmann () b1

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 :  MACSI (INRIA Lorraine - LORIA)
  • 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
  • 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