2018/09/15 by Longcheng Liu, Yong Chen, Liu, Longcheng +15
Computer Science · Engineering · #Optimization and Packing Problems #Optimization and Search Problems #Scheduling and Optimization Algorithms #cs.DS
paper · pdf · doi:10.48550/arxiv.1809.05745
An extended abstract containing a subset of results has been accepted by AAIM 2018. This is the full version with 20 pages, 14 figures
arxiv created 2018/09/15 · arxiv updated 2018/09/18
A mixed shop is a manufacturing infrastructure designed to process a mixture of a set of flow-shop jobs and a set of open-shop jobs. Mixed shops are in general much more complex to schedule than flow-shops and open-shops, and have been studied since the 1980's. We consider the three machine proportionate mixed shop problem denoted as M3 | prpt | Cmax, in which each job has equal processing times on all three machines. Koulamas and Kyparisis [\it European Journal of Operational Research, 243:70--74,2015] showed that the problem is solvable in polynomial time in some very special cases; for the non-solvable case, they proposed a 5/3-approximation algorithm. In this paper, we present an improved 4/3-approximation algorithm and show that this ratio of 4/3 is asymptotically tight; when the largest job is a flow-shop job, we present a fully polynomial-time approximation scheme (FPTAS). On the negative side, while the F3 | prpt | Cmax problem is polynomial-time solvable, we show an interesting hardness result that adding one open-shop job to the job set makes the problem NP-hard if this open-shop job is larger than any flow-shop job. We are able to design an FPTAS for this special case too.