An optimal online algorithm for two-machine open shop preemptive scheduling with bounded processing times

DOI10.1007/s11590-009-0163-4zbMath1190.90072OpenAlexW2080478733WikidataQ57185725 ScholiaQ57185725MaRDI QIDQ968014

Ming Liu, Feifeng Zheng, Chengbin Chu, Yin-Feng Xu

Publication date: 3 May 2010

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-009-0163-4

zbMATH Keywords

competitive analysis

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (2)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving job shop scheduling problems utilizing the properties of backbone and ``big valley
• An algorithm for the job shop scheduling problem based on global equilibrium search techniques
• Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times
• Semi on-line scheduling on two identical machines
• Semi-on-line scheduling on two parallel processors with an upper bound on the items
• Semi-online scheduling jobs with tightly-grouped processing times on three identical machines
• Open Shop Scheduling to Minimize Finish Time
• On-line scheduling of small open shops

This page was built for publication: An optimal online algorithm for two-machine open shop preemptive scheduling with bounded processing times