Approximation algorithms for the three-machine proportionate mixed shop scheduling

DOI10.1016/J.TCS.2019.05.036MaRDI QIDQ2283006zbMATH OpenOpenAlexWikidataFDO

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 algorithmfully polynomial time approximation schememixed shop problemscheduling

Mathematics Subject Classification ID

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

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.

Review text

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

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

• Complexity of mixed shop scheduling problems: A survey
• Focused Scheduling in Proportionate Flowshops
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1104339 (Why is no real title available?)
• 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)

• Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches
• The three-machine proportionate open shop and mixed shop minimum makespan 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
• On the complexity of proportionate open shop and job shop problems

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)