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

Dridi, Najoua; Hadda, Hatem; Hajri-Gabouj, Sonia

RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 4, pp. 421-436.

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.

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.

Classification : 90B35, 90B30
Keywords: scheduling, hybrid flow shop, dedicated machines, lower bounds, polynomial cases, heuristics
Mots clés : ordonnancement, flow shop hybride, machines dédiées, bornes inférieures, cas polynomiaux, heuristiques

[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. | Numdam | MR | Zbl

[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. | Zbl

[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. | MR | Zbl

[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. | Zbl

[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. | MR | Zbl

[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. | Zbl