Approximation algorithms for three-machine proportionate mixed shop scheduling
Full Text: 1-s2.0-S0304397519303858-main.pdf
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 , in which by “proportionate” each job has equal processing times on all three machines. Koulamas and Kyparisis (2015) [6] 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 first 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 then present a fully polynomial-time approximation scheme (FPTAS). On the negative side, while the 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.
Citation
L. Liu, Y. Chen, J. Dong, R. Goebel, G. Lin, Y. Luo, G. Ni, B. Su, Y. Xu, A. Zhang. "Approximation algorithms for three-machine proportionate mixed shop scheduling". Theoretical Computer Science, 803, pp 57-70, January 2020.| Keywords: | Scheduling, Mixed shop, Proportionate, Approximation algorithm, Fully polynomial-time approximation scheme |
| Category: | In Journal |
| Web Links: | DOI |
| Elsevier |
BibTeX
@article{Liu+al:20,
author = {Longcheng Liu and Yong Chen and Jianming Dong and Randy Goebel and
Guohui Lin and Yue Luo and Guanqun Ni and Bing Su and Yao Xu and An Zhang},
title = {Approximation algorithms for three-machine proportionate mixed shop
scheduling},
Volume = "803",
Pages = {57-70},
journal = {Theoretical Computer Science},
year = 2020,
}Last Updated: September 10, 2020Submitted by Sabina P
