Improved approximation algorithms for two-stage flexible flow shop scheduling
- PDF / 496,299 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 70 Downloads / 223 Views
Improved approximation algorithms for two-stage flexible flow shop scheduling Anzhen Peng1 · Longcheng Liu1 · Weifeng Lin1 Accepted: 29 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract A two-stage flexible flow shop scheduling is a manufacturing infrastructure designed to process a set of jobs, in which a single machine is available at the first stage and m parallel machines are available at the second stage. At the second stage, each task can be processed by multiple parallel machines. The objective is to minimize the maximum job completion time, i.e., the makespan. Sun et al. (J Softw 25:298–313, 2014) presented an O(n log n)-time 3-approximation algorithm for F2(1, Pm) | si zei | Cmax under some special conditions. Zhang et al. (J Comb Optim 39:1–14, 2020) presented a 2.5-approximation algorithm for F2(1, P2) | linei | Cmax and a 2.67-approximation algorithm for F2(1, P3) | linei | Cmax , which both run in linear time. In this paper, we achieved following improved results: for F2(1, P2) | linei | Cmax , we present an O(n log n)-time 2.25-approximation algorithm, for F2(1, P3) | linei | Cmax , we present an O(n log n)-time 7/3-approximation algorithm, for F2(1, Pm) | si zei | Cmax with the assumption min1≤i≤n { p1i } ≥ max1≤i≤n { p2i }, we present a linear time optimal algorithm. Keywords Scheduling · Two-stage flow shop · Approximation algorithm · Optimal algorithm
1 Introduction We study the following two-stage flexible flow shop scheduling problem, denoted as F2(1, Pm) | si zei | Cmax or F2(1, Pm) | linei | Cmax in the three field notation (Graham et al. 1979). Given a job set J = {J1 , J2 , . . . , Jn } and a two-stage flow
This research is supported by the Fundamental Research Funds for the Central Universities (Grant No. 20720190068).
B 1
Longcheng Liu [email protected] School of Mathematical Sciences, Xiamen University, Xiamen 361005, People’s Republic of China
123
Journal of Combinatorial Optimization
shop where there are a single machine at the first stage and m parallel machines at the second stage. Each job has to be processed non-preemptively on the only one machine of the first stage. After it has been finished in the first stage, it has to be processed non-preemptively on one or multiple parallel machines of the second stage. Each job Ji can be charactered as ( p1i , p2i , si zei /linei ), where p1i means the processing time at the first stage, p2i means the processing time at the second stage and si zei or linei means the number of required parallel machines at the second stage, particularly, linei represents the contiguous machine assignments at the second stage. The objective is to minimize the maximum job completion time, i.e., the makespan. The scheduling constraint is as usual, that is at every time point, a job can be processed by at most one machine and a machine can process at most one job. Flexible flow shop scheduling problems have many real-life applications: many discrete manufacturing industries have a flow shop architecture wh
Data Loading...