Logic-based Benders decomposition for additive manufacturing scheduling on unrelated parallel machines
研究了无关并行机上考虑零件释放时间的增材制造调度问题，提出基于逻辑的Benders分解算法，通过主问题分配零件并分批、子问题排序批次，结合多种割和启发式方法最小化最大完工时间。
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.