Effective heuristics for the blocking flowshop scheduling problem with makespan minimization
The blocking flowshop scheduling problem with makespan criterion has important applications in a variety of industrial systems. Heuristics that explore specific characteristics of the problem are essential for many practical systems to find good solutions with limited computational effort. This paper first presents two simple constructive heuristics, namely weighted profile fitting (wPF) and PW, based on the profile fitting (PF) approach of McCormick et al. [Sequencing in an assembly line with blocking to minimize cycle time. Operations Research 1989;37:925-36] and the characteristics of the problem. Then, three improved constructive heuristics, called PF-NEH, wPF-NEH, and PW-NEH, are proposed by combining the PF, wPF, and PW with the enumeration procedure of the Nawaz-Enscore-Ham (NEH) heuristic [A heuristic algorithm for the m-machine, n-job flow shop sequencing problem. OMEGA-International Journal of Management Science 1983;11:91-5] in an effective way. Thirdly, three composite heuristics i.e., PF-NEHLS, wPF-NEHLS, and PW-NEHLS, are developed by using the insertion-based local search method to improve the solutions generated by the constructive heuristics. Computational simulations and comparisons are carried out based on the well-known flowshop benchmarks of Taillard [Benchmarks for basic scheduling problems. European Journal of Operation Research 1993;64:278-85] that are considered as blocking flowshop instances. The results show that the presented constructive heuristics perform significantly better than the existing ones, and the proposed composite heuristics further improve the presented constructive heuristics by a considerable margin. In addition, 17 new best-known solutions for Taillard benchmarks with large scale are found by the presented heuristics.
Volume (Year): 40 (2012)
Issue (Month): 2 (April)
|Contact details of provider:|| Web page: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description|
|Order Information:|| Postal: http://www.elsevier.com/wps/find/supportfaq.cws_home/regional|
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Ruiz-Torres, Alex J. & Ho, Johnny C. & Ablanedo-Rosas, José H., 2011. "Makespan and workstation utilization minimization in a flowshop with operations flexibility," Omega, Elsevier, vol. 39(3), pages 273-282, June.
- Taillard, E., 1993. "Benchmarks for basic scheduling problems," European Journal of Operational Research, Elsevier, vol. 64(2), pages 278-285, January.
- Ribas, Imma & Companys, Ramon & Tort-Martorell, Xavier, 2011. "An iterated greedy algorithm for the flowshop scheduling problem with blocking," Omega, Elsevier, vol. 39(3), pages 293-301, June.
- Framinan, J. M. & Leisten, R., 2003. "An efficient constructive heuristic for flowtime minimisation in permutation flow shops," Omega, Elsevier, vol. 31(4), pages 311-317, August.
- Ruiz, Rubén & Maroto, Concepciøn & Alcaraz, Javier, 2006. "Two new robust genetic algorithms for the flowshop scheduling problem," Omega, Elsevier, vol. 34(5), pages 461-476, October.
- Rad, Shahriar Farahmand & Ruiz, Rubén & Boroojerdian, Naser, 2009. "New high performing heuristics for minimizing makespan in permutation flowshops," Omega, Elsevier, vol. 37(2), pages 331-345, April.
- Liu, Jiyin & Reeves, Colin R, 2001. "Constructive and composite heuristic solutions to the P//[summation operator]Ci scheduling problem," European Journal of Operational Research, Elsevier, vol. 132(2), pages 439-452, July.
- Vallada, Eva & Ruiz, Rubén, 2010. "Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem," Omega, Elsevier, vol. 38(1-2), pages 57-67, February.
- Ruiz, Ruben & Maroto, Concepcion, 2005. "A comprehensive review and evaluation of permutation flowshop heuristics," European Journal of Operational Research, Elsevier, vol. 165(2), pages 479-494, September.
- Li, Xiaoping & Wang, Qian & Wu, Cheng, 2009. "Efficient composite heuristics for total flowtime minimization in permutation flow shops," Omega, Elsevier, vol. 37(1), pages 155-164, February.
- Grabowski, Jozef & Pempera, Jaroslaw, 2000. "Sequencing of jobs in some production system," European Journal of Operational Research, Elsevier, vol. 125(3), pages 535-550, September.
- Nawaz, Muhammad & Enscore Jr, E Emory & Ham, Inyong, 1983. "A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem," Omega, Elsevier, vol. 11(1), pages 91-95.
- Laha, Dipak & Sarin, Subhash C., 2009. "A heuristic to minimize total flow time in permutation flow shop," Omega, Elsevier, vol. 37(3), pages 734-739, June.
- Ronconi, Debora P., 2004. "A note on constructive heuristics for the flowshop problem with blocking," International Journal of Production Economics, Elsevier, vol. 87(1), pages 39-48, January.
- Grabowski, Jøzef & Pempera, Jaroslaw, 2007. "The permutation flow shop problem with blocking. A tabu search approach," Omega, Elsevier, vol. 35(3), pages 302-311, June.
- Caraffa, Vince & Ianes, Stefano & P. Bagchi, Tapan & Sriskandarajah, Chelliah, 2001. "Minimizing makespan in a blocking flowshop using genetic algorithms," International Journal of Production Economics, Elsevier, vol. 70(2), pages 101-115, March.
When requesting a correction, please mention this item's handle: RePEc:eee:jomega:v:40:y:2012:i:2:p:218-229. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu)
If references are entirely missing, you can add them using this form.