A reinforcement learning iterated local search for makespan minimization in additive manufacturing machine scheduling problems. (English) Zbl 07485278

Summary: Additive manufacturing – also known as 3D printing – is a manufacturing process that is attracting more and more interest due to high production rates and reduced costs. This paper focuses on the scheduling problem of multiple additive manufacturing machines, recently proposed in the scientific literature. Given its intractability, instances of relevant size of additive manufacturing (AM) machine scheduling problem cannot be solved in reasonable computational times through mathematical models. For this reason, this paper proposes a Reinforcement Learning Iterated Local Search meta-heuristic, based on the implementation of a Q-Learning Variable Neighborhood Search, to provide heuristically good solutions at the cost of low computational expenses. A comprehensive computational study is conducted, comparing the proposed methodology with the results achieved by the CPLEX solver and to the performance of an Evolutionary Algorithm recently proposed for a similar problem, and adapted for the AM machine scheduling problem. Additionally, to explore the trade-off between efficiency and effectiveness more deeply, we present a further set of experiments that test the potential inclusion of a probabilistic stopping rule. The numerical results evidence that the proposed Reinforcement Learning Iterated Local Search is able to obtain statistically significant improvements compared to the other solution approaches featured in the computational experiments.


90Bxx Operations research and management science


CPLEX; ilsts-wvcp; irace
Full Text: DOI


[1] Alvarez Fernandez, S.; Ferone, D.; Juan, A. A.; Silva, D. G.; de Armas, J., A 2-stage biased-randomized iterated local search for the uncapacitated single allocation p-hub median problem, Transactions on Emerging Telecommunications Technologies, 29, Article e3418 pp. (2018)
[2] Alvarez Fernandez, S.; Ferone, D.; Juan, A. A.; Tarchi, D., A simheuristic algorithm for video streaming flows optimisation with QoS threshold modelled as a stochastic single-allocation p-hub median problem, Journal of Simulation (2021)
[3] Arroyo, J. E.C.; Leung, J. Y.T., An effective iterated greedy algorithm for scheduling unrelated parallel batch machines with non-identical capacities and unequal ready times, Computers & Industrial Engineering, 105, 84-100 (2017)
[4] Arroyo, J. E.C.; Leung, J. Y.T., Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times, Computers & Operations Research, 78, 117-128 (2017) · Zbl 1391.90236
[5] Asprone, D.; Auricchio, F.; Menna, C.; Mercuri, V., 3d printing of reinforced concrete elements: technology and design approach, Construction and Building Materials, 165, 218-231 (2018)
[6] Bougeret, M.; Dutot, P. F.; Jansen, K.; Otte, C.; Trystram, D., Approximation algorithms for multiple strip packing, (Approximation and Online Algorithms (2010), Springer: Springer Berlin Heidelberg), 37-48 · Zbl 1284.68657
[7] Bougeret, M.; Dutot, P. F.; Jansen, K.; Robenek, C.; Trystram, D., Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms, Discrete Mathematics, Algorithms and Applications, 03, 553-586 (2011) · Zbl 1253.68356
[8] Bremen, S.; Meiners, W.; Diatlov, A., Selective laser melting, Laser Technik Journal, 9, 33-38 (2012)
[9] Chang, P.Y., Damodaran*, P., Melouk, S., 2004. Minimizing makespan on parallel batch processing machines. International Journal of Production Research 42, 4211-4220.
[10] Cheng, B.; Yang, S.; Hu, X.; Chen, B., Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes, Applied Mathematical Modelling, 36, 3161-3167 (2012) · Zbl 1252.90022
[11] Chergui, A.; Hadj-Hamou, K.; Vignat, F., Production scheduling and nesting in additive manufacturing, Computers & Industrial Engineering, 126, 292-301 (2018), URL: http://www.sciencedirect.com/science/article/pii/S0360835218304649
[12] Coykendall, J., Cotteleer, M., Holdowsky, J., Mahto, M., 2014. 3d opportunity in aerospace and defense: Additive manufacturing takes flight. A Deloitte series on additive manufacturing 1.
[13] Dilberoglu, U. M.; Gharehpapagh, B.; Yaman, U.; Dolen, M., The role of additive manufacturing in the era of industry 4.0, Procedia Manufacturing, 11, 545-554 (2017)
[14] Felici, G.; Ferone, D.; Festa, P.; Napoletano, A.; Pastore, T., A GRASP for the Minimum Cost SAT Problem, (Battiti, R.; Kvasov, D. E.; Sergeyev, Y. D., Learning and Intelligent Optimization. LION 2017 (2017), Springer International Publishing: Springer International Publishing Cham), 64-78
[15] Fera, M.; Fruggiero, F.; Lambiase, A.; Macchiaroli, R.; Todisco, V., A modified genetic algorithm for time and cost optimization of an additive manufacturing single-machine scheduling, International Journal of Industrial Engineering Computations, 423-438 (2018)
[16] Ferone, D.; Festa, P.; Gruler, A.; Juan, A. A., Combining simulation with a GRASP metaheuristic for solving the permutation flow-shop problem with stochastic processing times, (2016 Winter Simulation Conference (WSC) (2016), IEEE), 2205-2215
[17] Ferone, D.; Hatami, S.; GonzálezáNeira, E. M.; Juan, A. A.; Festa, P., A biased-randomized iterated local search for the distributed assembly permutation flow-shop problem, International Transactions in Operational Research (2019)
[18] Festa, P., Pastore, T., Ferone, D., Juan, A.A., Bayliss, C., 2019. Integrating biased-randomized GRASP with Monte Carlo simulation for solving the vehicle routing problem with stochastic demands. In: Proceedings - Winter Simulation Conference 2018-Decem, pp. 2989-3000. doi: 10.1109/WSC.2018.8632348.
[19] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences) (1979), Freeman: Freeman W. H
[20] Griffiths, V.; Scanlan, J. P.; Eres, M. H.; Martinez-Sykora, A.; Chinchapatnam, P., Cost-driven build orientation and bin packing of parts in selective laser melting (slm), European Journal of Operational Research, 273, 334-352 (2019)
[21] Han, X.; Iwama, K.; Ye, D.; Zhang, G., Strip packing vs. bin packing, (Algorithmic Aspects in Information and Management (2007), Springer: Springer Berlin Heidelberg), 358-367 · Zbl 1137.90648
[22] Ikura, Y.; Gimple, M., Efficient scheduling algorithms for a single batch processing machine, Operations Research Letters, 5, 61-65 (1986) · Zbl 0594.90045
[23] Jansen, K.; Rau, M., Improved approximation for two dimensional strip packing with polynomial bounded width, (WALCOM: Algorithms and Computation (2017), Springer International Publishing), 409-420 · Zbl 1427.68368
[24] Jia, Z.h., Leung, J.Y.T., 2015. A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes. European Journal of Operational Research 240, 649-665. · Zbl 1338.90167
[25] Jia, Z.h., Li, K., Leung, J.Y.T., 2015. Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities. International Journal of Production Economics 169, 1-10.
[26] Jia, Z.h., Zhang, H., Long, W.t., Leung, J.Y., Li, K., Li, W., 2018. A meta-heuristic for minimizing total weighted flow time on parallel batch machines. Computers & Industrial Engineering 125, 298-308.
[27] Johnson, D. S.; Demers, A.; Ullman, J. D.; Garey, M. R.; Graham, R. L., Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM Journal on Computing, 3, 299-325 (1974) · Zbl 0297.68028
[28] Koh, S. G.; Koo, P. H.; Ha, J. W.; Lee, W. S., Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families, International Journal of Production Research, 42, 4091-4107 (2004) · Zbl 1060.90643
[29] Kucukkoc, I., MILP models to minimise makespan in additive manufacturing machine scheduling problems, Computers & Operations Research, 105, 58-67 (2019) · Zbl 1458.90315
[30] Leary, M., 2017. Surface roughness optimisation for selective laser melting (SLM). In: Laser Additive Manufacturing, Elsevier, pp. 99-118. doi: 10.1016/b978-0-08-100433-3.00004-x.
[31] Li, X.; Huang, Y.; Tan, Q.; Chen, H., Scheduling unrelated parallel batch processing machines with non-identical job sizes, Computers & Operations Research, 40, 2983-2990 (2013) · Zbl 1348.90285
[32] Li, K., Jia, Z.h., Leung, J.Y.T., 2015. Integrated production and delivery on parallel batching machines. European Journal of Operational Research 247, 755-763. · Zbl 1346.90366
[33] Li, Q.; Kucukkoc, I.; Zhang, D. Z., Production planning in additive manufacturing and 3d printing, Computers & Operations Research, 83, 157-172 (2017)
[34] Li, Q.; Zhang, D.; Kucukkoc, I., Order acceptance and scheduling in direct digital manufacturing with additive manufacturing, IFAC-PapersOnLine, 52, 1016-1021 (2019)
[35] Li, Q.; Zhang, D.; Wang, S.; Kucukkoc, I., A dynamic order acceptance and scheduling approach for additive manufacturing on-demand production, The International Journal of Advanced Manufacturing Technology, 105, 3711-3729 (2019)
[36] López-Ibáñez, M.; Dubois-Lacoste, J.; Cáceres, L. P.; Birattari, M.; Stützle, T., The irace package: Iterated racing for automatic algorithm configuration, Operations Research Perspectives, 3, 43-58 (2016)
[37] Lourenço, H. R.; Martin, O. C.; Stützle, T., Iterated local search: framework and applications, (Handbook of Metaheuristics (2019), Springer), 129-168
[38] Martello, S.; Toth, P., Knapsack Problems: Algorithms and Computer Implementations (1990), John Wiley & Sons Inc. · Zbl 0708.68002
[39] Martello, S.; Monaci, M.; Vigo, D., An exact approach to the strip-packing problem, INFORMS Journal on Computing, 15, 310-319 (2003) · Zbl 1238.90116
[40] Mladenović, N.; Hansen, P., Variable neighborhood search, Computers & Operations Research, 24, 1097-1100 (1997) · Zbl 0889.90119
[41] Nogueira, B.; Tavares, E.; Maciel, P., Iterated local search with tabu search for the weighted vertex coloring problem, Computers & Operations Research, 105087 (2020)
[42] Oh, Y., Zhou, C., Behdad, S., 2018. Production planning for mass customization in additive manufacturing: build orientation determination, 2d packing and scheduling. In: International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, American Society of Mechanical Engineers. p. V02AT03A033.
[43] Oh, Y.; Witherell, P.; Lu, Y.; Sprock, T., Nesting and scheduling problems for additive manufacturing: a taxonomy and review, Additive Manufacturing, 101492 (2020)
[44] Pastore, T.; Mercuri, V.; Menna, C.; Asprone, D.; Festa, P.; Auricchio, F., Topology optimization of stress-constrained structural elements using risk-factor approach, Computers & Structures, 224, Article 106104 pp. (2019)
[45] Pastore, T.; Menna, C.; Asprone, D., Combining multiple loads in a topology optimization framework for digitally fabricated concrete structures, (RILEM International Conference on Concrete and Digital Fabrication (2020), Springer), 691-700
[46] Queiroz Dos Santos, J. P.; De Melo, J. D.; Duarte Neto, A. D.; Aloise, D., Reactive Search strategies using Reinforcement Learning, local search algorithms and Variable Neighborhood Search, Expert Systems with Applications, 41, 4939-4949 (2014)
[47] Reyes-rubiano, L.; Ferone, D.; Juan, A. A.; Faulin, J., A simheuristic for routing electric vehicles with limited driving ranges and stochastic travel times, SORT, 43, 1-22 (2019) · Zbl 1421.90025
[48] Ribeiro, C. C.; Rosseti, I.; Souza, R. C., Probabilistic stopping rules for grasp heuristics and extensions, International Transactions in Operational Research, 20, 301-323 (2013) · Zbl 1270.90108
[49] Sames, W. J.; List, F. A.; Pannala, S.; Dehoff, R. R.; Babu, S. S., The metallurgy and processing science of metal additive manufacturing, International Materials Reviews, 61, 315-360 (2016)
[50] Stützle, T.; Ruiz, R., Iterated local search, (Martí, R.; Pardalos, P. M.; Resende, M. G.C., Handbook of Heuristics (2018), Springer International Publishing: Springer International Publishing Cham), 579-605
[51] Suhaimi, N.; Nguyen, C.; Damodaran, P., Lagrangian approach to minimize makespan of non-identical parallel batch processing machines, Computers & Industrial Engineering, 101, 295-302 (2016)
[52] Trindade, R. S.; de Araújo, O. C.B.; Fampa, M. H.C.; Müller, F. M., Modelling and symmetry breaking in scheduling problems on batch processing machines, International Journal of Production Research, 56, 7031-7048 (2018)
[53] Uzsoy, R., Scheduling a single batch processing machine with non-identical job sizes, The International Journal of Production Research, 32, 1615-1635 (1994) · Zbl 0906.90095
[54] Wang, Y.; Zheng, P.; Xu, X.; Yang, H.; Zou, J., Production planning for cloud-based additive manufacturing—a computer vision-based approach, Robotics and Computer-Integrated Manufacturing, 58, 145-157 (2019)
[55] Wu, S.; Kay, M.; King, R.; Vila-Parrish, A.; Warsing, D., Multi-objective optimization of 3d packing problem in additive manufacturing, (IIE Annual Conference. Proceedings (2014), Institute of Industrial and Systems Engineers (IISE)), 1485
[56] Zhang, J.; Yao, X.; Li, Y., Improved evolutionary algorithm for parallel batch processing machine scheduling in additive manufacturing, International Journal of Production Research, 58, 2263-2282 (2020)
[57] Zhou, S.; Chen, H.; Li, X., Distance matrix based heuristics to minimize makespan of parallel batch processing machines with arbitrary job sizes and release times, Applied Soft Computing, 52, 630-641 (2017)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.