Online scheduling of parallel jobs on two machines is 2-competitive

DOI10.1016/J.ORL.2007.06.001zbMath1138.90007OpenAlexW2119760147MaRDI QIDQ924886

Jacob Jan Paulus, Johann L. Hurink

Publication date: 29 May 2008

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

Full work available at URL: https://doi.org/10.1016/j.orl.2007.06.001

zbMATH Keywords

competitive analysisonline schedulingparallel jobs

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (18)

Online over time processing of combinatorial problems ⋮ Online scheduling of two type parallel jobs on identical machines ⋮ Improved Algorithms for Online Scheduling of Malleable Parallel Jobs on Two Identical Machines ⋮ A new lower bound for online strip packing ⋮ A tight analysis of Brown-Baker-Katseff sequences for online strip packing ⋮ The generalization of scheduling with machine cost ⋮ Online multiple-strip packing ⋮ Improved online algorithms for parallel job scheduling and strip packing ⋮ Unnamed Item ⋮ WORST-CASE PERFORMANCE EVALUATION ON MULTIPROCESSOR TASK SCHEDULING WITH RESOURCE AUGMENTATION ⋮ New upper bounds for online strip packing ⋮ A new upper bound for the online square packing problem in a strip ⋮ Online scheduling of malleable parallel jobs with setup times on two identical machines ⋮ Online Algorithm for Parallel Job Scheduling and Strip Packing ⋮ On-line scheduling of multi-core processor tasks with virtualization ⋮ ONLINE SCHEDULING OF PARALLEL JOBS WITH BOUNDED PROCESSING TIMES ON TWO MACHINES ⋮ A note on online strip packing ⋮ Improved lower bound for online strip packing

Cites Work

• Unnamed Item
• Scheduling parallel jobs to minimize the makespan
• On-line scheduling of parallel jobs on two machines
• Online algorithms: a survey
• Structural Information and Communication Complexity

This page was built for publication: Online scheduling of parallel jobs on two machines is 2-competitive