A branch-and-price algorithm to perform single-machine scheduling for additive manufacturing

DOI码：

10.1016/j.jmse.2022.10.001

发表刊物：

Journal of Management Science and Engineering

摘要：

Additive manufacturing (AM) has attracted significant attention in recent years based on its wide range of applications and growing demand. AM offers the advantages of production flexibility and design freedom. In this study, we considered a practical variant of the batch-processing-machine (BPM) scheduling problem that arises in AM industries, where an AM machine can process multiple parts simultaneously, as long as the two-dimensional rectangular packing constraint is not violated. Based on the set-partitioning formulation of our mixed-integer programming (MIP) model, a branch-and-price (B&P) algorithm was developed by embedding a column-generation technique into a branch-and-bound framework. Additionally, a novel labelling algorithm was developed to accelerate the column-generation process. Ours is the first study to provide a B&P algorithm to solve the BPM scheduling problem in the AM industry. We tested the performance of our algorithm using a modern MIP solver (Gurobi) and real data from a 3D printing factory. The results demonstrate that for most instances tested, our algorithm produces results similar or identical to those of Gurobi with reasonable computation time and outperforms Gurobi in terms of solution quality and running time on some large instances.

合写作者：

Zhenyu Wu

第一作者：

Lindong Liu

通讯作者：

Yugang Yu

论文编号：

[10]

卷号：

8

期号：

2

页面范围：

273-286

是否译文：

否

发表时间：

2023-06-18