Improved online algorithms for parallel job scheduling and strip packing

DOI10.1016/J.TCS.2009.05.033MaRDI QIDQ627112zbMATH OpenOpenAlexFDO

Authors Johann L. Hurink, Jacob Jan Paulus

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

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

Recommendations

• Online Algorithm for Parallel Job Scheduling and Strip Packing
• A note on online strip packing
• Structural Information and Communication Complexity
• On-line scheduling of parallel jobs in a list
• On an on-line scheduling problem for parallel jobs

Cites work

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

Cited in

(8)

• The generalization of scheduling with machine cost
• Approximation and online algorithms for multidimensional bin packing: a survey
• Improved upper bounds for online malleable job scheduling
• Online Algorithm for Parallel Job Scheduling and Strip Packing
• Online scheduling of malleable parallel jobs with setup times on two identical machines
• Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms
• Improved algorithms for online scheduling of malleable parallel jobs on two identical machines
• Online malleable job scheduling for \(m\leq 3\)

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

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