Capacitated lot-sizing and production sequence problem with setups complexity

Document Type : 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, Hafez Avenue, 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 it was converted to a mixed-integer linear program. To solve large-size instances of the problem, first, 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 multi-level, multi-period and multi-item capacitated lot-sizing problem is NP-hard and adding other factors such as family setups, setup carry over and sequence-dependent setups increases its complexity, in this paper, a genetic algorithm 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 genetic algorithm and lower bound, and, so, the genetic algorithm had been able to approach the optimal solution.

Keywords

References

References

[1] Allahverdi, A. Ng, C.T. Cheng, T.C.E. and Kovalyov, M.Y. “A survey of scheduling problems with setup times or costs” European Journal of Operational Research, 187(3), pp. 985–1032 (2008).
[2] Almada-Lobo, B., Klabjan, D., Carravilla, M.A. et al. “Single machine multi-product capacitated lot sizing with sequence-dependent setups” International Journal of Production Research, 45(20), pp. 4873-4894 (2007).
[3] Jin, F. Dong, S. and Wu, C. “A simulated annealing algorithm for single machine scheduling problems with family setups. Computers & Operations Research, 36(7), pp. 2133-2138 (2009).
[4] Poursabzi, O. Mohammadi, M. and Naderi, B. “An improved model and a heuristic for capacitated lot sizing and scheduling in job shop problems” Scientia Iranica, 25(6), pp. 3667-3684 (2018).
 [5] Sahling, F., Buschkühl, L., Tempelmeier, H. et al. “Solving a multi-level capacitated lot sizing problem with multi-period setup carry-over via a fix-and-optimize heuristic” Computers & Operations Research, 36(9), pp. 2546–2553 (2009).
[6] Carvalho, D.M. and Nascimento, M.C.V. “A kernel search to the multi-plant capacitated lot sizing problem with setup carry-over” Computers & Operations Research, 100, pp. 43-53 (2018).
[7] Florian, M. Lenstra, J. K. and Rinnooy Kan, A.H.G. “Deterministic production planning algorithms and complexity” Management Science, 26(7), pp. 669-679 (1980).
[8] Bitran, G. R. and Yanasse, H. H. “Computational complexity of the capacitated lot size problem” Management Science, 28(10), pp. 1174-1186 (1982).
[9] Chen W. H. and Thizy, J. M. “Analysis of relaxations for the multi-item capacitated lot-sizing problem” Annals of Operations Research, 26, pp. 29-72 (1990).
[10] Baldo, T.A., Santos, M.O., Almada-Lobo, B. et al. “An optimization approach for the lot sizing and scheduling problem in the brewery industry” Computers & Industrial Engineering, 72, pp. 58-71 (2014).
[11] Gicquel, C. and Minoux, M. “Multi-product valid inequalities for the discrete lot-sizing and scheduling problem” Computers & Operations Research, 54, pp. 12-20 (2015).
[12] Boonmee, A. and Sethanan K. “A GLNPSO for multi-level capacitated lot-sizing and scheduling problem in the poultry industry” European Journal of Operational Research, 250(216), pp. 652-665 (2016).
[13] Ceschia, S. Di Gaspero, L. and Schaerf, A. “Solving discrete lot-sizing and scheduling by simulated annealing and mixed integer programming” Computers & Industrial Engineering, 114, pp. 235-243 (2017).
[14] Curcio, E., Amorim, P., Zhang, Q. et al. “Adaptation and approximate strategies for solving the lot-sizing and scheduling problem under multistage demand uncertainty” International Journal of Production Economics, 202, pp. 81-96 (2018).
[15] Wichmann, M.G. Johannes, C. and Spengler, T.S. “An extension of the general lot-sizing and scheduling problem (GLSP) with time-dependent energy prices” Journal of Business Economics, 89, pp. 481–514 (2019).
[16] Toscano, A. Ferreira, D. and Morabito, R. “A decomposition heuristic to solve the two-stage lot sizing and scheduling problem with temporal cleaning” Flexible Services and Manufacturing Journal, 31, pp. 142–173 (2019).
[17] Kaczmarczyk, W. “Valid inequalities for proportional lot-sizing and scheduling problem with fictitious microperiods” International Journal of Production Economics, 219, pp. 236-247 (2020).
[18] Hu, Z. and Hu, G. “Hybrid stochastic and robust optimization model for lot-sizing and scheduling problems under uncertainties” European Journal of Operational Research, 284(216), pp. 485-497 (2020).
[19] Mohammadi, M. “Designing an integrated reliable model for stochastic lot-sizing and scheduling problem in hazardous materials supply chain under disruption and demand uncertainty” Journal of Cleaner Production, 2020, pp. 122621 (2021).
[20] Chen, Z. and Zhang, R. “A capital Flow-constrained lot-sizing problem with trade credit” Scientia Iranica, 25(5), 2775-2787 (2018).
[21 Cheng, Y., Wang, W., Wei, C. et al. “An integrated lot-sizing model for imperfect production with multiple disposals of defective items” Scientia Iranica, 25(2), pp. 852-867 (2018).
[22] Stadtler, H. and Meistering, M. “Model formulations for the capacitated lot-sizing problem with service-level constraints” OR Spectrum, 41, pp. 1025–1056 (2019).
[23] Abrishami, S. Vahdani, H. and Rezaee, B. “An integrated lot-sizing model with supplier and carrier selection and quantity discounts considering multiple products” Scientia Iranica, 27(4), pp. 2140-2156 (2020).
[24] Slama, I., Ben-Ammar, O., Dolgui, A. et al. “Genetic algorithm and Monte Carlo simulation for a stochastic capacitated disassembly lot-sizing problem under random lead times” Computers & Industrial Engineering, 159, pp. 107468 (2021).
[25] Li, Y. Saldanha-da-Gama, F. Liu, M. et al. “A risk-averse two-stage stochastic programming model for a joint multi-item capacitated line balancing and lot-sizing problem” European Journal of Operational Research, Doi: 10.1016/j.ejor.2021.09.043 (2022).
[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” Computers & Operations Research, 134, pp. 105373 (2021).
[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-part injection moulding” Applied Mathematical Modelling, 100, pp. 805-820 (2021).
[28] Koch, C., Arbaoui, T., Ouazene, Y. et al. “Capacitated multi-item lot sizing problem with client prioritization in tire industry” IFAC-PapersOnLine, 54(1), pp. 564-569 (2021).
[29] Gansterer, M. and Födermayr, P. and Hartl, R.F. “The capacitated multi-level lot-sizing problem with distributed agents” International Journal of Production Economics, 235, pp. 108090 (2021).
[30] Rezaei, S. and Behnamian, J. “Single-item lot-based supplying and batch production under a bilateral capacity reservation: A partnership structure” RAIRO - Operations Research, 55 (2021), pp. 2633-2652 (2021).
[31] Mohammadi, M. and Fatemi Ghomi, S.M.T. “Genetic algorithm-based heuristic for capacitated lot sizing problem in flow shops with sequence-dependent setups” Expert Systems with Applications, 38, pp. 7201–7207 (2011).
[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 problem with uncertainty in levels” International Journal of Production Research, 55(18), pp. 5330-5340 (2017).
[33] Behnamian, J., Fatemi Ghomi, S.M.T., Jolai, F. et al. “Realistic two-stage flowshop batch scheduling problems with transportation capacity and time” Applied Mathematical Modelling, 36, pp. 723–735 (2012).
[34] Jans, R. and Degraeve, Z. “Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches” European Journal of Operation Research, 177(3), pp.1851-1875 (2007).
[35] Swan, J., Adriaensen, S., Brownlee, A.E.I. et al. “Metaheuristics “In the Large”” European Journal of Operational Research, 297(2), pp. 393-406 (2022).
[36] Behnamian, J., Fatemi Ghomi, S.M.T., Jolai, F. et al. “Minimizing makespan on a three-machine flowshop batch scheduling problem with transportation using genetic algorithm” Applied soft computing, 12, pp. 768-777 (2012).
[37] Gen, M. and Cheng, R. “Genetic Algorithms and Engineering Designs”. 1th ed. New York: Wiley (1997).
[38] Reeves, C.R. “A genetic algorithm for flow shop sequencing” Computer & Operation Research, 22(1), pp. 5-13 (1995).
[39] Mohammadi, M., Fatemi Ghomi, S. M. T., Karimi, B. et al. “Rolling horizon and fix-and-relax heuristics for the multi-product multi-level capacitated lot sizing problem with sequence-dependent setups” Journal of Intelligent Manufacturing, 21, pp. 501–510 (2010).
Scientia Iranica

Articles in Press, Accepted Manuscript
Available Online from 23 January 2022

Files

Share

How to cite

Statistics