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

DOI10.1007/S11590-009-0163-4MaRDI QIDQ968014zbMATHOpenAlexWikidataFDO

Authors Ming Liu, Chengbin Chu, Feifeng Zheng, Yinfeng 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)

Recommendations

• On-line scheduling of two-machine open shops where jobs arrive over time
• An optimal online algorithm for scheduling two machines with release times
• Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines
• Tighter bounds on preemptive job shop scheduling with two machines
• On-line scheduling of small open shops

Cites work

• scientific article; zbMATH DE number 5345854 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1235242 (Why is no real title available?)
• 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
• New bounds and algorithms for on-line scheduling: two identical processors, known sum and upper bound on the tasks
• On-line scheduling of small open shops
• Open Shop Scheduling to Minimize Finish Time
• Scheduling algorithms
• 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
• Solving job shop scheduling problems utilizing the properties of backbone and ``big valley

Cited in

(4)

• Tighter bounds on preemptive job shop scheduling with two machines
• On-line two-machine open shop scheduling with time lags
• Four decades of research on the open-shop scheduling problem to minimize the makespan
• Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q968014)