Approximation algorithms for the three-machine proportionate mixed shop scheduling

DOI10.1016/J.TCS.2019.05.036zbMATH Open1444.90055arXiv1809.05745OpenAlexW2953662409WikidataQ127565663 ScholiaQ127565663MaRDI QIDQ2283006FDOQ2283006

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)

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.

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

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

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)

Cites Work

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

Cited In (4)

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

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)