Scheduling unrelated additive manufacturing machines with practical constraints

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.