A PTAS for non-resumable open shop scheduling with an availability constraint

DOI10.1007/s10878-021-00773-7zbMath1490.90260OpenAlexW3182289662MaRDI QIDQ2125217

Yan Lan, Xin Han, Ning Ding, Yuan Yuan

Publication date: 13 April 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-021-00773-7

zbMATH Keywords

approximation algorithmopen shop schedulingpolynomial time approximation schememachine non-availability

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Related Items

Open shop scheduling problem with a non-resumable flexible maintenance period

Cites Work

• Unnamed Item
• A PTAS for a particular case of the two-machine flow shop with limited machine availability
• A polynomial-time approximation scheme for the two machine flow shop problem with several availability constraints
• Two-machine flow shop and open shop scheduling problems with a single maintenance window
• Approximation results for flow shop scheduling problems with machine availability constraints
• An improved heuristic for two-machine flow shop scheduling with an availability constraint and nonresumable jobs
• A greedy open shop heuristic with job priorities
• Makespan minimization in open shops: A polynomial time approximation scheme
• Two-machine flowshop scheduling with availability constraints
• Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function
• Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint
• Non-preemptive two-machine open shop scheduling with non-availability constraints
• An improved heuristic for two-machine flowshop scheduling with an availability constraint
• An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint
• A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint
• Machine scheduling with an availability constraint
• Optimal two- and three-stage production schedules with setup times included
• An FPTAS for scheduling a two-machine flowshop with one unavailability interval
• Polynomial-time approximation schemes for two-machine open shop scheduling with nonavailability constraints
• Open Shop Scheduling to Minimize Finish Time
• Approximation Algorithms for Three-Machine Open Shop Scheduling
• A dynamic programming algorithm for scheduling jobs in a two-machine open shop with an availability constraint
• An NP-Hard Open Shop Scheduling Problem with Polynomial Average Time Complexity
• Scheduling jobs in open shops with limited machine availability
• Two-machine open shop scheduling with an availability constraint
• Two-machine flow shops with limited machine availability