Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年2月16日

查看全文
  • Jian Chen,
  • Wenjing Ma,
  • Mingyue Sun,
  • Zhiheng Zhao

摘要

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.