Open-shop dense schedules: properties and worst-case performance ratio

DOI10.1007/s10951-009-0128-6zbMath1280.90037OpenAlexW1991396184MaRDI QIDQ2434260

Rongjun Chen, Zhongxian Men, Guochun Tang, Wanzhen Huang

Publication date: 5 February 2014

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-009-0128-6

zbMATH Keywords

schedulingconjectureperformance ratioopen-shopdense schedule

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches, Four decades of research on the open-shop scheduling problem to minimize the makespan, Three-machine open shop with a bottleneck machine revisited, Polynomial time approximation algorithms for proportionate open‐shop scheduling

Cites Work

• Unnamed Item
• Makespan minimization in open shops: A polynomial time approximation scheme
• A branch \(\&\) bound algorithm for the open-shop problem
• Two-stage open shop scheduling with a bottleneck machine
• A polynomial-time open-shop problem with an arbitrary number of machines
• A polynomial algorithm for the three-machine open shop with a bottleneck machine
• When difference in machine loads leads to efficient scheduling in open shops
• Open-shop scheduling problems with dominated machines
• Open Shop Scheduling to Minimize Finish Time
• Approximation Algorithms for Three-Machine Open Shop Scheduling
• Short Shop Schedules
• An Algorithm for the Open-Shop Problem
• How good is a dense shop schedule?
• Solving the open shop scheduling problem