Approximation algorithms for the three-machine proportionate mixed shop scheduling

DOI10.1016/J.TCS.2019.05.036MaRDI QIDQ2283006zbMATHOpenAlexWikidataFDO

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

Publication date 27 December 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.05745

zbMATH Keywords

approximation algorithmschedulingfully polynomial time approximation schememixed shop problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

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 $M3midprptmid{C}_{max}$, 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 $F3midprptmid{C}_{max}$ 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.

Recommendations

• Approximation algorithms and a hardness result for the three-machine proportionate mixed shop
• Approximation Algorithms for Three-Machine Open Shop Scheduling
• A new three-machine shop scheduling: complexity and approximation algorithm
• An approximation algorithm for scheduling on three dedicated machines
• The three-machine proportionate open shop and mixed shop minimum makespan problems
• A 3/2-Approximation for the Proportionate Two-Machine Flow Shop Scheduling with Minimum Delays
• An approximate algorithm for the three-machine problem
• scientific article; zbMATH DE number 1497368
• Three-machine shop scheduling with partially ordered processing routes
• Algorithms – ESA 2005

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1104339 (Why is no real title available?)
• Complexity of mixed shop scheduling problems: A survey
• Focused Scheduling in Proportionate Flowshops
• On J -maximal and J -minimal Flow-Shop Schedules
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Review of the ordered and proportionate flow shop scheduling research
• Scheduling algorithms
• Scheduling ordered open shops
• Scheduling two jobs with fixed and nonfixed routes
• Shop-scheduling problems with fixed and non-fixed machine orders of the jobs
• The mixed shop scheduling problem
• The three-machine proportionate open shop and mixed shop minimum makespan problems
• Two-Machine Super-Shop Scheduling Problem

Cited in

(5)

• On the complexity of proportionate open shop and job shop problems
• Approximation algorithms and a hardness result for the three-machine proportionate mixed shop
• The LPT heuristic for minimizing total load on a proportionate openshop
• The three-machine proportionate open shop and mixed shop minimum makespan problems
• Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches

This page was built for publication: Approximation algorithms for the three-machine proportionate mixed shop scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2283006)