Skip to main content
SpringerLink
Log in

An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling

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

Abstract

This paper considers the permutation flow shop scheduling problem with the objective of minimizing the makespan. A new hybrid heuristic, based on simulated annealing and an improvement heuristic, is presented. The proposed hybrid heuristic uses simulated annealing in conjunction with the constructive heuristic of Nawaz et al. (Omega 11:91–95, 1983). Computational experiments carried out with the benchmark problems of Taillard (Eur J Oper Res 64:278–285, 1993) show that the proposed method produces solutions that are mostly superior to those obtained with five state-of-the-art approaches. Statistical tests of significance are used to verify the improvement in solution quality.

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.

Institutional subscriptions

Similar content being viewed by others

References

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

  2. Campbell HG, Dudek RA, Smith ML (1970) A heuristic algorithm for the n-job, m-machine scheduling problem. Manage Sci 16:630–637

    Article  Google Scholar 

  3. Adiri I, Pohoryles D (1982) Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times. Nav Res Logistics 29:495–504. doi:10.1002/nav.3800290311

    Article  MATH  MathSciNet  Google Scholar 

  4. Nawaz M, Enscore E, Ham I (1983) A heuristic algorithm for the m- machine, n-job flowshop sequencing problem. Omega 11:91–95. doi:10.1016/0305-0483(83)90088-9

    Article  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  6. Bertolissi E (2000) Heuristic algorithm for scheduling in the no-wait flow-shop. J Mater Process Technol 107:459–465. doi:10.1016/S0924-0136(00)00720-2

    Article  Google Scholar 

  7. Lim A, Rodrigues B, Wang C (2006) Two-machine flow shop problems with a single server. J Sched 9:515–543. doi:10.1007/s10951-006-8787-z

    Article  MATH  MathSciNet  Google Scholar 

  8. Kumar A, Prakash A, Shankar R, Tiwari MK (2006) Psycho-clonal algorithm based approach to solve continuous flowshop scheduling problem. Expert Syst Appl 31:504–514. doi:10.1016/j.eswa.2005.09.059

    Article  Google Scholar 

  9. Ruiz R, Allahverdi A (2007) No-wait flowshop with separate setup times to minimize maximum lateness. Int J Adv Manuf Technol 35:551–565. doi:10.1007/s00170-006-0726-9

    Article  Google Scholar 

  10. Chakraborty UK, Laha D (2007) An improved heuristic for permutation flowshop scheduling. Int J Inf Commun Technol 1:89–97. doi:10.1504/IJICT.2007.013279

    Article  Google Scholar 

  11. Laha D, Chakraborty UK (2008) A constructive heuristic for minimizing makespan in no-wait flow shop scheduling. Int J Adv Manuf Technol. doi:10.1007/s00170-008-1454-0

  12. Dannenbring DG (1977) An evaluation of flow-shop sequencing heuristic. Manage Sci 23:1174–1182

    Article  MATH  Google Scholar 

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

    Google Scholar 

  14. Fink A, Voß S (2003) Solving the continuous flow-shop scheduling problem by metaheuristics. Eur J Oper Res 151:400–414. doi:10.1016/S0377-2217(02)00834-2

    Article  MATH  Google Scholar 

  15. Taillard E (1990) Some efficient heuristic methods for the flow shop sequencing problem. Eur J Oper Res 47:65–74. doi:10.1016/0377-2217(90)90090-X

    Article  MATH  MathSciNet  Google Scholar 

  16. Guinet A, Legrand M (1998) Reduction of job-shop problems to flow-shop problems with precedence constraints. Eur J Oper Res 109:96–110. doi:10.1016/S0377-2217(97)00129-X

    Article  MATH  Google Scholar 

  17. Wang L, Zheng D (2001) An effective hybrid optimization strategy for job-shop scheduling problems. Comput Oper Res 28:585–596. doi:10.1016/S0305-0548(99)00137-9

    Article  MATH  MathSciNet  Google Scholar 

  18. Cheung WM, Zhou H (2001) Using genetic algorithms and heuristics for job shop scheduling with sequence-dependent setup times. Ann Oper Res 107:65–81. doi:10.1023/A:1014990729837

    Article  MATH  MathSciNet  Google Scholar 

  19. Schuster CJ, Framinan JM (2003) Approximate procedures for no-wait job shop scheduling. Oper Res Lett 31:308–318. doi:10.1016/S0167-6377(03)00005-1

    Article  MATH  MathSciNet  Google Scholar 

  20. Garey MR, Jonson DS, Sethi R (1976) The complexity of flowshop and job shop scheduling. Math Oper Res 1:117–129

    Article  MATH  MathSciNet  Google Scholar 

  21. Gonzalez T, Sahni S (1978) Flow shop and job shop scheduling: complexity and approximation. Oper Res 26:36–52

    Article  MATH  MathSciNet  Google Scholar 

  22. Pinedo M (2002) Scheduling: theory, algorithms and systems, 2nd edn. Prentice-Hall, Englewood Cliffs

    MATH  Google Scholar 

  23. Chakraborty UK (ed) (2009) Computational intelligence in flow shop and job shop scheduling. Springer, Berlin (in press)

  24. Michalewicz Z (1996) Genetic algorithms + data structures = evolution programs. Springer, Berlin

    MATH  Google Scholar 

  25. Aarts E, Korst J (1989) Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing. Wiley, Chichester

    MATH  Google Scholar 

  26. Mansouri SA (2006) A simulated annealing approach to a bi-criteria sequencing problem in a two-stage supply chain. Comput Ind Eng 50:105–119. doi:10.1016/j.cie.2006.01.002

    Article  Google Scholar 

  27. Dorigo M, Maniezzo V, Colorni A (1996) The ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern Part B 26:29–41

    Article  Google Scholar 

  28. Storn R, Price KV (1997) Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. J Glob Optim 2:341–359. doi:10.1023/A:1008202821328

    Article  MathSciNet  Google Scholar 

  29. Chakraborty UK (ed) (2008) Advances in differential evolution. Springer, Berlin

  30. Qian B, Wang L, De-Xian H, Wang X (2008) Scheduling multi-objective job shops using a memetic algorithm based on differential evolution. Int J Adv Manuf Technol 35:1014–1027. doi:10.1007/s00170-006-0787-9

    Article  Google Scholar 

  31. Allahverdi A, Al-Anzi FS (2008) The two-stage assembly flowshop scheduling problem with bicriteria of makespan and mean completion time. Int J Adv Manuf Technol 37:166–177. doi:10.1007/s00170-007-0950-y

    Article  Google Scholar 

  32. Kennedy J, Eberhart RC, Shi Y (2001) Swarm intelligence. Academic, San Diego

    Google Scholar 

  33. Liao C-J, Tseng C-T, Luarn P (2007) A discrete version of particle swarm optimization for flowshop scheduling problems. Comput Oper Res 34:3099–3111. doi:10.1016/j.cor.2005.11.017

    Article  MATH  Google Scholar 

  34. Ross TJ (2004) Fuzzy logic with engineering applications, 2nd edn. Wiley, Chichester

    MATH  Google Scholar 

  35. Sakawa M, Kubota R (2000) Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithms. Eur J Oper Res 120:393–407. doi:10.1016/S0377-2217(99)00094-6

    Article  MATH  MathSciNet  Google Scholar 

  36. Laha D, Chakraborty UK (2008) An efficient heuristic approach to total flowtime minimization in permutation flowshop scheduling. Int J Adv Manuf Technol 38:1018–1025. doi:10.1007/s00170-007-1156-z

    Article  Google Scholar 

  37. Aldowaisan T, Allahverdi A (1998) Total flowtime in no-wait flowshops with setup times. Comput Oper Res 25:757–765. doi:10.1016/S0305-0548(98)00002-1

    Article  MATH  Google Scholar 

  38. Rajendran C, Ziegler H (1997) An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs. Eur J Oper Res 103:129–138. doi:10.1016/S0377-2217(96)00273-1

    Article  MATH  Google Scholar 

  39. Framinan JM, Leisten R, Ruiz-Usano R (2005) Comparison of heuristics for flow time minimization in permutation flow shop. Comput Oper Res 32:1237–1254

    MATH  Google Scholar 

  40. Sarin S, Lefoka M (1993) Scheduling heuristic for the n-job m-machine flow shop. OMEGA Int J Manage Sci 21(2):229–234

    Article  Google Scholar 

  41. Ishibuchi H, Misaki S, Tanaka H (1995) Modified simulated annealing algorithms for the flowshop sequencing problem. Eur J Oper Res 81:388–398. doi:10.1016/0377-2217(93)E0235-P

    Article  MATH  Google Scholar 

  42. Osman IH, Potts CN (1989) Simulated annealing for permutation flow-shop scheduling. OMEGA Int J Manage Sci 17:551–557

    Article  Google Scholar 

  43. Ben-Daya BM, Al-Fawzan M (1998) A tabu search approach for the flow shop-scheduling problem. Eur J Oper Res 109:88–95. doi:10.1016/S0377-2217(97)00136-7

    Article  MATH  Google Scholar 

  44. Reeves CR (1995) A genetic algorithm for flow shop sequencing. Comput Oper Res 22:5–11. doi:10.1016/0305-0548(93)E0014-K

    Article  MATH  Google Scholar 

  45. Rajendran C, Ziegler H (2004) Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. Eur J Oper Res 155:426–438. doi:10.1016/S0377-2217(02)00908-6

    Article  MATH  MathSciNet  Google Scholar 

  46. Agarwal A, Colak S, Eryarsoy E (2006) Improvement heuristic for the flow-shop scheduling problem: an adaptive-learning approach. Eur J Oper Res 169:801–815. doi:10.1016/j.ejor.2004.06.039

    Article  MATH  MathSciNet  Google Scholar 

  47. Hejazi SR, Saghafian S (2005) Flowshop-scheduling problems with makespan criterion: a review. Int J Prod Res 43:2895–2929. doi:10.1080/0020754050056417

    Article  MATH  Google Scholar 

  48. Ruiz R, Maroto C (2005) A comprehensive review and evaluation of permutation flow-shop heuristics. Eur J Oper Res 165:479–494. doi:10.1016/j.ejor.2004.04.017

    Article  MATH  MathSciNet  Google Scholar 

  49. Laha D, Chakraborty UK (2007) An efficient stochastic hybrid heuristic for flowshop scheduling. Eng Appl Artif Intell 20:851–856. doi:10.1016/j.engappai.2006.10.003

    Article  Google Scholar 

  50. Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680. doi:10.1126/science.220.4598.671

    Article  MathSciNet  Google Scholar 

  51. Ogbu FA, Smith DK (1990) The application of the simulated annealing algorithm to the solution of the n/m/Cmax flow shop problem. Comput Oper Res 17:243–253. doi:10.1016/0305-0548(90)90001-N

    Article  MATH  MathSciNet  Google Scholar 

  52. Ponnambalam SG, Aravindan P, Chandrasekaran S (2003) Constructive and improvement flow-shop scheduling heuristics: an extensive evaluation. Prod Plann Contr 12(4):335–344. doi:10.1080/09537280152004950

    Google Scholar 

  53. Stuetzle T (1998) An ant approach for the flow shop problem. In: Proceedings of the 6th European Congress on Intelligent Techniques and Soft Computing (EUFIT’98), vol 3. Verlag Mainz, Aachen, Germany, pp 1560–1564

  54. Liu J, Reeves CR (2001) Constructive and composite heuristics solution of the \(\left. P \right\|\sum {C_i } \) scheduling problem. Eur J Oper Res 132:439–452. doi:10.1016/S0377-2217(00)00137-5

    Article  MATH  MathSciNet  Google Scholar 

  55. Leon VJ, Ramamoorthy B (1997) An adaptable problem-space-based search methods for flexible flow line scheduling. IIE Trans 29(2):115–125

    Google Scholar 

  56. Turner S, Booth D (1987) Comparison of heuristics for flow shop sequencing. OMEGA Int J Manage Sci 15(1):75–78

    Article  Google Scholar 

  57. Koulamas C (1998) A new constructive heuristic for a flowshop-scheduling problem. Eur J Oper Res 105:66–71. doi:10.1016/S0377-2217(97)00027-1

    Article  MATH  Google Scholar 

  58. Davoud Pour H (2001) A new heuristic for the n-job, m-machine flow-shop problem. Prod Plann Contr 12(7):648–653. doi:10.1080/09537280152582995

    Article  Google Scholar 

  59. Merkle D, Middendorf M (2000) An ant algorithm with a new pheromone evaluation rule for total tardiness problems. In: Proceedings of the Evo Workshops 2000. In: Lecture Notes in Computer Science, vol 1803. Springer, Berlin, pp 287–296

  60. Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64:278–285. doi:10.1016/0377-2217(93)90182-M

    Article  MATH  Google Scholar 

  61. Palmer DS (1965) Sequencing jobs through a multi-stage process in the total time—a quick method of obtained a near optimum. Oper Res Q 16:101–107

    Article  Google Scholar 

  62. Grabowski J, Pempera J (2007) The permutation flow shop problem with blocking. Omega 35:302–311. doi:10.1016/j.omega.2005.07.004

    Article  Google Scholar 

  63. Kreyszig E (1972) Advanced engineering mathematics. Wiley, New York

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Mechanical Engineering Department, Jadavpur University, Kolkata, 700032, India

    Dipak Laha

  2. Department of Mathematics and Computer Science, University of Missouri, St. Louis, MO, 63121, USA

    Uday Kumar Chakraborty

Authors
  1. Dipak Laha
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Uday Kumar Chakraborty
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Uday Kumar Chakraborty.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Laha, D., Chakraborty, U.K. An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling. Int J Adv Manuf Technol 44, 559–569 (2009). https://doi.org/10.1007/s00170-008-1845-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00170-008-1845-2

Keywords

Search

Navigation