Skip to main content
SpringerLink
Log in

New heuristics for the no-wait flowshop with sequence-dependent setup times problem

  • Technical Paper
  • Published:
Journal of the Brazilian Society of Mechanical Sciences and Engineering Aims and scope Submit manuscript

Abstract

In this paper, we address the problem of scheduling jobs in a no-wait flowshop with sequence-dependent setup times with the objective of minimizing the makespan and the total flowtime. As this problem is well known for being NP hard, we present two new constructive heuristics to obtain good approximate solutions for the problem in a short CPU time, named GAPH and QUARTS. GAPH is based on a structural property for minimizing makespan and QUARTS breaks the problem in quartets to minimize the total flowtime. Experimental results demonstrate the superiority of the proposed approaches over three of the best-known methods in the literature: BAH and BIH, from Bianco et al. (INFOR J 37(1):3–19, 1999) and TRIPS, by Brown et al. (J Oper Res Soc 55(6):614–621, 2004).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Aldowaisan T, Allahverdi A (2003) New heuristics for no-wait flowshops to minimize makespan. Comput Oper Res 30(8):1219–1231

    Article  MATH  Google Scholar 

  2. Allahverdi A, Aldowaisan T (2000) No-wait and separate setup three-machine flowshop with total completion time criterion. Int Trans Oper Res 7(3):245–264

    Article  MathSciNet  Google Scholar 

  3. Allahverdi A, Gupta JND, Aldowaisan T (1999) A review of scheduling research involving setup considerations. Omega Int J Manag Sci 27(2):219–239

    Article  Google Scholar 

  4. Allahverdi A, Aldowaisan T (2001) Minimizing total completion time in a no-wait flowshop with sequence-dependent additive changeover times. J Oper Res Soc 52(4):449–462

    Article  MATH  Google Scholar 

  5. Allahverdi A, Ng CT, Cheng TCE, Kovalyov MY (2008) A survey of scheduling problems with setups times or costs. Eur J Oper Res 187(3):985–1032

    Article  MATH  MathSciNet  Google Scholar 

  6. Allahverdi A, Soroush HM (2008) The significance of reducing setup times/setup costs. Eur J Oper Res 187(3):978–984

    Article  MATH  Google Scholar 

  7. Bianco L, Dell’Olmo P, Giordani S (1999) Flow shop no-wait scheduling with sequence-dependent setup times and release dates. INFOR J 37(1):3–19

    Google Scholar 

  8. Brown SI, Mcgarvey R, Ventura JA (2004) Total flowtime and makespan for a no-wait m-machine flowshop with set-up times separated. J Oper Res Soc 55(6):614–621

    Article  MATH  Google Scholar 

  9. Eren T (2010) A bicriteria m-machine flowshop scheduling with sequence dependent setup times. Appl Math Model 34(2):284–293

    Article  MATH  MathSciNet  Google Scholar 

  10. Fink A, Voβ S (2003) Solving the continuos flow-shop scheduling problem by metaheuristics. Eur J Oper Res 151(2):400–414

    Article  MATH  Google Scholar 

  11. Framinan JM, Nagano MS (2008) Evaluating the performance for makespan minimisation in no-wait flowshop sequencing. J Mater Process Technol 197(1):1–9

    Article  Google Scholar 

  12. Framinan JM, Nagano MS, Moccellin JV (2010) An efficient heuristic for total flowtime minimisation in no-wait flowshops. Int J Adv Manuf Technol 46(9–12):1049–1057

    Article  Google Scholar 

  13. França PM, Tin G Jr, Buriol LS (2006) Genetic Algorithms for the no-wait flowshop sequencing problem with time restrictions. Int J Prod Res 44(5):939–957

    Article  Google Scholar 

  14. Grabowski J, Pempera J (2007) The permutation flowshop problem with blocking—a tabu search approach. Omega Int J Manag Sci 35(3):302–311

    Article  Google Scholar 

  15. Hall NG, Sriskandarajah C (1996) A survey of machine scheduling problems with blocking and no-wait in process. Oper Res 44(3):510–525

    Article  MATH  MathSciNet  Google Scholar 

  16. Kumar S, Bagchi TP, Sriskandarajah C (2000) Lot streaming and scheduling heuristics for m-machine no-wait flowshops. Comput Ind Eng 38(1):149–172

    Article  Google Scholar 

  17. Nagano MS, Silva AA, Lorena LAN (2012) A new evolutionary clustering search for a no-wait flow shop problem with set-up times. Eng Appl Artif Intell 25(6):1114–1120

    Article  Google Scholar 

  18. Pan Q-K, Tasgetiren MF, Liang Y-C (2008) A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. Comput Oper Res 35(9):2807–2839

    Article  MATH  MathSciNet  Google Scholar 

  19. Ribeiro Filho G, Nagano MS, Lorena LAN (2007) Hybrid evolutionary algorithm for flowtime minimisation in no-wait flowshop scheduling. Lect Notes Comput Sci 4827:1099–1109

    Article  Google Scholar 

  20. Ruiz R, Allahverdi A (2007) Some effective heuristics for no-wait flowshops with setup times to minimize total completion time. Ann Oper Res 156(1):143–171

    Article  MATH  MathSciNet  Google Scholar 

  21. Ruiz R, Allahverdi A (2007) No-wait flowshop with separate setup times to minimize maximum lateness. Int J Adv Manuf Technol 35(5–6):551–565

    Article  Google Scholar 

  22. Ruiz R, Maroto C, Alcaraz J (2005) Solving the flowshop scheduling problem with sequence-dependent setup times using advanced metaheuristics. Eur J Oper Res 165(1):34–54

    Article  MATH  MathSciNet  Google Scholar 

  23. Ruiz R, Stützle T (2008) An iterated greedy heuristic for the sequence dependent setup times flowshop with makespan and weighted tardiness objectives. Eur J Oper Res 187(3):1143–1159

    Article  MATH  Google Scholar 

  24. Shyu SJ, Lin BMT, Yin PY (2004) Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time. Comput Ind Eng 47(2–3):181–193

    Article  Google Scholar 

  25. Stafford EF Jr, Tseng FT (2002) Two models for a family of flowshop sequencing problems. Eur J Oper Res 142(2):282–293

    Article  MATH  MathSciNet  Google Scholar 

  26. Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64(2):278–285

    Google Scholar 

  27. Wang C, Li X, Wang Q (2010) Accelerated tabu search for no-wait flowshop scheduling problem with maximum lateness criterion. Eur J Oper Res 206(1):64–72

    Article  MATH  Google Scholar 

  28. Yaurima V, Burtseva L, Tchernykh A (2009) Hybrid flowshop with unrelated machines, sequence dependent setup time, availability constraints and limited buffers. Comput Ind Eng 56(4):1452–1463

    Article  Google Scholar 

Download references

Acknowledgments

The research of the first author is partially supported by a grants numbers 476753/2011-2 and 303000/2010-4 from the National Council for Scientific and Technological Development (CNPq), Brazil. The research of the second author is partially supported by The State of São Paulo Research Foundation (FAPESP) under grant number 09/06832-2.

Author information

Authors and Affiliations

  1. School of Engineering of São Carlos, University of São Paulo, Production Engineering, 13566-590, São Carlos, São Paulo, Brazil

    Marcelo Seido Nagano & Daniella Castro Araújo

Authors
  1. Marcelo Seido Nagano
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniella Castro Araújo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marcelo Seido Nagano.

Additional information

Technical Editor: Fernando Forcellini.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Nagano, M.S., Araújo, D.C. New heuristics for the no-wait flowshop with sequence-dependent setup times problem. J Braz. Soc. Mech. Sci. Eng. 36, 139–151 (2014). https://doi.org/10.1007/s40430-013-0064-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40430-013-0064-4

Keywords

Search

Navigation