Logic-based Benders decomposition for additive manufacturing scheduling on unrelated parallel machines

Abstract

Additive manufacturing (AM), also known as 3D printing, offers innovative solutions for customized production. This paper addresses an AM scheduling problem on unrelated parallel machines that considers different part release times. A mixed integer linear programming (MILP) model aimed at minimizing makespan is developed, enhanced by valid inequalities and symmetry-breaking constraints. We propose a logic-based Benders decomposition (LBBD) algorithm to divide the problem into a master problem (MP), which determines part assignment and grouping into batches, and multiple subproblems (SPs) that sequence the batches on each AM machine. An earliest release date (ERD) rule is introduced to quickly solve subproblems. Three feasibility cuts and two optimality cuts are proposed and combined into eight types of cuts for the master problem. In addition, a new heuristic is developed to quickly obtain an upper bound of the problem. Computational results across various instance sizes demonstrate the performance of the proposed LBBD algorithm, as well as the effectiveness of the proposed symmetry-breaking constraints and various types of cuts.