Competitive design and analysis for machine-minimizing job scheduling problem

DOI10.1007/978-3-642-35261-4_11MaRDI QIDQ4909524zbMATH OpenOpenAlexFDO

Authors Mong-Jen Kao, Jian-Jia Chen, Ignaz Rutter, Dorothea Wagner

Publication date 21 March 2013

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.5697

Mathematics Subject Classification ID

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

Abstract: We explore the machine-minimizing job scheduling problem, which has a rich history in the line of research, under an online setting. We consider systems with arbitrary job arrival times, arbitrary job deadlines, and unit job execution time. For this problem, we present a lower bound 2.09 on the competitive factor of emph{any} online algorithms, followed by designing a 5.2-competitive online algorithm. We also point out a false claim made in an existing paper of Shi and Ye regarding a further restricted case of the considered problem. To the best of our knowledge, what we present is the first concrete result concerning online machine-minimizing job scheduling with arbitrary job arrival times and deadlines.

Recommendations

• An O( m)-competitive algorithm for online machine minimization
• An \(\mathcal{O}(\log m)\)-competitive algorithm for online machine minimization
• Online scheduling of parallel jobs on two machines is 2-competitive
• New upper and lower bounds for online scheduling with machine cost
• Competitive analysis of a better on-line algorithm to minimize total completion time on a single-machine

Cited in

(9)

• Online scheduling of time-critical tasks to minimize the number of calibrations
• Efficient algorithms for scheduling parallel jobs with interval constraints in clouds
• Online machine minimization with lookahead
• Online dynamic power management with hard real-time guarantees
• An improved algorithm for online machine minimization
• scientific article; zbMATH DE number 5521829 (Why is no real title available?)
• An O( m)-competitive algorithm for online machine minimization
• An \(\mathcal{O}(\log m)\)-competitive algorithm for online machine minimization
• Exploring a resolution method based on an evolutionary game-theoretical model for minimizing the machines with limited workload capacity and interval constraints

This page was built for publication: Competitive design and analysis for machine-minimizing job scheduling problem

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