Machine scheduling with orientation selection and two-dimensional packing for additive manufacturing. (English) Zbl 1510.90102
Summary: In recent years, additive manufacturing (AM) gains increasing attention in manufacturing industries due to the growing demands, and the corresponding machine scheduling problems also attract many researchers. In this paper, we study a new unrelated parallel batch processing machine scheduling problem arose in AM, which requires to simultaneously assign parts to batches, determine the orientation of parts, pack the parts to the two-dimensional surface, and allocate the batches to machines. It is the first work to consider the orientation selection for parts in machine scheduling with the objective to minimize the makespan. To solve this problem, we first present a mixed integer linear programming model. Then, a simulated annealing algorithm with designed packing strategies based on the skyline representation of packing pattern is developed. Moreover, data structure Trie is introduced to accelerate the whole procedure and four post-optimization methods are designed to further refine solutions. Finally, a comprehensive computational study is conducted. The efficiency of our heuristic algorithms is verified and the best packing strategy for this problem is identified. The advantage of considering multiple orientations of parts in machine scheduling is demonstrated by comparisons with scenarios of fixed orientation.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
scheduling; additive manufacturing; unrelated parallel batch machines; part orientation selection; two-dimensional bin packing; heuristicsReferences:
| [1] | Ahn, D.; Kim, H.; Lee, S., Fabrication direction optimization to minimize post-machining in layered manufacturing, Int. J. Mach. Tools Manuf, 47, 593-606 (2007) |
| [2] | Alexander, P.; Allen, S.; Dutta, D., Part orientation and build cost determination in layered manufacturing, Comput. Aided Des., 30, 343-356 (1998) |
| [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, Comput. Ind. Eng., 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, Comput. Oper. Res., 78, 117-128 (2017) · Zbl 1391.90236 |
| [5] | Burke, E. K.; Kendall, G.; Whitwell, G., A new placement heuristic for the orthogonal stock-cutting problem, Oper. Res., 52, 655-671 (2004) · Zbl 1165.90690 |
| [6] | Byun, H. S.; Lee, K. H., Determination of optimal build direction in rapid prototyping with variable slicing, Int. J. Adv. Manuf. Technol., 28, 307-313 (2006) |
| [7] | 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, 69-80 (2006) |
| [8] | Calignano, F., Design optimization of supports for overhanging structures in aluminum and titanium alloys by selective laser melting, Mater. Design, 64, 203-213 (2014) |
| [9] | Canellidis, V.; Giannatsis, J.; Dedoussis, V., Genetic-algorithm-based multi-objective optimization of the build orientation in stereolithography, Int. J. Adv. Manuf. Technol., 45, 714-730 (2009) |
| [10] | Canellidis, V.; Giannatsis, J.; Dedoussis, V., Efficient parts nesting schemes for improving stereolithography utilization, Comput. Aided Des., 45, 875-886 (2013) |
| [11] | Chergui, A.; Hadj-Hamou, K.; Vignat, F., Production scheduling and nesting in additive manufacturing, Comput. Ind. Eng., 126, 292-301 (2018) |
| [12] | 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 Design Appl., 14, 1-13 (2017) |
| [13] | Dvorak, F.; Micali, M.; Mathieug, M., Planning and scheduling in additive manufacturing, Inteligencia Artif., 21, 40-52 (2018) |
| [14] | Fera, M., Macchiaroli, R., Fruggiero, F., Lambiase, A., 2018. Production management fundamentals for additive manufacturing. 3D Printing, 71-88. |
| [15] | Guo, N.; Leu, M. C., Additive manufacturing: technology, applications and research needs, Front. Mech. Eng., 8, 215-243 (2013) |
| [16] | 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, 236-243 (2001) |
| [17] | Kim, D. W.; Kim, K. H.; Jang, W.; Frank Chen, F., Unrelated parallel machine scheduling with setup times using simulated annealing, Robot. Comput.-Integr. Manuf., 18, 223-231 (2002) |
| [18] | Kucukkoc, I., MILP models to minimise makespan in additive manufacturing machine scheduling problems, Comput. Oper. Res., 105, 58-67 (2019) · Zbl 1458.90315 |
| [19] | Lai, K.; Chan, J. W., Developing a simulated annealing algorithm for the cutting stock problem, Comput. Ind. Eng., 32, 115-127 (1997) |
| [20] | Leung, S. C.; Zhang, D.; Sim, K. M., A two-stage intelligent search algorithm for the two-dimensional strip packing problem, Eur. J. Oper. Res., 215, 57-69 (2011) |
| [21] | Li, Q.; Kucukkoc, I.; Zhang, D. Z., Production planning in additive manufacturing and 3d printing, Comput. Oper. Res., 83, 157-172 (2017) |
| [22] | Li, X.; Huang, Y.; Tan, Q.; Chen, H., Scheduling unrelated parallel batch processing machines with non-identical job sizes, Comput. Oper. Res., 40, 2983-2990 (2013) · Zbl 1348.90285 |
| [23] | Lin, S.-W.; Ying, K.-C., A multi-point simulated annealing heuristic for solving multiple objective unrelated parallel machine scheduling problems, Int. J. Prod. Res., 53, 1065-1076 (2015) |
| [24] | Padhye, N.; Deb, K., Multi-objective optimisation and multi-criteria decision making in sls using evolutionary approaches, Rapid Prototyping J., 17, 458-478 (2011) |
| [25] | Pandey, P.M., Thrimurthulu, K., Reddy, N.V., 2004. Optimal part deposition orientation in fdm by using a multicriteria genetic algorithm. Int. J. Prod. Res. 42, 4069-4089. · Zbl 1060.90030 |
| [26] | Pour, M. A.; Zanardini, M.; Bacchetti, A.; Zanoni, S., Additive manufacturing impacts on productions and logistics systems, IFAC-PapersOnLine, 49, 1679-1684 (2016) |
| [27] | Shahvari, O.; Logendran, R., A bi-objective batch processing problem with dual-resources on unrelated-parallel machines, Appl. Soft Comput., 61, 174-192 (2017) |
| [28] | Thrimurthulu, K.; Pandey, P. M.; Reddy, N. V., Optimum part deposition orientation in fused deposition modeling, Int. J. Mach. Tools Manuf., 44, 585-594 (2004) |
| [29] | Vicari, A., 2015. Advanced applications of 3d printing: from prototypes and parts. Additive Manufacturing for Defence and Aerospace Summit, London.https://additivemanufacturing.iqpc.co.uk/downloads/advanced-applications-of-3d-printing-fromprototypes-and-parts. |
| [30] | Wei, L.; Hu, Q.; Leung, S. C.; Zhang, N., An improved skyline based heuristic for the 2D strip packing problem and its efficient implementation, Comput. Oper. Res., 80, 113-127 (2017) · Zbl 1391.90538 |
| [31] | 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, 18-30 (2014) |
| [32] | Wei, L.; Zhang, Z.; Zhang, D.; Leung, S. C., A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints, Eur. J. Oper. Res., 265, 843-859 (2018) · Zbl 1374.90329 |
| [33] | 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, 1485-1494 (2014) |
| [34] | Xiao, J.; Yang, H.; Zhang, C.; Zheng, L.; Gupta, J. N., A hybrid lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times, Comput. Oper. Res., 63, 72-82 (2015) · Zbl 1349.90053 |
| [35] | 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, 116-129 (2003) |
| [36] | Zhang, D.; Dong, R.; Si, Y. W.; Ye, F.; Cai, Q., A hybrid swarm algorithm based on ABC and AIS for 2L-HFCVRP, Appl. Soft Comput., 64, 468-479 (2018) |
| [37] | Zhang, J.; Yao, X.; Li, Y., Improved evolutionary algorithm for parallel batch processing machine scheduling in additive manufacturing, Int. J. Prod. Res., 58, 2263-2282 (2020) |
| [38] | Zhang, Y.; Bernard, A.; Harik, R.; Karunakaran, K., Build orientation optimization for multi-part production in additive manufacturing, J. Intell. Manuf., 28, 1393-1407 (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. 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.
