×

Optimal decomposition approach for solving large nesting and scheduling problems of additive manufacturing systems. (English) Zbl 07881375

Summary: This paper addresses the challenges associated with nesting and production scheduling in additive manufacturing (AM). The problem studied consists of grouping a set of parts into batches, which are then assigned to and sequenced across the available machines, guaranteeing the production of all parts. This work stands out by proposing exact methods for the AM nesting and scheduling problem considering irregular-shaped parts with specific release dates, processing times, and due dates, with the aim of minimizing the cumulative tardiness. The proposed approaches include two logic-based Benders decompositions: one combining Mixed Integer Programming (MIP) and Constraint Programming (CP), and the other relying solely on CP. To deal with the sub-problems, a strategic procedure was developed to reduce the solution space while maintaining low resolution times per iteration. Problem-specific cuts are also generated to improve the efficiency of these approaches. Computational experiments show that both decompositions significantly outperform a prior monolithic CP model, with the decomposition based solely on CP yielding the best results. Moreover, the results show that this approach has the potential to achieve similar computational performance of non-exact approaches that are currently considered state-of-the-art. A set of instances is provided to serve as a benchmark for future studies.

MSC:

90Bxx Operations research and management science
Full Text: DOI

References:

[1] Alicastro, M.; Ferone, D.; Festa, P.; Fugaro, S.; Pastore, T., A reinforcement learning iterated local search for makespan minimization in additive manufacturing machine scheduling problems, Computers and Operations Research, 131, Article 105272 pp., 2021, January 2020 · Zbl 1510.90093
[2] Aloui, A.; Hadj-hamou, K., A heuristic approach for a scheduling problem in additive manufacturing under technological constraints, Computers & Industrial Engineering, 154, Article 107115 pp., 2021, March 2020
[3] Alvarez-Valdes, R.; Martinez, A.; Tamarit, J. M., A branch & bound algorithm for cutting and packing irregularly shaped pieces, International Journal of Production Economics, 145, 2, 463-477, 2013
[4] Arık, O. A., Additive manufacturing scheduling problem considering assembly operations of parts, Operational Research, Article 0123456789 pp., 2021
[5] Barzanji, R.; Naderi, B.; Begen, M. A., Decomposition algorithms for the integrated process planning and scheduling problem, Omega, 93, 2020, (United Kingdom)
[6] Bennell, J. A.; Oliveira, J. F., A tutorial in irregular shape packing problems, Journal of the Operational Research Society, 60, SUP1, S93-S105, 2009 · Zbl 1168.90300
[7] Burke, E. K.; Hellier, R. S.R.; Kendall, G.; Whitwell, G., Complete and robust no-fit polygon generation for the irregular stock cutting problem, European Journal of Operational Research, 179, 1, 27-49, 2007 · Zbl 1175.90325
[8] Carravilla, M. A.; Ribeiro, C.; Oliveira, J. F., Solving nesting problems with non-convex polygons by constraint logic programming, International Transactions in Operational Research, 10, 6, 651-663, 2003 · Zbl 1094.68533
[9] Chang, P. Y.; Damodaran, P.; Melouk, S., Minimizing makespan on parallel batch processing machines, International Journal of Production Research, 42, 19, 4211-4220, 2004
[10] Che, Y.; Hu, K.; Zhang, Z.; Lim, A., Machine scheduling with orientation selection and two-dimensional packing for additive manufacturing, Computers and Operations Research, 130, Article 105245 pp., 2021 · Zbl 1510.90102
[11] Chergui, A.; Hadj-hamou, K.; Vignat, F., Production scheduling and nesting in additive manufacturing, Computers & Industrial Engineering, 126, 292-301, 2018, September
[12] Cherri, L. H.; Mundim, L. R.; Andretta, M.; Toledo, F. M.B.; Oliveira, J. F.; Carravilla, M. A., Robust mixed-integer linear programming models for the irregular strip packing problem, European Journal of Operational Research, 253, 3, 570-583, 2016 · Zbl 1346.90626
[13] Cherri, L. H.; Carravilla, M. A.; Ribeiro, C.; Toledo, F. M.B., Optimality in nesting problems: New constraint programming models and a new global constraint for non-overlap, Operations Research Perspectives, 6, Article 100125 pp., 2019
[14] Chou, F. D., Minimising the total weighted tardiness for non-identical parallel batch processing machines with job release times and non-identical job sizes, European J. Industrial Engineering, 7, 5, 2013
[15] Chung, S. H.; Tai, Y. T.; Pearn, W. L., Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes, International Journal of Production Research, 47, 18, 5109-5128, 2009 · Zbl 1198.90174
[16] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Mathematical Programming Series B, 91, 2, 201-213, 2002 · Zbl 1049.90004
[17] 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, 9, 4, 423-438, 2018
[18] Fera, M.; Macchiaroli, R.; Fruggiero, F.; Lambiase, A., A modified tabu search algorithm for the single-machine scheduling problem using additive manufacturing technology, International Journal of Industrial Engineering Computations, 11, 3, 401-414, 2020
[19] Fischetti, M.; Luzzi, I., Mixed-integer programming models for nesting problems, Journal of Heuristics, 15, 3, 201-226, 2009 · Zbl 1172.90495
[20] Fischetti, M.; Ljubić, I.; Monaci, M.; Sinnl, M., A new general-purpose algorithm for mixed-integer bi-level linear programs, Operations Research, 65, 6, 1615-1637, 2017 · Zbl 1386.90085
[21] Fowler, J. W.; Mönch, L., A survey of scheduling with parallel batch (p-batch) processing, European Journal of Operational Research, 298, 1, 1-24, 2022, Elsevier B.V · Zbl 1490.90125
[22] Framinan, J. M.; Fernandez-Viagas, V.; Perez-Gonzalez, P., An overview on the use of operations research in additive manufacturing, Annals of Operations Research, 322, 1, 2023, Springer US · Zbl 1517.90044
[23] Gardan, J., Additive manufacturing technologies: State of the art and trends, International Journal of Production Research, 54, 10, 3118-3132, 2016
[24] Gedik, R.; Rainwater, C.; Nachtmann, H.; Pohl, E. A., Analysis of a parallel machine scheduling problem with sequence dependent setup times and job availability intervals, European Journal of Operational Research, 251, 2, 640-650, 2016 · Zbl 1346.90346
[25] Goel, V.; Slusky, M.; Van Hoeve, W. J.; Furman, K. C.; Shao, Y., Constraint programming for LNG ship scheduling and inventory management, European Journal of Operational Research, 241, 3, 662-673, 2015 · Zbl 1339.90049
[26] Grossmann, I. E.; Biegler, L. T., Part II. Future perspective on optimization, Computers and Chemical Engineering, 28, 8, 1193-1218, 2004
[27] Ham, A. M.; Fowler, J. W.; Cakici, E., Constraint programming approach for scheduling jobs with release times, non-identical sizes, and incompatible families on parallel batching machines, IEEE Transactions on Semiconductor Manufacturing, 30, 4, 500-507, 2017
[28] Hooker, J. N., Logic-based methods for optimization: combining optimization and constraint satisfaction, 2000, John Wiley & Sons · Zbl 0974.90001
[29] Hooker, J. N., Planning and scheduling by logic-based benders decomposition, Operations Research, 55, 3, 588-602, 2007 · Zbl 1167.90512
[30] Hooker, J. N., Logic-based benders decomposition for large-scale optimization, Large scale optimization in supply chains and smart manufacturing: Theory and applications, 1-26, 2019, Springer International Publishing, M. and F. M. Velásquez-Bermúdez & Jesús M. and Khakifirooz (Ed.) · Zbl 1446.90108
[31] Hu, K.; Che, Y.; Zhang, Z., Scheduling unrelated additive manufacturing machines with practical constraints, Computers and Operations Research, 144, Article 105847 pp., 2022, February · Zbl 1520.90109
[32] Hu, K.; Che, Y.; Ng, T. S.; Deng, J., Unrelated parallel batch processing machine scheduling with time requirements and two-dimensional packing constraints, Computers and Operations Research, 162, 2024 · Zbl 07860746
[33] ISO/ASTM. (2021). ISO/ASTM 52900: additive manufacturing - general principles - fundamentals and vocabulary. In International Standard: Vol. Second Edition (pp. 1-28). https://www.iso.org/standard/74514.html.
[34] Jain, V.; Grossmann, I. E., Algorithms for hybrid MILP/CP models for a class of optimization problems, INFORMS Journal on Computing, 13, 4, 258-276, 2001 · Zbl 1238.90106
[35] Kang, H. S.; Noh, S. Do; Son, J. Y.; Kim, H.; Park, J. H.; Lee, J. Y., The FaaS system using additive manufacturing for personalized production, Rapid Prototyping Journal, 24, 9, 1486-1499, 2018
[36] Kucukkoc, I., MILP models to minimise makespan in additive manufacturing machine scheduling problems, Computers and Operations Research, 105, 58-67, 2019 · Zbl 1458.90315
[37] Li, Q.; Kucukkoc, I.; Zhang, D. Z., Production planning in additive manufacturing and 3D printing, Computers and Operations Research, 83, 1339-1351, 2017
[38] Liu, L.; Wu, Z.; Yu, Y., A branch-and-price algorithm to perform single-machine scheduling for additive manufacturing, Journal of Management Science and Engineering, 8, 2, 273-286, 2023
[39] Lunardi, W. T.; Birgin, E. G.; Laborie, P.; Ronconi, D. P.; Voos, H., Mixed integer linear programming and constraint programming models for the online printing shop scheduling problem, Computers and Operations Research, 123, 2020 · Zbl 1458.90326
[40] Mönch, L.; Balasubramanian, H.; Fowler, J. W.; Pfund, M. E., Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times, Computers and Operations Research, 32, 11, 2731-2750, 2005 · Zbl 1071.90019
[41] Malapert, A.; Guéret, C.; Rousseau, L. M., A constraint programming approach for a batch processing problem with non-identical job sizes, European Journal of Operational Research, 221, 3, 533-545, 2012 · Zbl 1253.90198
[42] Maranha, J.; Nascimento, P. J.; Calcerano, T. A.; Silva, C.; Mueller, S.; Moniz, S., A decision-support framework for selecting additive manufacturing technologies, Journal of Manufacturing Technology Management, 2023
[43] Nascimento, P., Silva, C., Mueller, S., & Moniz, S. (2023). Nesting and scheduling for additive manufacturing: an approach considering order due dates. In J. P . Almeida, C. S . Geraldes, I. C . Lopes, S. Moniz, J. F . Oliveira, & A. & A. Pinto (Eds.), Operational Research. IO 2021. Springer Proceedings in Mathematics & Statistics (pp. 117-128, Cham: Springer. 10.1007/978-3-031-20788-4_8.
[44] Oh, Y.; Zhou, C.; Behdad, S., Production planning for mass customization in additive manufacturing: Build orientation determination, 2D packing and scheduling, (Proceedings of the ASME design engineering technical conference, 2018), 1-9, 2A-2018
[45] Oh, Y.; Witherell, P.; Lu, Y.; Sprock, T., Nesting and scheduling problems for additive manufacturing : A taxonomy and review, Additive Manufacturing, 36, Article 101492 pp., 2020, April
[46] Pinto, M.; Silva, C.; Thürer, M.; Moniz, S., Nesting and scheduling optimization of additive manufacturing systems: mapping the territory, Computers & Operations Research, 165, Article 106592 pp., 2024 · Zbl 07870687
[47] Ribeiro, C.; Carravilla, M. A., A global constraint for nesting problems, Artificial Intelligence Review, 30, 1-4, 99-118, 2008
[48] Tafakkori, K.; Tavakkoli-moghaddam, R.; Siadat, A., Sustainable negotiation-based nesting and scheduling in additive manufacturing systems : A case study and multi-objective meta-heuristic algorithms, Engineering Applications of Artificial Intelligence, 112, Article 104836 pp., 2022, September 2021
[49] Toledo, F. M.B.; Carravilla, M. A.; Ribeiro, C.; Oliveira, J. F.; Gomes, A. M., The Dotted-Board Model: A new MIP model for nesting irregular shapes, International Journal of Production Economics, 145, 2, 478-487, 2013
[50] 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, 22, 7031-7048, 2018
[51] Trindade, R. S.; de Araújo, O. C.B.; Fampa, M., Arc-flow approach for parallel batch processing machine scheduling with non-identical job sizes, Lecture Notes in Computer Science, 2020, 179-190, 2020
[52] Trindade, R. S.; de Araújo, O. C.B.; Fampa, M., Arc-flow approach for single batch-processing machine scheduling, Computers and Operations Research, 134, 2021 · Zbl 1511.90221
[53] Uzsoy, R., Scheduling a single batch processing machine with non-identical job sizes, International Journal of Production Research, 32, 7, 1615-1635, 1994 · Zbl 0906.90095
[54] Vélez-Gallego, M. C., Algorithms for scheduling parallel batch processing machines with non-identical job ready times, 2009, Florida International University
[55] Wohlers, T., Campbell, I., Diegel, I., Huff, R., & Kowen, J. (2023). Wohlers report 2023: 3D printing and additive manufacturing state of the industry.
[56] Ying, K.; Fruggiero, F.; Pourhejazy, P.; Lee, B., Adjusted iterated greedy for the optimization of additive manufacturing scheduling problems, Expert Systems with Applications, 198, Article 116908 pp., 2022, January
[57] Yu, C.; Matta, A.; Semeraro, Q.; Lin, J., Mathematical models for minimizing total tardiness on parallel additive manufacturing machines, IFAC PapersOnLine, 55, 10, 1521-1526, 2022
[58] Yunusoglu, P.; Topaloglu Yildiz, S., Constraint programming approach for multi-resource-constrained unrelated parallel machine scheduling problem with sequence-dependent setup times, International Journal of Production Research, 60, 7, 2212-2229, 2022
[59] Zhang, J.; Yao, X.; Li, Y., Improved evolutionary algorithm for parallel batch processing machine scheduling in additive manufacturing, International Journal of Production Research, 7543, 2020
[60] Zhang, X.; Shan, M.; Zeng, J., Parallel batch processing machine scheduling under two-dimensional bin-packing constraints, IEEE Transactions on Reliability, 72, 3, 1265-1275, 2023
[61] Zipfel, B.; Neufeld, J.; Buscher, U., An iterated local search for customer order scheduling in additive manufacturing, International Journal of Production Research, 2023
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.