Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion

  • ORIGINAL ARTICLE
  • Published:
The International Journal of Advanced Manufacturing Technology Aims and scope Submit manuscript

Abstract

An improved iterated greedy algorithm (IIGA) is proposed in this paper to solve the no-wait flow shop scheduling problem with the objective to minimize the makespan. In the proposed IIGA, firstly, a speed-up method for the insert neighborhood is developed to evaluate the whole insert neighborhood of a single solution with (n − 1)2 neighbors in time O(n 2), where n is the number of jobs; secondly, an improved Nawaz-Enscore-Ham (NEH) heuristic is presented for constructing solutions in the initial stage and searching process; thirdly, a simple local search algorithm based on the speed-up method is incorporated into the iterated greedy algorithm to perform exploitation. The computational results based on some well-known benchmarks show that the proposed IIGA can obtain results better than those from some existing approaches in the literature.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Stadtler H (2005) Supply chain management and advanced planning—basics, overview and challenges. Eur J Oper Res 163(3):575–588

    Article  MATH  Google Scholar 

  2. Pan Q-K, Tasgetiren MF, Liang Y-C (2005) A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem with makespan criterion. In: Proceedings of the 24th Annual Workshop of the UK Planning and Scheduling Special Interest Group (UK PlanSIG 2005), London, UK, December 2005, pp 31–41

  3. Wang L, Zheng D-Z (2003) An effective hybrid heuristic for flow shop scheduling. Int J Adv Manuf Technol 21(1):38–44

    Article  Google Scholar 

  4. Dimopoulos C, Zalazala AMS (2000) Recent developments in evolutionary computation for manufacturing optimization: problems, solutions, and comparisons. IEEE Trans Evolut Comput 4(2):93–113

    Article  Google Scholar 

  5. Liu B, Wang L, Jin Y-H (2007) An effective hybrid particle swarm optimization for no-wait flow shop scheduling. Int J Adv Manuf Technol 31:1001–1011

    Article  Google Scholar 

  6. Pan Q-K, Tasgetiren MF, Liang Y-C (2006) Minimizing total earliness and tardiness penalties with a common due date on a single-machine using a discrete particle swarm optimization algorithm. Lect Notes Comput Sci 4150:460–467

    Article  Google Scholar 

  7. Li B-B, Wang L (2007) A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling. IEEE Trans Syst Man Cybern B Cybern 37:576–591

    Article  Google Scholar 

  8. Wang L (2003) Shop scheduling with genetic algorithms. Tsinghua University Press, Beijing, China

    Google Scholar 

  9. Rajendran C (1994) A no-wait flowshop scheduling heuristic to minimize makespan. J Oper Res Soc 45:472–478

    Article  MATH  Google Scholar 

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

    MATH  MathSciNet  Google Scholar 

  11. Grabowski J, Pempera J (2000) Sequencing of jobs in some production system. Eur J Oper Res 125:535–550

    Article  MATH  MathSciNet  Google Scholar 

  12. Raaymakers WHM, Hoogeveen JA (2000) Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing. Eur J Oper Res 126:131–151

    Article  MATH  Google Scholar 

  13. Rock H (1984) The three-machine no-wait flow shop problem is NP-complete. J Assoc Comput Machinery 31:336–345

    MathSciNet  Google Scholar 

  14. Bonney MC, Gundry SW (1976) Solutions to the constrained flowshop sequencing problem. Oper Res Q 27:869–883

    MATH  Google Scholar 

  15. King JR, Spachis AS (1980) Heuristics for flowshop scheduling. Int J Prod Res 18:343–357

    Google Scholar 

  16. Gangadharan R, Rajedran C (1993) Heuristic algorithms for scheduling in the no-wait flowshop. Int J Prod Econ 32:285–290

    Article  Google Scholar 

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

    Article  MATH  Google Scholar 

  18. Schuster CJ, Framinan JM (2003) Approximative procedures for no-wait job shop scheduling. Oper Res Lett 31:308–318

    Article  MATH  MathSciNet  Google Scholar 

  19. Grabowski J, Pempera J (2005) Some local search algorithms for no-wait flow-shop problem with makespan criterion. Comput Oper Res 32:2197–2212

    Article  MATH  MathSciNet  Google Scholar 

  20. Ruiz R, Stützle T (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 177:2033–2049

    Article  MATH  Google Scholar 

  21. Jacobs LW, Brusco MJ (1995) A local-search heuristic for large set-covering problems. Nav Res Logist Q 42(7):1129–1140

    Article  MATH  MathSciNet  Google Scholar 

  22. Marchiori E, Steenbeek A (2000) An evolutionary algorithm for large scale set covering problems with application to airline crew scheduling. Lect Notes Comput Sci 1803:367–381

    Google Scholar 

  23. Nawaz M, Enscore EE Jr, Ham I (1983) A heuristic algorithm for the m-machine, n-job flow shop sequencing problem. Omega 11:91–95

    Article  Google Scholar 

  24. Koulamas C (1998) A new constructive heuristic for the flowshop scheduling problem. Eur J Oper Res 105:66–71

    Article  MATH  Google Scholar 

  25. Turner S, Booth D (1987) Comparison of heuristics for flow shop sequencing. Omega 15(1):75–85

    Article  Google Scholar 

  26. Carlier J (1978) Ordonnancements à contraintes disjonctives. RAIRO Rech Oper 12:333–351

    MATH  MathSciNet  Google Scholar 

  27. Reeves CR (1995) A genetic algorithm for flowshop sequencing. Comput Oper Res 22:5–13

    Article  MATH  Google Scholar 

  28. Heller J (1960) Some numerical experiments for an M×J flow shop and its decision-theoretical aspects. Oper Res 8:178–184

    Article  MATH  MathSciNet  Google Scholar 

  29. Osman IH, Potts CN (1989) Simulated annealing for permutation flow-shop scheduling. Omega 17(6):551–557

    Article  Google Scholar 

  30. Wang L, Zheng D-Z (2001) An effective hybrid optimization strategy for job-shop scheduling problems. Comput Oper Res 28(6):585–596

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Science and Technology of China, Hefei, 230026, People’s Republic of China

    Quan-Ke Pan & Bao-Hua Zhao

  2. College of Computer Science, Liaocheng University, Liaocheng, 252059, People’s Republic of China

    Quan-Ke Pan

  3. Department of Automation, Tsinghua University, Beijing, 100084, People’s Republic of China

    Ling Wang

Authors
  1. Quan-Ke Pan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ling Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bao-Hua Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Quan-Ke Pan.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pan, QK., Wang, L. & Zhao, BH. An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion. Int J Adv Manuf Technol 38, 778–786 (2008). https://doi.org/10.1007/s00170-007-1120-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00170-007-1120-y

Keywords

Search

Navigation