Capacitated lot-sizing and production sequence problem with setups complexity

Document Type : Research Article

Authors

1 Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran

2 Department of Industrial Engineering, Amirkabir University of Technology, 15916-34311, Tehran, Iran

Abstract

This paper considered the multi-product multi-level multi-period capacitated lot-sizing and sequencing problem with setup carry-over and sequence-dependent family setup times and costs. A formulation of the problem was provided as a mixed-integer nonlinear programming model. To propose this formulation, first, the mixed-integer nonlinear of the problem was linearized, and then converted to a mixed-integer linear program. To solve large-size instances of the problem, then, a lower bound was provided. The results confirmed the efficiency of the proposed model compared to previous models in terms of the runtime and the number of defined variables and constraints. Since this problem is NP-hard and adding other factors such as family setups, setup carry over and sequence-dependent setups increase its complexity, in this paper, a Genetic Algorithm (GA) was applied in large-size dimensions and its results were compared with the proposed lower bound. The numerical results showed that there is no significant difference between the results of the proposed GA and lower bound, and, so, the GA had been
able to approach the optimal solution.

Keywords

References

References:
1.Allahverdi, A., Ng, C.T., Cheng, T.C.E., et al. “A survey of scheduling problems with setup times orcosts”, European Journal of Operational Research,187(3), pp. 985–1032 (2008).https://doi.org/10.1016/j.ejor.2006.06.060.
2.Almada-Lobo, B., Klabjan, D., Carravilla, M.A., etal. “Single machine multi-product capacitated lotsizing with sequence-dependent setups”International Journal of Production Research,45(20), pp. 4873-4894 (2007). https://doi.org/10.1080/00207540601094465.
3.Jin, F., Dong, S., and Wu, C. “A simulatedannealing algorithm for single machine schedulingproblems with family setups’’, Computers andOperations Research, 36(7), pp. 2133-2138 (2009).https://doi.org/10.1016/j.cor.2008.08.001.
4.Poursabzi, O., Mohammadi, M., and Naderi, B. “An improved model and a heuristic for capacitated lotsizing and scheduling in job shop problems”,Scientia Iranica, 25(6), pp. 3667-3684 (2018).https://doi.org/10.24200/sci.2017.20016.
5.Sahling, F., Buschkühl, L., Tempelmeier, H., et al.“Solving a multi-level capacitated lot sizingproblem with multi-period setup carry-over via afix-and-optimize heuristic”, Computers andOperations Research, 36(9), pp. 2546–2553 (2009). https://doi.org/10.1016/j.cor.2008.10.009.
6.Carvalho, D.M. and Nascimento, M.C.V. “A kernelsearch to the multi-plant capacitated lot sizingproblem with setup carry-over”, Computers &Operations Research, 100, pp. 43-53 (2018).https://doi.org/10.1016/j.cor.2018.07.008.
7.Florian, M., Lenstra, J.K., and Rinnooy Kan,A.H.G. “Deterministic production planningalgorithms and complexity”, Management Science,26(7), pp. 669-679 (1980). https://doi.org/10.1287/mnsc.26.7.669.
8.Bitran, G.R. and Yanasse, H.H. “Computationalcomplexity of the capacitated lot size problem”,Management Science, 28(10), pp. 1174-1186(1982). https://doi.org/10.1287/mnsc.28.10.1174.
9.Chen, W.H. and Thizy, J.M. “Analysis ofrelaxations for the multi-item capacitated lot-sizing problem”, Annals of Operations Research, 26, pp. 29-72 (1990). https://doi.org/10.1007/BF02248584.
10.Baldo, T.A., Santos, M.O., Almada-Lobo, B., et al.“An optimization approach for the lot sizing andscheduling problem in the brewery industry”,Computers and Industrial Engineering, 72, pp. 58-71 (2014). https://doi.org/10.1016/j.cie.2014.02.008.
11.Gicquel, C. and Minoux, M. “Multi-product validinequalities for the discrete lot-sizing andscheduling problem”, Computers and OperationsResearch, 54, pp. 12-20 (2015). https://doi.org/10.1016/j.cor.2014.08.022.
12.Boonmee, A. and Sethanan, K. “A GLNPSO formulti-level capacitated lot-sizing and schedulingproblem in the poultry industry”, European Journalof Operational Research, 250(216), pp. 652-665(2016). https://doi.org/10.1016/j.ejor.2015.09.020.
13.Ceschia, S., Di Gaspero, L., and Schaerf, A. “Solvingdiscrete lot-sizing and scheduling by simulatedannealing and mixed integer programming”,Computers and Industrial Engineering, 114, pp. 235-243 (2017). https://doi.org/10.1016/j.cie.2017.10.017.
14.Curcio, E., Amorim, P., Zhang, Q., et al.“Adaptation and approximate strategies for solvingthe lot-sizing and scheduling problem undermultistage demand uncertainty”, InternationalJournal of Production Economics, 202, pp. 81-96(2018). https://doi.org/10.1016/j.ijpe.2018.04.012.
15.Wichmann, M.G., Johannes, C., and Spengler, T.S.“An extension of the general lot-sizing andscheduling problem (GLSP) with time-dependentenergy prices”, Journal of Business Economics, 89,pp. 481–514 (2019). https://doi.org/10.1007/s11573-018-0921-9.
16.Toscano, A., Ferreira, D., and Morabito, R. “Adecomposition heuristic to solve the two-stage lotsizing and scheduling problem with temporalcleaning”, Flexible Services and ManufacturingJournal, 31, pp. 142–173 (2019). https://doi.org/10.1007/s10696-017-9303-9.
17.Kaczmarczyk, W. “Valid inequalities forproportional lot-sizing and scheduling problemwith fictitious microperiods”, International Journal of Production Economics, 219, pp. 236-247 (2020). https://doi.org/10.1016/j.ijpe.2019.06.005.
18.Hu, Z. and Hu, G. “Hybrid stochastic and robustoptimization model for lot-sizing and schedulingproblems under uncertainties”, European Journalof Operational Research, 284(216), pp. 485-497(2020). https://doi.org/10.1016/j.ejor.2019.12.030.
19.Mohammadi, M. “Designing an integrated reliablemodel for stochastic lot-sizing and schedulingproblem in hazardous materials supply chain underdisruption and demand uncertainty”, Journal ofCleaner Production, 2020, 122621 (2021).https://doi.org/10.1016/j.jclepro.2020.122621.
20.Chen, Z. and Zhang, R. “A capital flow-constrainedlot-sizing problem with trade credit”, ScientiaIranica, 25(5), pp. 2775-2787 (2018).https://doi.org/10.24200/sci.2017.4444.
21.Cheng, Y., Wang, W., Wei, C., et al. “An integratedlot-sizing model for imperfect production withmultiple disposals of defective items”, ScientiaIranica, 25(2), pp. 852-867 (2018). https://doi.org/10.24200/sci.2017.4414.
22.Stadtler, H. and Meistering, M. “Modelformulations for the capacitated lot-sizing problemwith service-level constraints”, OR Spectrum, 41,pp. 1025–1056 (2019). https://doi.org/10.1007/s00291-019-00552-1.
23.Abrishami, S., Vahdani, H., and Rezaee, B. “Anintegrated lot-sizing model with supplier and carrier selection and quantity discounts consideringmultiple products”, Scientia Iranica, 27(4), pp.2140-2156 (2020). https://doi.org/10.24200/sci.2019.5155.1125.
24.Slama, I., Ben-Ammar, O., Dolgui, A., et al.“Genetic algorithm and Monte Carlo simulation fora stochastic capacitated disassembly lot-sizingproblem under random lead times”, Computers andIndustrial Engineering, 159, 107468 (2021).https://doi.org/10.1016/j.cie.2021.107468.
25.Li, Y., Saldanha-da-Gama, F., Liu, M., et al. “A risk-averse two-stage stochastic programming model for ajoint multi-item capacitated line balancing and lot-sizing problem”, European Journal of OperationalResearch, 304(1), pp. 353-365 (2023). https://doi.org/10.1016/j.ejor.2021.09.043.
26.Malekian, Y., Mirmohammadi, S.H., and Bijari, M.“Polynomial-time algorithms to solve the single-item capacitated lot sizing problem with a 1-breakpoint all-units quantity discount”, Computersand Operations Research, 134, 105373 (2021).https://doi.org/10.1016/j.cor.2021.105373.
27.Mula, J., Díaz-Madroñero, M., Andres, B., et al. “A capacitated lot-sizing model with sequence-dependent setups, parallel machines and bi-partinjection moulding”, Applied Mathematical Modelling, 100, pp. 805-820 (2021). https://doi.org/10.1016/j.apm.2021.07.028.
28.Koch, C., Arbaoui, T., Ouazene, Y., et al. “Capacitated multi-item lot sizing problem with OnLine, 54(1), pp. 564-569 (2021). https://doi.org/10.1016/j.ifacol.2021.08.064.
29.Gansterer, M., Födermayr, P., and Hartl, R.F. “Thecapacitated multi-level lot-sizing problem withdistributed agents”, International Journal ofProduction Economics, 235, 108090 (2021).https://doi.org/10.1016/j.ijpe.2021.108090.
30.Rezaei, S. and Behnamian, J. “Single-item lot-based supplying and batch production under abilateral capacity reservation: A partnershipstructure”, RAIRO-Operations Research, 55(2021), pp. 2633-2652 (2021). https://doi.org/10.1051/ro/2020099.
31.Mohammadi, M. and Fatemi Ghomi, S.M.T.“Genetic algorithm-based heuristic for capacitatedlot sizing problem in flow shops with sequence-dependent setups”, Expert Systems withApplications, 38, pp. 7201–7207 (2011). https://doi.org/10.1016/j.eswa.2010.12.038.
32.Behnamian, J., Fatemi Ghomi, S.M.T., Karimi, B.et al. “A Markovian approach for multi-level multi-product multi-period capacitated lot-sizing problemwith uncertainty in levels”, International Journal ofProduction Research, 55(18), pp. 5330-5340(2017). https://doi.org/10.1080/00207543.2017.1311048.
33.Behnamian, J., Fatemi Ghomi, S.M.T., Jolai, F., etal. “Realistic two-stage flowshop batch schedulingproblems with transportation capacity and time”,Applied Mathematical Modelling, 36, pp. 723–735(2012). https://doi.org/10.1016/j.apm.2011.07.011.
34.Jans, R. and Degraeve, Z. “Meta-heuristics fordynamic lot sizing: A review and comparison ofsolution approaches”, European Journal ofOperation Research, 177(3), pp.1851-1875 (2007).https://doi.org/10.1016/j.ejor.2005.12.008.
35.Swan, J., Adriaensen, S., Brownlee, A.E.I., et al.“Metaheuristics `In the Large’, European Journalof Operational Research, 297(2), pp. 393-406(2022). https://doi.org/10.1016/j.ejor.2021.05.042.
36.Behnamian, J., Fatemi Ghomi, S.M.T., Jolai, F., etal. “Minimizing makespan on a three-machineflowshop batch scheduling problem withtransportation using genetic algorithm”, AppliedSoft Computing, 12, pp. 768-777 (2012).https://doi.org/10.1016/j.asoc.2011.10.015.
37.Gen, M. and Cheng, R., Genetic Algorithms andEngineering Designs, 1st. Ed., New York: Wiley(1997).
38.Reeves, C.R. “A genetic algorithm for flow shopsequencing”, Computer and Operation Research,22(1), pp. 5-13 (1995).
https://doi.org/10.1016/0305-0548(93)E0014-K.
39.Mohammadi, M., Fatemi Ghomi, S.M.T., Karimi,B., et al. “Rolling horizon and fix-and-relaxheuristics for the multi-product multi-levelcapacitated lot sizing problem with sequence-dependent setups”, Journal of IntelligentManufacturing, 21, pp. 501–510 (2010).https://doi.org/10.1007/s10845-008-0207-0.
Scientia Iranica
Volume 32, Issue 4
Transactions on Industrial Engineering
January and February 2025 Article ID:5025

Files

History

  • Receive Date: 04 November 2020
  • Revise Date: 13 December 2021
  • Accept Date: 24 January 2022

Share

How to cite

Statistics