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

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