Approximation algorithms for the three-machine proportionate mixed shop scheduling

Longcheng Liu, Yong Chen, Jianming Dong, Randy Goebel, Guohui Lin, Yue Luo, Guanqun Ni, Bing Su, Yao Xu, An Zhang

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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

Original languageEnglish
Pages (from-to)57-70
Number of pages14
JournalTheoretical Computer Science
Volume803
DOIs
StatePublished - Jan 10 2020

Scopus Subject Areas

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Approximation algorithm
  • Fully polynomial-time approximation scheme
  • Mixed shop
  • Proportionate
  • Scheduling

Fingerprint

Dive into the research topics of 'Approximation algorithms for the three-machine proportionate mixed shop scheduling'. Together they form a unique fingerprint.

Cite this