Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experimen
- PDF / 1,218,591 Bytes
- 14 Pages / 595.276 x 790.866 pts Page_size
- 16 Downloads / 203 Views
Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments Jianming Dong1 · Joshua Chang2 · Bing Su3 · Jueliang Hu1 · Guohui Lin2
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We study a scheduling environment that finds many real-world manufacturing applications, in which there is a close connection between a hybrid multiprocessor open shop and multiple parallel identical flow shops. In this environment, there is an extended two-stage open shop, where in one stage we have a set of parallel identical machines, while in the other we have a two-machine flow shop. Our objective is to minimize the makespan, that is, the latest completion time of all jobs. We pursue approximation algorithms with provable performance, and we achieve a 2-approximation when the number of parallel identical machines is constant or is part of the input; we also design a 5/3-approximation for the special case where there is only one machine in the multiprocessor stage, which remains weakly NP-hard. Our empirical experiments show that both approximation algorithms perform much better in simulated instances; their average ratios over the proposed lower bound are around 1.5 and 1.2, respectively. Keywords Scheduling · Extended two-stage open shop · Two-machine flow shop · Multiprocessor · Approximation algorithm
1 Introduction We consider an extended two-stage open-shop scheduling environment denoted as O2(P, F2), where in one stage we have a set of parallel identical machines denoted as A1 , A2 , . . . , Am , while in the other stage we have a twomachine flow shop F2 consisting of two machines B and C in order. (Here, m is part of the input; when m is a fixed con-
B
Guohui Lin [email protected] Jianming Dong [email protected] Joshua Chang [email protected] Bing Su [email protected] Jueliang Hu [email protected]
1
Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou, Zhejiang, China
2
Department of Computing Science, University of Alberta, Edmonton, AB T6G 2E8, Canada
3
School of Economics and Management, Xi’an Technological University, Xi’an, Shaanxi, China
stant, the environment is usually denoted as O2(Pm, F2).) Let J = {J1 , J2 , . . . , Jn } denote the given set of jobs, where each job J j needs to be processed non-preemptively on any one of the parallel identical machines for a j time units, on machine B for b j time units and on machine C for c j time units. The constraint on the machine order for processing J j states that whenever J j enters F2, then it needs to be processed first on B, then on C, and then it can leave F2. Our objective is to minimize the makespan, which is the latest completion time among all jobs. This scheduling problem has not been studied in the literature, but it mirrors many applications with two (or more) independent processes, and one (or more) of them is a twostep (multi-step) sequential process. It is closely connected to several well-studied problems, in particular the k-stage hybrid open sh
Data Loading...
