On the complexity of preemptive open-shop scheduling problems

DOI10.1016/0167-6377(85)90035-5zbMath0565.90027OpenAlexW2063571792MaRDI 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-hardm-machine open shopoptimal flow-time schedulespreemptive open-shop scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (9)

On the complexity of preemptive openshop scheduling problems ⋮ 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 ⋮ Minimizing expected makespan in a two-machine stochastic open shop with Poisson arrival ⋮ 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. ⋮ On the open-shop problem with preemption and minimizing the average completion time ⋮ Scheduling preemptive open shops to minimize total tardiness ⋮ Scheduling ordered open shops

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

This page was built for publication: On the complexity of preemptive open-shop scheduling problems