A heuristic algorithm for identical parallel machine scheduling: splitting jobs, sequence-dependent setup times, and lim
- PDF / 1,598,553 Bytes
- 35 Pages / 439.37 x 666.142 pts Page_size
- 21 Downloads / 214 Views
A heuristic algorithm for identical parallel machine scheduling: splitting jobs, sequence‑dependent setup times, and limited setup operators Jun‑Ho Lee1 · Hyun‑Jung Kim2 Accepted: 15 November 2020 © The Author(s), under exclusive licence to Springer Science+Business Media, LLC part of Springer Nature 2020
Abstract We examine a parallel machine scheduling problem with a job splitting property, sequence-dependent setup times, and limited setup operators, for minimizing makespan. Jobs are split into arbitrary (job) sections that can be processed on different machines simultaneously. When a job starts to be processed on a machine, a setup that requires an operator is performed, and the setup time is sequence-dependent. The number of setup operators is limited, and hence not all of the machines can be set up at the same time. For this problem, we propose a mathematical programming model and analyze a lower bound. We then develop a simple but efficient heuristic algorithm so that it can be used in practice, and analytically derive a worst-case bound of the algorithm. We finally evaluate the performance of the proposed algorithm numerically with various scenarios. Keywords Parallel machine scheduling · Job splitting · Setup operators · Sequencedependent setup times · Heuristic algorithm
1 Introduction In this paper, an identical parallel machine scheduling problem with job splitting, sequence-dependent setup times, and limited setup operators (or resources) is addressed. This problem is motivated from real-world applications such as casting processes for automotive pistons, cylinder heads, and cylinder blocks in an internal combustion engine, and transmission housings. For example, automotive pistons are first cast from aluminum alloys in multiple identical machines, each of which * Hyun‑Jung Kim [email protected] 1
School of Business, Chungnam National University, Daejeon 34134, Republic of Korea
2
Department of Industrial and Systems Engineering, Korea Advanced Institute of Science and Technology, Daejeon 34141, Republic of Korea
13
Vol.:(0123456789)
J.-H. Lee, H.-J. Kim
can process approximately 1000–2000 piston units a day. When a piston type to be processed is changed, a setup is performed for hours, mostly 4–10 h, depending on the pistons that are just completed and to be processed; that is, sequence-dependent setup times are assumed. In the example, pistons with the same type can be split into arbitrary lot sizes. A job then refers to a set of pistons with the same type, and the number of pistons processed consecutively on a machine refers to a section of the job; that is, jobs can be split into arbitrary job sections that can be processed on multiple machines at the same time. Another important scheduling requirement of the problem is the limited setup operators. When a section of a job is processed on a machine, a setup that is performed by a setup operator is required. However, there are too few setup operators to set up all the machines at the same time. Therefore, the number of setups pe
Data Loading...
