Scheduling algorithms for procrastinators

DOI10.1007/S10951-007-0038-4MaRDI QIDQ835586zbMATH OpenOpenAlexFDO

Authors Michael A. Bender, Raphaël Clifford, Kostas Tsichlas

Publication date 28 August 2009

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

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

zbMATH Keywords

NP-completeonline schedulingstretchhit-the-highest-nailinterval stretchprocrastinateprocrastinatorsum-of-squares problem

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Abstract: This paper presents scheduling algorithms for procrastinators, where the speed that a procrastinator executes a job increases as the due date approaches. We give optimal off-line scheduling policies for linearly increasing speed functions. We then explain the computational/numerical issues involved in implementing this policy. We next explore the online setting, showing that there exist adversaries that force any online scheduling policy to miss due dates. This impossibility result motivates the problem of minimizing the maximum interval stretch of any job; the interval stretch of a job is the job's flow time divided by the job's due date minus release time. We show that several common scheduling strategies, including the "hit-the-highest-nail" strategy beloved by procrastinators, have arbitrarily large maximum interval stretch. Then we give the "thrashing" scheduling policy and show that it is a Theta(1) approximation algorithm for the maximum interval stretch.

Recommendations

• scientific article; zbMATH DE number 2119737
• The lazy bureaucrat scheduling problem
• scientific article; zbMATH DE number 2185608
• Approximation algorithms for average stretch scheduling
• Algorithms and Data Structures

Cites work

• scientific article; zbMATH DE number 2185608 (Why is no real title available?)
• scientific article; zbMATH DE number 2089207 (Why is no real title available?)
• scientific article; zbMATH DE number 1303566 (Why is no real title available?)
• scientific article; zbMATH DE number 2079322 (Why is no real title available?)
• scientific article; zbMATH DE number 2086777 (Why is no real title available?)
• scientific article; zbMATH DE number 2086912 (Why is no real title available?)
• Algorithms for Scheduling Tasks on Unrelated Processors
• An efficient approximation algorithm for minimizing makespan on uniformly related machines.
• Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds
• Approximation and Online Algorithms
• Energy-Efficient Algorithms for Flow Time Minimization
• Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
• Minimizing the total weighted completion time of deteriorating jobs
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Online scheduling of parallel programs on heterogeneous systems with applications to Cilk
• STACS 2005
• Scheduling jobs with varying processing times
• Scheduling with time dependent processing times: Review and extensions
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
• Speed scaling to manage energy and temperature
• The lazy bureaucrat scheduling problem

Cited in

(5)

• scientific article; zbMATH DE number 1634827 (Why is no real title available?)
• Upper domination: complexity and approximation
• Online scheduling to minimize maximum response time and maximum delay factor
• The many facets of upper domination
• OL-DEC-MDP model for multiagent online scheduling with a time-dependent probability of success

This page was built for publication: Scheduling algorithms for procrastinators

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