IDEAS home Printed from https://ideas.repec.org/
MyIDEAS: Log in (now much improved!) to save this article

Effective heuristics for the blocking flowshop scheduling problem with makespan minimization

Author Info

Listed author(s):
  • Pan, Quan-Ke
  • Wang, Ling
Registered author(s):

    Abstract

    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.

    Download Info

    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.

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048311000971
    Download Restriction: Full text for ScienceDirect subscribers only

    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.

    Article provided by Elsevier in its journal Omega.

    Volume (Year): 40 (2012)
    Issue (Month): 2 (April)
    Pages: 218-229

    as
    in new window

    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

    Keywords: Flowshop Blocking Makespan Constructive heuristics Composite heuristics;

    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.:

    as
    in new window


    1. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. Taillard, E., 1993. "Benchmarks for basic scheduling problems," European Journal of Operational Research, Elsevier, vol. 64(2), pages 278-285, January.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    Full references (including those not matched with items on IDEAS)

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.

    as
    in new window


    Cited by:

    1. Lin, Shih-Wei & Ying, Kuo-Ching, 2016. "Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics," Omega, Elsevier, vol. 64(C), pages 115-125.
    2. Pan, Quan-Ke & Wang, Ling & Li, Jun-Qing & Duan, Jun-Hua, 2014. "A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation," Omega, Elsevier, vol. 45(C), pages 42-56.
    3. Shabtay, Dvir & Arviv, Kfir & Stern, Helman & Edan, Yael, 2014. "A combined robot selection and scheduling problem for flow-shops with no-wait restrictions," Omega, Elsevier, vol. 43(C), pages 96-107.
    4. Pan, Quan-Ke & Ruiz, Rubén, 2014. "An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem," Omega, Elsevier, vol. 44(C), pages 41-50.
    5. Lin, Shih-Wei & Ying, Kuo-Ching, 2013. "Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm," Omega, Elsevier, vol. 41(2), pages 383-389.

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    Access and download statistics

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

    This information is provided to you by IDEAS at the Research Division of the Federal Reserve Bank of St. Louis using RePEc data.