An exact algorithm for an identical parallel additive machine scheduling problem with multiple processing alternatives

Abstract

This paper develops an exact algorithm for the identical parallel additive machine scheduling problem by considering multiple processing alternatives to minimise the makespan. This research is motivated from an idea of elevating flexibility of a manufacturing system by using additive machines, such as 3D printers. It becomes possible to produce a job in a different form; a job can be printed in a complete form or in separate parts. This problem is defined as a bi-level optimisation model in which its upper level problem is to determine a proper processing alternative for each product, and its lower level problem is to assign the parts that should be produced to the additive machines. An exact algorithm, which consists of the linear programming relaxation of a one-dimensional cutting stock problem, a branch-and-price algorithm, and a rescheduling algorithm, is proposed to find an optimal solution of the problem. The experimental results show that the computational time of the algorithm outperforms a commercial solver (CPLEX). By examining how the parts are comprised when the processing alternatives are optimally selected, some useful insights are derived for designing processing alternatives of products.

KEYWORDS:

• Additive manufacturing system
• parallel machine scheduling
• multiple processing alternatives
• minimization of makespan
• exact algorithm

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The data that supports the findings of this study is available from the first author, Jun Kim, upon reasonable request.

Additional information

Funding

This paper was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (Ministry of Science Industry and Technology) (No. 2019R1C1C1004667).

Notes on contributors

Jun Kim

Jun Kim is a researcher in the Digital Transformation R&D Department, Korea Institute of Industrial Technology. He is currently pursuing his Ph.D. degree from the Sungkyunkwan University (South Korea) and received his Bachelor's degree from the same university in 2014. His research interest is optimisation, scheduling, smart factory, digital transformation, and data analytics.

Hyun-Jung Kim

Hyun-Jung Kim received the Ph.D. degree in Industrial and Systems Engineering from Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Republic of Korea in 2013. She was a Postdoctoral Researcher in the Department of Industrial Engineering & Operations Research, University of California, Berkeley, and was an Assistant Professor in the Department of Systems Management Engineering, Sungkyunkwan University, Republic of Korea. She is now an Assistant Professor with the Department of Industrial & Systems Engineering, KAIST. Her research interests include modelling, scheduling, and control of production systems.