Skip to main content
SpringerLink
Log in

A genetic algorithm for the simultaneous lot sizing and scheduling problem in capacitated flow shop with complex setups and backlogging

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

Abstract

In this paper the capacitated lot sizing and scheduling problem with sequence-dependent setups, setup carryover, and backlogging has been studied. The problem can be formulated as a mixed-integer program. Most lot sizing problems are hard to solve, especially in medium and large scale. In recent years, to deal with the complexity and find optimal or near-optimal results in reasonable computational time, a growing number of researchers have employed metaheuristic approaches to lot sizing problems. One of the most popular metaheuristics is genetic algorithm which has been applied to different optimization problems successfully. Therefore, we have developed a genetic algorithm to solve this model. To test the accuracy of the genetic algorithm, a lower bound is developed and compared against the genetic algorithm. In computational experiments, proposed genetic algorithm performed extremely well. It is concluded that the genetic algorithm is efficient and effective for this problem.

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. Eppen GD, Martin RK (1987) Solving multi-item capacitated lot-sizing problems using variable redefinition. Oper Res 35(6):832–848

    Article  MATH  Google Scholar 

  2. Fleischmann B (1990) The discrete lot-sizing and scheduling problem. Eur J Oper Res 44:337–348

    Article  MATH  MathSciNet  Google Scholar 

  3. Haase K (1996) Capacitated lot-sizing with sequence dependent setup costs. OR Spektrum 18:51–59

    Article  MATH  MathSciNet  Google Scholar 

  4. Meyr H (1999) Simultane Losgrößen- und Reihenfolgeplanung fürkontinuierliche Produktionslinien—Modelle und Methodenim Rahmen des Supply Chain Management. Gabler, Wiesbaden

    Book  Google Scholar 

  5. Almada-lobo B, Klabjan D, Carravilla MA, Oliveira JF (2007) Single machine multi-product capacitated lot sizing with sequence-dependent setups. Int J Prod Res 45(20):4873–4894

    Article  MATH  Google Scholar 

  6. Haase, Kimms A (2000) Lot sizing and scheduling with sequence-dependent setup costs and times and efficient rescheduling opportunities. Int J Prod Econ 66(2):159–169

    Article  Google Scholar 

  7. Gopalakrishnan (2000) A modified framework for modeling setup carryover in the capacitated lot-sizing problem. Int J Prod Res 38(14):3421–3424

    Article  MATH  Google Scholar 

  8. Gupta D, Magnusson T (2005) The capacitated lotsizing and scheduling problem with sequence-dependent setup costs and setup times. Comput Oper Res 32:727–747

    Article  MATH  MathSciNet  Google Scholar 

  9. Smith-Daniels VL, Smith-Daniels DE (1986) A mixed integer programming model for lot sizing and sequencing packaging lines in the process industries. IIE Trans 18:278–285

    Article  Google Scholar 

  10. Mohammadi M, Fatemi Ghomi SMT, Karimi B, Torabi SA (2009) MIP-based heuristics for lotsizing in capacitated pure flow shop with sequence-dependent setups. Int J Prod Res 48(10):2957–2973

    Article  Google Scholar 

  11. Porkka, Vepsalainen APJ, Kuula M (2003) Multi period production planning carrying over set-up time. Int J Prod Res 41(6):1133–1148

    Article  MATH  Google Scholar 

  12. Gopalakrishnan D, Miller M, Schmidt CP (1995) A framework for modeling setup carryover in the capacitated lot-sizing problem. Int J Prod Res 33(7):1973–1988

    Article  MATH  Google Scholar 

  13. Sahling F, Buschkühl L, Helber S, Tempelmeier H (2009) Solving a multi-level capacitated lot sizing problem with multi-period setup carry-over via a fix-and-optimize heuristic. Comput Oper Res 36(9):2546–2553

    Article  MATH  Google Scholar 

  14. Quadt D, Kuhn H (2009) Capacitated lot-sizing and scheduling with parallel machines, back-orders, and setup carry-over. naval research logistics, Vol. 56

  15. Wu T, Shi L, Geunes J, Akartunal K (2011) An optimization framework for solving capacitated multi-level lot sizing problems with backlogging. Eur J Oper Res 214(2):428–441

    Article  MATH  Google Scholar 

  16. Pochet Y, Wolsey L (1988) Lot size models with backlogging: strong reformulations and cutting planes. Math Program 40:317–335

    Article  MATH  MathSciNet  Google Scholar 

  17. Millar H, Yang M (1994) Lagrangian heuristics for the capacitated multi-item lot-sizing problem with backordering. Int J Prod Econ 34:1–15

    Article  Google Scholar 

  18. Cheng CH, Madan MS, Gupta Y, So S (2001) Solving the capacitated lot-sizing problem with backorder consideration. J Oper Res Soc 52:952–959

    Article  MATH  Google Scholar 

  19. Karimi B, Fathemi Ghomi SMT, Wilson JM (2006) A tabu search heuristic for solving the CLSP with backlogging and setup carry-over. J Oper Res Soc 57:140–147

    MATH  Google Scholar 

  20. Absi N, KedadSidhoum S (2008) The multi-item capacitated lot-sizing problem with setup times and shortage costs. Eur J Oper Res 185:1351–1374

    Article  MATH  Google Scholar 

  21. Bitran GR, Yanasse HH (1982) Computational complexity of the capacitated lot size problem. Manag Sci 28:1174–1186

    Article  MATH  MathSciNet  Google Scholar 

  22. Maes J, McClain JO, Van Wassenhove LN (1991) Multilevel capacitated lotsizing complexity and LP-based heuristics. Eur J Oper Res 53:131–148

    Article  MATH  Google Scholar 

  23. Kimms A (1999) A genetic algorithm for multi-level, multi-machine lot sizing and scheduling. Comput Oper Res 26:829–848

    Article  MATH  Google Scholar 

  24. Sun H, Huei-Chuen, Jaruphongs HW (2009) Genetic algorithms for the multiple-machine economic lot scheduling problem. Int J Adv Manuf Technol 43:1251–1260

    Article  Google Scholar 

  25. Mohammadi M, Fatemi Ghomi SMT, Karimi B, Torabi SA (2010) Rolling-horizon and fix-and-relax heuristics for the multi-product multi-level capacitated lot sizing problem with sequence-dependent setups. J Intell Manuf 21:501–510

    Article  Google Scholar 

  26. Mohammadi M, Fatemi Ghomi SMT (2011) Genetic algorithm-based heuristic for capacitated lotsizing problem in flow shops with sequence-dependent setups. Expert Syst Appl 38:7201–7207

    Article  Google Scholar 

  27. Aytug H, Khouj M, Vergara FE (2003) Use of genetic algorithms to solve production and operations management problems: a review. Int J Prod Res 41(17):3955–4009

    Article  Google Scholar 

  28. Jans R, Degraeve Z (2007) Meta-heuristics for dynamic lot sizing: a review and comparison of solution approaches. Eur J Oper Res 177(3):1855–1875

    Article  MATH  Google Scholar 

  29. Goren HG, Tunali S, Jans R (2010) A review of applications of genetic algorithms in lot sizing. J Intell Manuf 21(94):575–590

    Article  Google Scholar 

  30. Chen Y-Y, Lin JT (2009) A modified particle swarm optimization for production planning problems in the TFT array process. Expert Syst Appl 36(10):12264–12271

    Article  Google Scholar 

  31. Yamad T, Reeves CR (1998) Solving the Cmax permutation flowshop scheduling problem by genetic local search, in: Proceedings of 1998 I.E. International Conference on Evolutionary Computation, 230–234

  32. Tasgetiren MF, Sevkli M, Liang YC, Gencyilmaz G (2004) Particle swarm optimization algorithm for permutation flowshop sequencing problem, Lecture Notes in Computer Science, vol. 3172, Springer, New York, 382–390

  33. Tasgetiren MF, Sevkli M, Liang Y-C, Gencyilmaz G (2004) Particle swarm optimization algorithm for single machine total weighted tardiness problem, in: Proceedings of the 2004 Congress on Evolutionary Computation (CEC’04), Portland, Oregon, 1412–1419

  34. Tasgetiren MF, Liang Y-C, Sevkli M, Gencyilmaz G (2004) Particle swarm optimization algorithm for makespan and maximum lateness minimization in permutation flowshop sequencing problem, in: Proceedings of the 4th International Symposium on Intelligent Manufacturing Systems (IMS2004), Sakarya, Turkey, 431–441

  35. Tasgetiren MF, Liang Y-C (2003) A binary particle swarm optimization algorithm for lot sizing problem. J Econ Soc Res 5(2):1–20

    Google Scholar 

  36. Han Y, Tang JF, Kaku I, Mu LF (2009) Solving uncapacitated multilevel lot-sizing problem using a particle swarm optimization with flexible inertial weight. Comput Math Appl 57:1748–1755

    Article  MATH  MathSciNet  Google Scholar 

  37. Guo WZ, Chen GL, Huang M, Chen SL (2007) A discrete particle swarm optimization algorithm for the multi-objective permutation flow shop sequencing problem. Proceeding of International Conference on Fuzzy Information and Engineering, pp 323–331

  38. T’kindt V, Monmarche N, Tercinet F, Laugt D (2002) An ant colony optimization algorithm to solve a 2-machine bi-criteria flowshop scheduling problem. Eur J Oper Res 142:250–257

    Article  MATH  MathSciNet  Google Scholar 

  39. Rajendran C, Ziegler H (2004) Ant-colony algorithms for permutation flow shop scheduling to minimize makespan/total flow time of jobs. Eur J Oper Res 155:426–438

    Article  MATH  MathSciNet  Google Scholar 

  40. Marimuthu S, Ponnambalamb SG, Jawahar N (2009) Threshold accepting and ant-colony optimization algorithms for scheduling m-machine flow shops with lot streaming. J Mater Process Technol 209:1026–1041

    Article  Google Scholar 

  41. Huang RH, Yang CL (2009) Solving a multi-objective overlapping flow-shop scheduling. Int J Adv Manuf Technol 42:955–962

    Article  Google Scholar 

  42. Naderi B, Zandieh M, Balagh AKG, Roshanaei V (2009) An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness. Expert Syst Appl 36:9625–9633

    Article  Google Scholar 

  43. Suresh RK, Mohanasundaram KM (2004) Pareto archived simulated annealing for permutation flow shop scheduling with multiple objectives. Proceedings of IEEE Conference on Cybernetics and Intelligent Systems (CIS), vol 2. Singapore, December 1–3, 712–717

  44. Varadharajan TK, Rajendran C (2005) A multi-objective simulated annealing algorithm for scheduling in flowshops to minimize the makespan and total flow time of jobs. Eur J Oper Res 167:772–795

    Article  MATH  MathSciNet  Google Scholar 

  45. Hatami S, Ebrahimnejad S, Tavakkoli-Moghaddam R, Maboudian Y (2010) Two meta-heuristics for three-stage assembly flowshop scheduling with sequence-dependent setup times. Int J Adv Manuf Technol 50:1153–1164

    Article  Google Scholar 

  46. Tavakkoli-Moghaddam R, Rahimi-Vahed A, Mirzaei AH (2008) Solving a multi-objective no-wait flow shop scheduling problem with an immune algorithm. Int J Adv Manuf Technol 36:969–981

    Article  Google Scholar 

  47. Tavakkoli-Moghaddam R, Rahimi-Vahed A, Mirzaei AH (2007) A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: weighted mean completion time and weighted mean tardiness. Inform Sci 177:5072–5090

    Article  MATH  MathSciNet  Google Scholar 

  48. Fandel G, Stammen-Hegene C (2006) Simultaneous lot sizing and scheduling for multi-product multi-level production. Int J Prod Econ 104(2):308–316

    Article  Google Scholar 

  49. Florian M, Lenstra J, Kan AR (1980) Deterministic production planning: algorithms and complexity. Manage Sci 26:669–679

    Article  MATH  Google Scholar 

  50. Holland JH (1992) Adaptation in natural and artificial systems, 2nd edn. University of Michigan Press, Michigan

    Google Scholar 

  51. Mohammadi M, Fatemi Ghomi SMT, Jafari N (2011) A genetic algorithm for simultaneous lot sizing and sequencing of the permutation flow shops with sequence-dependent setups. Int J Comput Integr Manuf 24:87–93

    Article  Google Scholar 

  52. Gen M, Cheng R (1997) Genetic algorithms and engineering design. Wiley, New York

    Google Scholar 

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

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Karaj, Iran

    M. Babaei & M. Mohammadi

  2. Department of Industrial Engineering, Amirkabir University of Technology, Tehran, Iran

    S. M. T. Fatemi Ghomi

Authors
  1. M. Babaei
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. Mohammadi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. S. M. T. Fatemi Ghomi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. Mohammadi.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Babaei, M., Mohammadi, M. & Ghomi, S.M.T.F. A genetic algorithm for the simultaneous lot sizing and scheduling problem in capacitated flow shop with complex setups and backlogging. Int J Adv Manuf Technol 70, 125–134 (2014). https://doi.org/10.1007/s00170-013-5252-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00170-013-5252-y

Keywords

Search

Navigation