Heuristic Algorithm for Lot Sizing and Scheduling on Identical Parallel Machines
DOI:
https://doi.org/10.7494/dmms.2022.16.4105Keywords:
lot sizing, lot scheduling, identical parallel machines, heuristics, algorithmAbstract
This paper presents a new heuristic algorithm for the task of lot sizing and scheduling for identical parallel machines. The new algorithm is based on the rolling-horizon approach and the fix-and-relax decomposition technique. Two variants of the algorithm are finally proposed for solving the problem of lot scheduling with parallel machines where the number of products and machines is greater than that of the machines. A computational experiment has been conducted for a group of 30 data sets. The results showed that the new algorithm efficiently provided good solutions for tasks with large numbers of machines and products.
References
Beraldi P., Ghiani G., Grieco A. & Guerriero E. (2008). Rolling-horizon and fix-and-relax heuristics for the parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs. Computers & Operations Research, 35(11), pp. 3644–3656. DOI: https://doi.org/10.1016/j.cor.2007.04.003.
Gurobi Optimization, LLC (2022). Gurobi Optimizer. URL: https://www.gurobi.com/product [11.12.2022].
Haase K. (1994). Lotsizing and Scheduling for Production Planning. Lecture Notes in Economics and Mathematical Systems, vol. 408. Berlin–Heidelberg: Springer-Verlag. DOI: https://doi.org/10.1007/978-3-642-45735-7.
Jans R.F. & Degraeve Z. (2008). Modeling industrial lot sizing problems: A review. International Journal of Production Research, 46(6), pp. 1619–1643. DOI: https://doi.org/10.1080/00207540600902262.
Kaczmarczyk W. (2006). Modele PLC planowania wielkości i szeregowania partii z identycznymi liniami równoległymi. Zeszyty Naukowe Politechniki Śląskiej. Seria Automatyka, 144, pp. 23–32. URL: https://delibra.bg.polsl.pl/dlibra/publication/49935/edition/45722.
Kaczmarczyk W. (2011). Proportional lot-sizing and scheduling problem with identical parallel machines. International Journal of Production Research, 49(9), pp. 2605–2623. DOI: https://doi.org/10.1080/00207543.2010.532929.
Kimms A. & Drexl A. (1998). Some insights into proportional lot sizing and scheduling. Journal of the Operational Research Society, 49(11), pp. 1196–1205. DOI: https://doi.org/10.2307/3010100.
Lasdon L.S. & Terjung R.C. (1971). An efficient algorithm for multi-item scheduling. Operations Research, 19(4), pp. 946–969. DOI: https://doi.org/10.1287/opre.19.4.946.
Mehdizadeh E., Tavakkoli-Moghaddam R. & Yazdani M. (2015). A vibration damping optimization algorithm for a parallel machines scheduling problem with sequence-independent family setup times. Applied Mathematical Modelling, 39(22), pp. 6845–6859. DOI: https://doi.org/10.1016/j.apm.2015.02.027.
Mensendiek A., Gupta J.N.D. & Herrmann J. (2015). Scheduling identical parallel machines with fixed delivery dates to minimize total tardiness. European Journal of Operational Research, 243(2), pp. 514–522. DOI: https://doi.org/10.1016/j.ejor.2014.12.002.
Miodońska B. (2006). Koordynacja w łańcuchach dostaw [Master’s thesis]. Kraków: AGH University of Science and Technology.
Pochet Y. & Wolsey L.A. (2006). Production Planning by Mixed Integer Programming. Springer Series in Operations Research and Financial Engineering. New York: Springer. DOI: https://doi.org/10.1007/0-387-33477-7.
PyPy Project (2022). PyPy. URL: https://pypy.org/ [12.11.2022].
