Scheduling Algorithms for Procrastinators

Details Scheduling Algorithms for Procrastinators Scheduling Algorithms for Procrastinators

2006-06-14

arxiv.org/abs/cs/0606067v2

Computer Science

Data Structures and Algorithms

12 pages, 3 figures

Scientific paper

10.1007/s10951-007-0038-4

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.

Affiliated with

Also associated with

No associations

Rating

Scheduling Algorithms for Procrastinators does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Scheduling Algorithms for Procrastinators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduling Algorithms for Procrastinators will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-196939