Méthode heuristique pour le problème de flow shop hybride avec machines dédiées

Najoua Dridi; Hatem Hadda; Sonia Hajri-Gabouj

RAIRO - Operations Research (2009)

  • Volume: 43, Issue: 4, page 421-436
  • ISSN: 0399-0559

Abstract

top
In this paper we deal with the two-stage hybrid flow shop with dedicated machines. The objective is to minimize the makespan. We first provide some basic properties, a set of lower bounds and two polynomial cases. We then propose a new heuristic based on the established properties. The heuristic tries to sequence jobs in such a way that the obtained makespan corresponds to the lower bound. In the last part, we present the results of a computational experience comparing our heuristic with another heuristic found in the literature. The analysis of those results allows us to appreciate the quality of our proposition.

How to cite

top

Dridi, Najoua, Hadda, Hatem, and Hajri-Gabouj, Sonia. "Méthode heuristique pour le problème de flow shop hybride avec machines dédiées." RAIRO - Operations Research 43.4 (2009): 421-436. <http://eudml.org/doc/250636>.

@article{Dridi2009,
abstract = { Dans ce papier, nous traitons le problème de minimisation du makespan dans un flow shop hybride à deux étages avec machines dédiées. En premier lieu, nous présentons des propriétés de base, un ensemble de bornes inférieures et deux cas polynomiaux. En second lieu, nous proposons une nouvelle heuristique qui exploite ces propriétés, et cherche à placer les jobs, en tenant compte pour chaque instance du problème, de la valeur de la borne inférieure. La dernière partie de ce travail présente les résultats expérimentaux d'une étude comparative avec une heuristique de la littérature. L'analyse de ces résultats permet d'apprécier la qualité de notre proposition. },
author = {Dridi, Najoua, Hadda, Hatem, Hajri-Gabouj, Sonia},
journal = {RAIRO - Operations Research},
keywords = {Ordonnancement; flow shop hybride; machines dédiées; bornes inférieures; cas polynomiaux; heuristiques. },
language = {fre},
month = {10},
number = {4},
pages = {421-436},
publisher = {EDP Sciences},
title = {Méthode heuristique pour le problème de flow shop hybride avec machines dédiées},
url = {http://eudml.org/doc/250636},
volume = {43},
year = {2009},
}

TY - JOUR
AU - Dridi, Najoua
AU - Hadda, Hatem
AU - Hajri-Gabouj, Sonia
TI - Méthode heuristique pour le problème de flow shop hybride avec machines dédiées
JO - RAIRO - Operations Research
DA - 2009/10//
PB - EDP Sciences
VL - 43
IS - 4
SP - 421
EP - 436
AB - Dans ce papier, nous traitons le problème de minimisation du makespan dans un flow shop hybride à deux étages avec machines dédiées. En premier lieu, nous présentons des propriétés de base, un ensemble de bornes inférieures et deux cas polynomiaux. En second lieu, nous proposons une nouvelle heuristique qui exploite ces propriétés, et cherche à placer les jobs, en tenant compte pour chaque instance du problème, de la valeur de la borne inférieure. La dernière partie de ce travail présente les résultats expérimentaux d'une étude comparative avec une heuristique de la littérature. L'analyse de ces résultats permet d'apprécier la qualité de notre proposition.
LA - fre
KW - Ordonnancement; flow shop hybride; machines dédiées; bornes inférieures; cas polynomiaux; heuristiques.
UR - http://eudml.org/doc/250636
ER -

References

top
  1. H. Hadda, N. Dridi and S. Hajri-Gabouj, Heuristiques pour le flow shop hybride à deux étages avec machines dédiées, in Actes de la Conférence Scientifique Conjointe en Recherche Opérationnelle et aide à la Décision : FRANCORO V/ROADEF. Grenoble, France (2007) 229–230.  
  2. H. Hadda, N. Dridi and S. Hajri-Gabouj, Heuristique d'ordonnancement du flow shop hybride à deux étages avec machines dédiées, in Actes du 7ème Congrès International de Génie Industriel : CIGI. Trois-Rivières, Québec (2007).  
  3. M. Haouari and T. Daouas, Optimal scheduling of the 3-machine assembly-type flow shop. RAIRO Oper. Res.33 (1999) 439–445.  
  4. S.M. Johnson, Optimal two- and three-stage production schedules with setup times included. Nav. Res. Log. Q.1 (1954) 61–68.  
  5. C.Y. Lee, T.C.E. Cheng and B.M.T. Lin, Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. Manage. Sci.39 (1993) 616–625.  
  6. B.M.T. Lin, The strong NP-hardness of two-stage flowshop scheduling with a common second-stage machine. Comput. Oper. Res.26 (1999) 695–698.  
  7. H.T. Lin and C.J. Liao, A case study in a two-stage hybrid flow shop with setup time and dedicated machines. Int. J. Prod. Econ.86 (2003) 133–143.  
  8. M. Lin and J. Wu, Effective lower bounds for scheduling problems in two-stage hybrid flowshops. J. Manage.21 (2004) 363–374.  
  9. C. Oguz, B.M.T. Lin and T.C.E. Cheng, Two-stage flowshop scheduling problem with a common second-stage machine. Comput. Oper. Res.24 (1997) 1169–1174.  
  10. C.N. Potts, S.V. Sevast'janov, V.A. Strusevich, L.N. Van, wassenhove and C.M. Zwaneveld, The two-stage assembly scheduling problem: complexity and approximation. Oper. Res.43 (1995) 346–355.  
  11. F. Riane, A. Artiba and S.E. Elmaghraby, Sequencing hybrid two-stage flow shop with dedicated machines, in 3e Conférence Francophone de modélisation et simulation “Conception, Analyse et Gestion des Systèmes Industriels”, MOSIM'01, Troyes, France (2001) 591–597.  
  12. F. Riane, A. Artiba and S.E. Elmaghraby, A hybrid three-stage flowshop problem: Efficient heuristics to minimise makespan. Eur. J. Oper. Res.109 (1998) 321–329.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.