Approximation algorithms for the three-machine proportionate mixed shop scheduling (Q2283006)

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).