Improved online algorithms for parallel job scheduling and strip packing

DOI10.1016/j.tcs.2009.05.033zbMath1206.68373OpenAlexW2028810820MaRDI QIDQ627112

Jacob Jan Paulus, Johann L. Hurink

Publication date: 21 February 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.05.033

zbMATH Keywords

competitive analysisstrip packingonline schedulingparallel jobs

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27)

Related Items (6)

Improved Algorithms for Online Scheduling of Malleable Parallel Jobs on Two Identical Machines ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ The generalization of scheduling with machine cost ⋮ Improved upper bounds for online malleable job scheduling ⋮ Online malleable job scheduling for \(m\leq 3\) ⋮ Online scheduling of malleable parallel jobs with setup times on two identical machines

Cites Work

• Scheduling parallel jobs to minimize the makespan
• Online scheduling of parallel jobs on two machines is 2-competitive
• On-line scheduling of parallel jobs in a list
• A note on online strip packing
• Lower bounds for on-line two-dimensional packing algorithms
• Shelf Algorithms for Two-Dimensional Packing Problems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

This page was built for publication: Improved online algorithms for parallel job scheduling and strip packing