Machine scheduling with orientation selection and two-dimensional packing for additive manufacturing

Abstract 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.