Combinatorial Benders decomposition for single machine scheduling in additive manufacturing with two-dimensional packing constraints

Zhaofang Mao, Enyuan Fu, Dian Huang, Kan Fang and Lin Chen

European Journal of Operational Research, 2024, vol. 317, issue 3, 890-905

Abstract: This paper addresses a single-machine scheduling problem in additive manufacturing (AM). We focus on the direct metal laser sintering (DMLS) technology of an AM process, where parts can be produced simultaneously in a batch. In this problem, we consider simultaneously the assignment of parts to batches and the packing of parts onto two-dimensional surfaces of the build chamber to minimize the makespan objective. To solve this problem, a mixed integer linear programming model is formulated, and an approximation algorithm is proposed, followed by an exact algorithm based on combinatorial Benders decomposition method with various Benders cuts and acceleration strategies (Algorithm CBD). Finally, we conduct a comprehensive computational study to verify the efficiency of our proposed Algorithm CBD. The computational results show that our proposed Algorithm CBD can effectively solve the test instances with different sizes.

Keywords: Scheduling; Additive manufacturing; Two-dimensional packing; Approximation algorithm; Combinatorial benders decomposition (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724003394
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:317:y:2024:i:3:p:890-905

DOI: 10.1016/j.ejor.2024.05.001

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().