Approximation algorithms for the three-machine proportionate mixed shop scheduling (Q2283006)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximation algorithms for the three-machine proportionate mixed shop scheduling |
scientific article |
Statements
Approximation algorithms for the three-machine proportionate mixed shop scheduling (English)
0 references
27 December 2019
0 references
The authors consider a mixed shop composed of a flow shop and an open shop sub-problem with three machines and the objective of minimizing the makespan, where each job has equal processing times on all three machines. For the case that the job with the largest processing time underlies the flow shop condition, a fully polynomial time approximation scheme is given (Section 3). If the largest job is of the open shop type, a 4/3-approximation algorithm is derived, and it is shown that this ratio is asymptotically tight (Section 4). However, the problem becomes NP-hard if there is only one open shop job which is strictly larger than any flow shop job which is proven by a reduction from the partition problem (Section 5). Finally, a fully polynomial time approximation scheme is given for the case of only one open shop job in the mixed shop (Section 6).
0 references
scheduling
0 references
mixed shop problem
0 references
fully polynomial time approximation scheme
0 references
approximation algorithm
0 references