Scheduling unrelated additive manufacturing machines with practical constraints. (English) Zbl 1520.90109
Summary: In the context of Industry 4.0 and COVID-19 pandemic, additive manufacturing (AM), the technology of rapid prototyping directly from digital models, has received rapid development and makes it possible to achieve the need of companies in terms of customized production and limited human resources. Consequently, the growing demands and potential applications necessitate the careful investigation on the associated AM machine scheduling problems to improve productivity. This paper is the first time to study a new AM scheduling problem, which considers unrelated parallel machines and two practical constraints, two-dimensional packing constraints and unequal part release times. Additionally, during the scheduling process, there exist multiple orientation candidates for each part, which potentially influences the processing time and increase the complexity of packing. To solve this problem, we first present a mixed integer linear programming model with the objective to minimize the makespan. Due to the NP-hard nature of the problem, we propose an adaptive large neighborhood search algorithm for large instances where the skyline packing pattern is adopted for the packing procedure. Several destroy and repair operators are designed based on the characteristics of the AM scheduling problem. Finally, three types of datasets with different ranges of release times are generated to verify the efficiency of the proposed algorithm. Some interesting insights on the effects of release times and orientation selection are also revealed and discussed.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
additive manufacturing; unrelated parallel batch machines; two-dimensional packing; part orientation selection; unequal release timesSoftware:
iraceReferences:
| [1] | Ahn, D.; Kim, H.; Lee, S., Fabrication direction optimization to minimize post-machining in layered manufacturing, Int. J. Mach. Tools Manuf., 47, 3-4, 593-606 (2007) |
| [2] | Alexander, P.; Allen, S.; Dutta, D., Part orientation and build cost determination in layered manufacturing, Comput. Aided Des., 30, 5, 343-356 (1998) |
| [3] | 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, Comput. Oper. Res., 131, Article 105272 pp. (2021) · Zbl 1510.90093 |
| [4] | Aloui, A.; Hadj-Hamou, K., A heuristic approach for a scheduling problem in additive manufacturing under technological constraints, Comput. Ind. Eng., 154, Article 107115 pp. (2021) |
| [5] | Altekin, F. T.; Bukchin, Y., A multi-objective optimization approach for exploring the cost and makespan trade-off in additive manufacturing, European J. Oper. Res., 301, 1, 235-253 (2021) · Zbl 1506.90090 |
| [6] | Ark, O. A., Additive manufacturing scheduling problem considering assembly operations of parts, Oper. Res. Int. J. (2021), Published online |
| [7] | 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, Comput. Ind. Eng., 105, 84-100 (2017) |
| [8] | Arroyo, J. E.C.; Leung, J. Y.-T., Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times, Comput. Oper. Res., 78, 117-128 (2017) · Zbl 1391.90236 |
| [9] | Azi, N.; Gendreau, M.; Potvin, J.-y., An adaptive large neighborhood search for a vehicle routing problem with multiple routes, Comput. Oper. Res., 41, 167-173 (2014) · Zbl 1348.90065 |
| [10] | Beezão, A. C.; Cordeau, J. F.; Laporte, G.; Yanasse, H. H., Scheduling identical parallel machines with tooling constraints, European J. Oper. Res., 257, 3, 834-844 (2017) · Zbl 1394.90263 |
| [11] | Bensoussan, H., The history of 3D printing: 3D printing technologies from the 80s to today, Blog Post. Sculpt. Np, 14 (2016) |
| [12] | Burke, E. K.; Kendall, G.; Whitwell, G., A new placement heuristic for the orthogonal stock-cutting problem, Oper. Res., 52, 4, 655-671 (2004) · Zbl 1165.90690 |
| [13] | Byun, H. S.; Lee, K. H., Determination of optimal build direction in rapid prototyping with variable slicing, Int. J. Adv. Manuf. Technol., 28, 3-4, 307-313 (2006) |
| [14] | Byun, H.-S.; Lee, K. H., Determination of the optimal build direction for different rapid prototyping processes using multi-criterion decision making, Robot. Comput.-Integr. Manuf., 22, 1, 69-80 (2006) |
| [15] | Calignano, F., Design optimization of supports for overhanging structures in aluminum and titanium alloys by selective laser melting, Mater. Des., 64, 203-213 (2014) |
| [16] | Canellidis, V.; Giannatsis, J.; Dedoussis, V., Genetic-algorithm-based multi-objective optimization of the build orientation in stereolithography, Int. J. Adv. Manuf. Technol., 45, 7-8, 714-730 (2009) |
| [17] | Canellidis, V.; Giannatsis, J.; Dedoussis, V., Efficient parts nesting schemes for improving stereolithography utilization, Comput. Aided Des., 45, 5, 875-886 (2013) |
| [18] | Castillo-Rivera, S., Maximum utilization in operations scheduling for multiple machines and batches in additive manufacturing, Digit. Manuf. Technol., 1, 1, 1-14 (2021) |
| [19] | Che, Y.; Hu, K.; Zhang, Z.; Lim, A., Machine scheduling with orientation selection and two-dimensional packing for additive manufacturing, Comput. Oper. Res., 130, Article 105245 pp. (2021) · Zbl 1510.90102 |
| [20] | Chergui, A.; Hadj-Hamou, K.; Vignat, F., Production scheduling and nesting in additive manufacturing, Comput. Ind. Eng., 126, 292-301 (2018) |
| [21] | Das, P.; Mhapsekar, K.; Chowdhury, S.; Samant, R.; Anand, S., Selection of build orientation for optimal support structures and minimum part errors in additive manufacturing, Comput.-Aided Des. Appl., 14, sup1, 1-13 (2017) |
| [22] | Demir, E.; Bektaş, T.; Laporte, G., An adaptive large neighborhood search heuristic for the pollution-routing problem, European J. Oper. Res., 223, 2, 346-359 (2012) · Zbl 1292.90045 |
| [23] | Dvorak, F.; Micali, M.; Mathieug, M., Planning and scheduling in additive manufacturing, Intel. Artif., 21, 62, 40-52 (2018) |
| [24] | Fera, M.; Macchiaroli, R.; Fruggiero, F.; Lambiase, A., Production management fundamentals for additive manufacturing, (3D Printing (2018), IntechOpen) |
| [25] | François, V.; Arda, Y.; Crama, Y., Adaptive large neighborhood search for multitrip vehicle routing with time windows, Transp. Sci., 53, 6, 1706-1730 (2019) |
| [26] | Frazier, W. E., Metal additive manufacturing: a review, J. Mater. Eng. Perform., 23, 6, 1917-1928 (2014) |
| [27] | Hur, S.-M.; Choi, K.-H.; Lee, S.-H.; Chang, P.-K., Determination of fabricating orientation and packing in SLS process, J. Mater Process. Technol., 112, 2-3, 236-243 (2001) |
| [28] | Kapadia, M. S.; Uzsoy, R.; Starly, B.; Warsing, D. P., A genetic algorithm for order acceptance and scheduling in additive manufacturing, Int. J. Prod. Res. (2021), Published online |
| [29] | Kucukkoc, I., MILP models to minimise makespan in additive manufacturing machine scheduling problems, Comput. Oper. Res., 105, 58-67 (2019) · Zbl 1458.90315 |
| [30] | Kuhn, H.; Schubert, D.; Holzapfel, A., Integrated order batching and vehicle routing operations in grocery retail-A General Adaptive Large Neighborhood Search algorithm, European J. Oper. Res., 294, 3, 1003-1021 (2020) · Zbl 1487.90125 |
| [31] | Lan, P.-T.; Chou, S.-Y.; Chen, L.-L.; Gemmill, D., Determining fabrication orientations for rapid prototyping with stereolithography apparatus, Comput. Aided Des., 29, 1, 53-62 (1997) |
| [32] | Li, X.; Huang, Y.; Tan, Q.; Chen, H., Scheduling unrelated parallel batch processing machines with non-identical job sizes, Comput. Oper. Res., 40, 12, 2983-2990 (2013) · Zbl 1348.90285 |
| [33] | Li, Q.; Kucukkoc, I.; Zhang, D. Z., Production planning in additive manufacturing and 3D printing, Comput. Oper. Res., 83, 157-172 (2017) |
| [34] | Li, Q.; Zhang, D.; Wang, S.; Kucukkoc, I., A dynamic order acceptance and scheduling approach for additive manufacturing on-demand production, Int. J. Adv. Manuf. Technol., 105, 9, 3711-3729 (2019) |
| [35] | Liu, X.; Laporte, G.; Chen, Y.; He, R., An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time, Comput. Oper. Res., 86, 41-53 (2017) · Zbl 1391.90288 |
| [36] | López-Ibánez, M.; Dubois-Lacoste, J.; Cáceres, L. P.; Birattari, M.; Stützle, T., The irace package: Iterated racing for automatic algorithm configuration, Oper. Res. Perspect., 3, 43-58 (2016) |
| [37] | Narayanamurthy, G.; Tortorella, G., Impact of COVID-19 outbreak on employee performance-Moderating role of industry 4.0 base technologies, Int. J. Prod. Econ., 234, Article 108075 pp. (2021) |
| [38] | Pandey, P. M.; Thrimurthulu, K.; Reddy*, N. V., Optimal part deposition orientation in FDM by using a multicriteria genetic algorithm, Int. J. Prod. Res., 42, 19, 4069-4089 (2004) · Zbl 1060.90030 |
| [39] | Rifai, A. P.; Nguyen, H.-T.; Dawal, S. Z.M., Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling, Appl. Soft Comput., 40, 42-57 (2016) |
| [40] | Rohaninejad, M.; Tavakkoli-Moghaddam, R.; Vahedi-Nouri, B.; Hanzálek, Z.; Shirazian, S., A hybrid learning-based meta-heuristic algorithm for scheduling of an additive manufacturing system consisting of parallel SLM machines, Int. J. Prod. Res. (2021), Published online |
| [41] | Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transp. Sci., 40, 4, 455-472 (2006) |
| [42] | Shahidi-Zadeh, B.; Tavakkoli-Moghaddam, R.; Taheri-Moghadam, A.; Rastgar, I., Solving a bi-objective unrelated parallel batch processing machines scheduling problem: A comparison study, Comput. Oper. Res., 88, 71-90 (2017) · Zbl 1391.90315 |
| [43] | Thrimurthulu, K.; Pandey, P. M.; Reddy, N. V., Optimum part deposition orientation in fused deposition modeling, Int. J. Mach. Tools Manuf., 44, 6, 585-594 (2004) |
| [44] | Vicari, A., Advanced applications of 3D printing: From prototypes and parts, (Additive Manufacturing for Defence and Aerospace Summit, London (2015)), https://Additivemanufacturing.iqpc.co.uk/downloads/advanced-applications-of-3d-printing-fromprototypes-and-parts |
| [45] | Wei, L.; Zhang, Z.; Lim, A., An adaptive variable neighborhood search for a heterogeneous fleet vehicle routing problem with three-dimensional loading constraints, IEEE Comput. Intell. Mag., 9, 4, 18-30 (2014) |
| [46] | Wei, L.; Zhang, Z.; Zhang, D.; Lim, A., A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints, European J. Oper. Res., 243, 3, 798-814 (2015) · Zbl 1346.90193 |
| [47] | Wohlers, L., Wohlers publishes 2020 AM report, Metal Powder Rep., 75, 4, 237 (2020) |
| [48] | Yang, Y.; Fuh, J. Y.; Loh, H. T.; Wong, Y. S., Multi-orientational deposition to minimize support in the layered manufacturing process, J. Manuf. Syst., 22, 2, 116-129 (2003) |
| [49] | Zhang, Y.; Bernard, A.; Harik, R.; Karunakaran, K., Build orientation optimization for multi-part production in additive manufacturing, J. Intell. Manuf., 28, 6, 1393-1407 (2017) |
| [50] | Zhang, J.; Yao, X.; Li, Y., Improved evolutionary algorithm for parallel batch processing machine scheduling in additive manufacturing, Int. J. Prod. Res., 58, 8, 2263-2282 (2020) |
| [51] | Zhou, S.; Xie, J.; Du, N.; Pang, Y., A random-keys genetic algorithm for scheduling unrelated parallel batch processing machines with different capacities and arbitrary job sizes, Appl. Math. Comput., 334, 254-268 (2018) · Zbl 1427.90166 |
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.
