Exact methods for the parallel machines scheduling problem with identical machines, controllable processing times, and resource consumption
DOI:
https://doi.org/10.5540/03.2025.011.01.0393Keywords:
Production sequencing, sustainable manufacturing, green scheduling, combinatorial optimizationAbstract
This paper aims to introduce a new variant of the identical parallel machines scheduling problem with controllable processing times and resource consumption. The performance measure is the minimization of makespan. We developed a mixed-integer linear programming (MILP) formulation and a constraint programming (CP) model. We conducted computational experiments using 2250 randomly generated test instances. The extensive computational experience of tested methods shows that the MILP model is promising for solving small-sized instances, and the CP model got the best average relative deviation and superior performance in large-sized instances.
Downloads
References
L. R. de Abreu, K. A. G. Araújo, B. A. de Prata, M. S. Nagano, and J. V. Moccellin. “A new variable neighbourhood search with a constraint programming search strategy for the open shop scheduling problem with operation repetitions”. In: Engineering Optimization 54.9 (2022), pp. 1563–1582. doi: 10.1080/0305215X.2021.1957101.
L. R. Abreu, B. A. Prata, M. S. Nagano, and J. M. Framinan. “A constraint programming-based iterated greedy algorithm for the open shop with sequence-dependent processing times and makespan minimization”. In: Computers & Operations Research 160 (2023), p. 106386. doi: 10.1016/j.cor.2023.106386.
M. Dell’Amico and S. Martello. “Optimal scheduling of tasks on identical parallel processors”. In: ORSA Journal on Computing 7.2 (1995), pp. 191–200. doi: 10.1287/ijoc.7.2.191.
K. T. Fang and B. M. T. Lin. “Parallel-machine scheduling to minimize tardiness penalty and power cost”. In: Computers & Industrial Engineering 64.1 (2013), pp. 224–234. doi: 10.1016/j.cie.2012.10.002.
V. Fernandez-Viagas and J. M. Framinan. “Controllable processing times in project and production management: Analysing the trade-off between processing times and the amount of resources”. In: Mathematical Problems in Engineering 2015 (2015). doi: 10.1155/2015/826318.
V. Kayvanfar, G. H. M. Komaki, A. Aalaei, and M. Zandieh. “Minimizing total tardiness and earliness on unrelated parallel machines with controllable processing times”. In: Computers & Operations Research 41 (2014), pp. 31–43. doi: 10.1016/j.cor.2013.08.003.
P. Laborie. “An update on the comparison of MIP, CP and hybrid approaches for mixed resource allocation and scheduling”. In: International conference on the integration of constraint programming, artificial intelligence, and operations research. Springer. 2018, pp. 403–411. doi: 10.1007/978-3-319-93031-2_29.
E. Mokotoff. “An exact algorithm for the identical parallel machine scheduling problem”. In: European Journal of Operational Research 152.3 (2004), pp. 758–769. doi: 10.1016/S0377-2217(02)00726-9.
B. A. Prata, L. R. de Abreu, and J. Y. F. Lima. “Heuristic methods for the single-machine scheduling problem with periodical resource constraints”. In: Top 29.2 (2021), pp. 524–546. doi: 10.1007/s11750-020-00574-x.
B. A. Prata, L. R. Abreu, and M. S. Nagano. “Applications of constraint programming in production scheduling problems: A descriptive bibliometric analysis”. In: Results in Control and Optimization 14 (2024), p. 100350. doi: 10.1016/j.rico.2023.100350.
B. A. Prata, V. Fernandez-Viagas, J. M. Framinan, and C. D. Rodrigues. “Matheuristics for the flowshop scheduling problem with controllable processing times and limited resource consumption to minimize total tardiness”. In: Computers & Operations Research 145 (2022), p. 105880. doi: 10.1016/j.cor.2022.105880.
D. Shabtay and G. Steiner. “A survey of scheduling with controllable processing times”. In: Discrete Applied Mathematics 155.13 (2007), pp. 1643–1666. doi: 10.1016/j.dam.2007.02.003.
