A Genetic algorithm to minimize the makespan in the k-stage hybrid flow shop scheduling problem

• Autorzy: Besbes W. , Teghem J. , Loukil T.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we consider the k-stage hybrid flow shop scheduling problem where the parallel machines are identical. Our study aims to provide a good approximate solution to this specific problem with the makespan (Cmax) minimization as the objective function. Considering the success of the Genetic Algorithms (GA) developed for scheduling problems, we apply this metaheuristic to deal with this problem. We develop a GA with a new crossover operator. Indeed, it is a combination of two other crossover operator proposed in the literature. The design of our GA is different compared to the classical structure of the genetic algorithm especially in the encoding of solutions. For the calibration of our metaheuristic parameters, we conduct several experimental designs. Our algorithm is tested on a well known benchmark in the literature. The numerical results show that the proposed genetic algorithm is an efficient approach for solving the k-stage hybrid flow shop problem. Furthermore, this computational study shows that our GA, with the proposed crossover operator gives better results than the two other crossover operators.

Słowa kluczowe

EN

scheduling; hybrid flow shop; genetic algorithm

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2010
• Tom: Vol. 35, No. 1
• Strony: 3--24
• Opis fizyczny: Bibliogr 25 poz.

Twórcy

autor

Besbes W.

autor

Teghem J.

autor

Loukil T.

Bibliografia

• [1] Arthanary T.S., Ramaswamy K.G., An extension of two machine sequencing problem, The Journal of the Operational Research Society of India, 8, 4, 1971. 10-22.
• [2] Ben Hmida A., Huguet M-J., Lopez P., Haouari M., Climbing discrepancy search for solving the hybrid flow shop, European Journal of Industrial Engineering, 1, 2007, 223-243.
• [3] Bertel S., Billaut J.C., A genetic algorithm for an industrial multiprocessor flow shop scheduling problem with recirculation, European Journal of Operational Research, 159, 2004, 651-662.
• [4] Besbes W., A genetic algorithm to minimize the makespan in the k-stage hybrid flow shop, Master's Thesis, G.I.A.D-Faculty of Economics and Management of Sfax, Tunisia, 2006.
• [5] Campbell H.G., Dudek R.A., Smith M.L., A heuristic algorithm for the n-job m-machine sequencing problem, Management Sciences 16, 1970, 630-637.
• [6] Carlier J., Neron E., An exact method for solving the multiprocessor flowshop. R.A.I.R.O- R.O, 34, 2000, 1-25.
• [7] Engin O., Döyen A., A new approach to solve hybrid flow shop scheduling problems by artificial immune system, Future Generation Computer Systems 20, 2004, 1083-1095.
• [8] Graham R.L., Bounds for certain multiprocessing anomalies, The Bell System Technical Journal, 45, 1966, 1563-1581.
• [9] Guinet A., Solomon M.M., Kedia P.K., Dussauchoy A., A computational study of heuristics for two-stage flexible flowshop, International Journal of Production Research, 34, 1966, 1399-1415.
• [10] Gupta J.N.D., Two stage hybrid flowshop scheduling problem, Journal of Operational Research Society, 39, 1988, 359-364.
• [11] Gupta J.N.D., Tunc E.A., Schedules for a two stage hybrid flow shop with parallel machines at the second stage, International Journal of Production Research, 29, 1991, 1489-1502
• [12] Gupta J.N.D., Hariri A.M.A., Potts C.N., Scheduling a two-stage hybrid flow shop with parallel machines at the first stage, Annals of Operations Research, 69, 1997, 171-191.
• [13] Haouari M., Hidri L., Gharbi A., Optimal Scheduling of a two-stage hybrid flow shop, Mathematical Methods of Operational Research, 64, 2006, 107-124.
• [14] Hoogeveen J.A., Lenstra J.K., Veltman B., Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard, European Journal of Operational Research, 89, 1996, 172-175.
• [15] Hunsucker J.L., Sha R., Comparative performance analysis of priority rules in a constrained flow shop with multiple processors environment, European Journal of Operational Research, 72, 1994, 102-114.
• [16] Janiak A., Kozan E., Lichtenstein M., Oguz C., Metaheuristic approaches to the hybrid flow shop scheduling problem with cost-related criterion, International Journal of Production Economics, 105, 2007, 407-424.
• [17] Lee C.Y., Vairaktarakis G.L., Minimizing makespan in hybrid flow shop, Operations Research Letters, 16, 1994, 149-158.
• [18] Linn, R., Zhang, W., Hybrid flowshop scheduling: A survey, Computers and Industrial Engineering, 37, 1999, 57-61.
• [19] Naseri M.R.A., Behsehti-Nia M.A., Hybrid flow shop scheduling with parallel batching, International Journal Production Economics, 117, 2009, 185-196.
• [20] Neron E., Baptise P., Gupta J.N.D., Solving hybrid flow shop problem using energetic reasoning and global operations, Omega, 29, 2001, 501-511.
• [21] Oguz C., Ercan M.F., A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks, Journal of Scheduling, 8, 2005, 323-351.
• [22] Riane F., Artiba A., Elmaghraby S.E., A hybrid three stage flowshop problem: efficient heuristics to minimize makespan, European Journal of Operational Research, 109, 1998, 321-329.
• [23] Ruiz R., Maroto C., A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility, European Journal of Operational Research, 169,2006,781-800.
• [24] Soewnadi H., Elmaghraby S.E., Sequencing three-stage flexible flowshops with identical machines to minimize makespan, I IE Transactions, 31, 2001, 985-993.
• [25] Vignier A., Billaut J. C., Proust C., Les problèmes d'ordonnancement de type flow-shop hybride : etat de l'art, RAIRO Rech.Opèr, 33, 1999, 177-183.