On Recent Modifications And Extensions Of The Neh Heuristic For Flow Shop Sequencing

• Autorzy: Kalczyński P.J. , Kamburowski J.
• Języki publikacji: EN

Abstrakty

EN

Until recently, the NEH heuristic of Nawaz, Enscore and Ham published in j 1983 was commonly regarded as the best constructive heuristic for solving the classic j strongly NP-hard problem of minimizing the makespan in permutation flow shops. The I long-lasting success of NEH inspired many researchers to propose improvements to the original heuristic. In this paper, we empirically examine recent modifications and extensions of NEH and present a heuristic for the permutation flow shop problem which incorporates components from the best proposals. The performance of analyzed heuristics is evaluated with respect to the improvement over NEH and additional computational time required to achieve this improvement.

Słowa kluczowe

EN

scheduling; flow shop; makespan; constructive heuristics

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2011
• Tom: Vol. 36, No. 1
• Strony: 18--33
• Opis fizyczny: Bibliogr. 26 poz.

Twórcy

autor

Kalczyński P.J.

autor

Kamburowski J.

• Mihaylo College of Business and Economics, California State University, Fullerton, Fullerton, CA 92834, tel: [phone],

Bibliografia

• [1] C. Low, J.Y. Yeh & K.I. Huang: A robust simulated annealing heuristic for flow shop scheduling problems. International Journal of Advanced Manufacturing Technology. 23, 2004, 762-767.
• [2] C.R. Reeves: Improvements to the NEH heuristic for flowshop scheduling. SOR91/2. Coventry, UK, Coventry University, 1991.
• [3] E. Tail lard: Benchmarks for basic scheduling problems. European Journal of Operational Research. 64, 1993, 278-285.
• [4] E. Taillard: Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research. 47, 1990, 65-74.
• [5] G.I. Zobolas, C.D. Tarantilis & G. loannou: Minimizing makespan in permutation flowshop scheduling problems using a hybrid metaheuristic algorithm. Computers and Operations Research. 36, 2009, 1249-1267.
• [6] J. M. Framinan, R. Leisten & C. Rajendran: Different initial sequences for the heuristic of nawaz, enscore and ham to minimize makespan, idle time or flowtime in the static permutation flowshop problem. International Journal of Production Research. 41, 2003, 121-148.
• [7] J.P. Stinson & A.W. Smith: A heuristic programming procedure for sequencing the static flowshop. International Journal of Production Research. 20, 1982, 753-764.
• [8] L. Deroussi, M. Gourgand & S. Noire: New effective neighborhoods for the permutation flow shop problem. Unpublished manuscript, 2006.
• [9] L.Y. Tseng & Y.T. Lin: A hybrid genetic local search algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research. 198, 2009, 84-92.
• [10] M. Nawaz, E. Enscore & I. Ham: A heuristic algorithm for the m-machine, n-job flowshop sequencing problem. Omega, the International Journal of Management Science. 11, 1983,91-95.
• [11] M.F. Tasgetiren, Y.C. Liang, M. Sevkli & G. Gencyilmaz: A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research. 177,2007, 1930-1947.
• [12] JM.R.D. Garey, D.S. Johnson & R. Sethi: The complexity of flow shop and job shop scheduling. Mathematics of Operations Research. 1, 1976, 117-129.
• [13] M.S. Nagano & J.V. Moccellin: A high quality solution constructive heuristic for flow shop sequencing. Journal of the Operational Research Society. 53, 2002, 1374-1379.
• [14] P.J. Kalczynski & J. Kamburowski: An empirical analysis of the optimality rate of flow shop heuristics. European Journal of Operational Research. 198, 2009, 93-101.
• [15] P.J. Kalczynski & J. Kamburowski: An improved NEH heuristic to minimize makespan in permutation flow shops. Computers & Operations Research. 35, 2008, 3001-3008.
• [16] P.J. Kalczynski & J. Kamburowski: On the NEH heuristic for minimizing the makespan in permutation flowshops. Omega, the International Journal of Management Science. 35, 2007, 53-60.
• [17] R. Companys & M. Mateo: Different behaviour of a double branch-and-bound-algorithm on Fm|prmu|Cmax and Fm|block|Cmax problems. Computers & Operations Research. 34, 2007, 938-953.
• [18] S. Gao, Y. Liu, W. Zhang & J. Zhang: Some supplementation for NEH heuristic in solving flow shop problem. Proceedings of the 2007 American Control Conference. New York, 2007, 3348-3352.
• [19] S.F. Rad, R. Ruiz & N. Boroojerdian: New high performing heuristics for minimizing makespan in permutation flowshops. Omega, the International Journal of Management Science. 37, 2009, 331-345.
• [20] S.M. Johnson: Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly. 1, 1954, 61-68.
• [21] S.W. Gao, C. Lin & W.D. Zhang: Enhanced NEH method in solving permutation flow shop problem. Journal of Shanghai Jiaotong University (Science). 72, 2007, 47-52.
• [22] S.W. Gao, R. Leisten, Y. Dai & W.D. Zhang: Break the ties for NEH heuristic in solving the permutation flow shop problems. Journal ofDonghua University. 25, 2008, 1-11.
• [23] S.W. Gao & W.D. Zhang: The modification on NEH heuristic in solving permutation flow shop scheduling problems. Unpublished manuscript, 2007.
• [24] U.K. Chakraborty & D. Laha: An improved heuristic for permutation flowshop scheduling. International Journal of Information and Communication Technology 1 2007,89-97.
• [25] X. Dong, H. Huang & P. Chen: An improved NEH-based heuristic for the permutation flowshop problem. Computers & Operations Research. 35, 2008, 3962-3968.
• [26] X.P. Li & Y.X. Wang. Heuristic algorithms for large flowshop scheduling problems (in Chinese). World Congress on Intelligent Control and Automation (WCICA) Hangzhou, China, 2004, 2999-3003.