Scheduling Algorithms for Procrastinators

by: Michael A Bender, Raphael Clifford, Kostas Tsichlas

(14 Aug 2007)

View FullText article

arXiv (abstract), arXiv (PDF)

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

pdlug, rahul, austin, SRL (group)

Find related articles with these CiteULike tags

al, algorithm, algorithms, compsci, cs, different, interesting, math, procrastination, scheduling

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 Θ(1) approximation algorithm for the maximum interval stretch.

@misc{citeulike:1595770, 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.}, author = {Bender, Michael A. and Clifford, Raphael and Tsichlas, Kostas }, citeulike-article-id = {1595770}, eprint = {cs/0606067}, keywords = {al}, month = {Aug}, posted-at = {2007-08-27 09:01:58}, priority = {2}, title = {Scheduling Algorithms for Procrastinators}, url = {http://arxiv.org/abs/cs/0606067}, year = {2007} }

RIS record

TY - ELEC ID - citeulike:1595770 L3 - citeulike-article-id:1595770 TI - Scheduling Algorithms for Procrastinators N2 - 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. KW - al AU - Bender, Michael AU - Clifford, Raphael AU - Tsichlas, Kostas PY - 2007/Aug/14/ UR - http://arxiv.org/abs/cs/0606067 ER -

RIS BibTeX