On the complexity of preemptive open-shop scheduling problems

DOI10.1016/0167-6377(85)90035-5zbMath0565.90027MaRDI QIDQ1058969

C. Y. Liu, Robert L. Bulfin

Publication date: 1985

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(85)90035-5

zbMATH Keywords

NP-hard; m-machine open shop; optimal flow-time schedules; preemptive open-shop scheduling

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

Related Items

Scheduling ordered open shops, On the open-shop problem with preemption and minimizing the average completion time, Scheduling preemptive open shops to minimize total tardiness, Minimizing expected makespan in a two-machine stochastic open shop with Poisson arrival, On the complexity of preemptive openshop scheduling problems, Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, An efficient tabu search approach for the two-machine preemptive open shop scheduling problem., Scheduling two-machine preemptive open shops to minimize total completion time, Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop

Cites Work

• Unnamed Item
• Unnamed Item
• A Note on Open Shop Preemptive Schedules
• Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops
• Scheduling the Open Shop to Minimize Mean Flow Time
• Minimizing Maximum Lateness in a Two-Machine Open Shop
• Unit Execution Time Shop Problems
• Open Shop Scheduling to Minimize Finish Time
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• An Algorithm for the Open-Shop Problem