Improved Algorithms for Online Scheduling of Malleable Parallel Jobs on Two Identical Machines

DOI10.1142/S0217595915500347zbMath1330.90040MaRDI QIDQ3455878

Ping Zhou, Hao Zhou, Yiwei Jiang

Publication date: 11 December 2015

Published in: Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

competitive ratiomakespanonline algorithmmalleable parallel job

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)

Cites Work

• Scheduling malleable tasks with precedence constraints
• Improved online algorithms for parallel job scheduling and strip packing
• 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
• On-line scheduling of parallel jobs on two machines
• Online scheduling of malleable parallel jobs with setup times on two identical machines
• A note on online strip packing
• A dominant class of schedules for malleable jobs in the problem to minimize the total weighted completion time
• Scheduling malleable parallel tasks: an asymptotic fully polynomial time approximation scheme
• Online malleable job scheduling for \(m\leq 3\)
• Competitive online scheduling of perfectly malleable jobs with setup times

This page was built for publication: Improved Algorithms for Online Scheduling of Malleable Parallel Jobs on Two Identical Machines