Improved upper bounds for online malleable job scheduling

DOI10.1007/S10951-014-0406-9MaRDI QIDQ892840zbMATH OpenOpenAlexFDO

Authors Nathaniel Kell, Jessen T. Havill

Publication date 12 November 2015

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10951-014-0406-9

zbMATH Keywords

online algorithmsschedulingidentical machinesparallel jobsoverhead time

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Online malleable job scheduling for m 3
• Online scheduling of malleable parallel jobs
• Improved algorithms for online scheduling of malleable parallel jobs on two identical machines
• Competitive online scheduling of perfectly malleable jobs with setup times
• Improved randomized online scheduling of intervals and jobs
• Improved Bounds for the Online Scheduling Problem
• New lower and upper bounds for on-line scheduling
• Online scheduling of bounded length jobs to maximize throughput
• Online Scheduling of Bounded Length Jobs to Maximize Throughput
• Improved Randomized Online Scheduling of Unit Length Intervals and Jobs

Cites work

• scientific article; zbMATH DE number 4130003 (Why is no real title available?)
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• A 2.5 times optimal algorithm for packing in two dimensions
• A note on online strip packing
• Bounds for Multiprocessor Scheduling with Resource Constraints
• Bounds on Multiprocessing Timing Anomalies
• Competitive online scheduling of perfectly malleable jobs with setup times
• Complexity of Scheduling Parallel Task Systems
• Improved Lower Bound for Online Strip Packing
• Improved online algorithms for parallel job scheduling and strip packing
• Malleable scheduling for flows of jobs and applications to MapReduce
• New algorithms for an ancient scheduling problem.
• New lower and upper bounds for on-line scheduling
• On an on-line scheduling problem for parallel jobs
• On-line scheduling of parallel jobs
• On-line scheduling of parallel jobs in a list
• Online malleable job scheduling for m 3
• Online scheduling of malleable parallel jobs
• Online scheduling of malleable parallel jobs with setup times on two identical machines
• Orthogonal Packings in Two Dimensions
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Scheduling parallel jobs to minimize the makespan
• Smart SMART Bounds for Weighted Response Time Scheduling

Cited in

(9)

• Improved competitive algorithms for online scheduling with partial job values
• Malleable scheduling beyond identical machines
• Online scheduling of malleable parallel jobs
• Decentralized Online Scheduling of Malleable NP-hard Jobs
• Online scheduling of moldable parallel tasks
• Improved algorithms for online scheduling of malleable parallel jobs on two identical machines
• Competitive online scheduling of perfectly malleable jobs with setup times
• Online malleable job scheduling for m 3
• Efficient approximation algorithms for scheduling moldable tasks

Describes a project that uses

Uses Software

• NAS Parallel Benchmarks

This page was built for publication: Improved upper bounds for online malleable job scheduling

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