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.
If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Volume (Year): 40 (2012)
Issue (Month): 2 (April)
Pages: 218-229
| Handle: | RePEc:eee:jomega:v:40:y:2012:i:2:p:218-229 |
| 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 Web: https://shop.elsevier.com/order?id=375&ref=375_01_ooc_1&version=01 |
References listed on IDEAS
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.:
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Taillard, E., 1993. "Benchmarks for basic scheduling problems," European Journal of Operational Research, Elsevier, vol. 64(2), pages 278-285, January.
- 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.
- 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.
- 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.
This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.
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: (Zhang, Lei)
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.