Scheduling algorithms for procrastinators

Scheduling algorithms for procrastinators

0.00 Avg rating0 Votes
Article ID: iaor20091005
Country: United Kingdom
Volume: 11
Issue: 2
Start Page Number: 95
End Page Number: 104
Publication Date: Apr 2008
Journal: Journal of Scheduling
Authors: , ,
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 offline 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, incluqmg 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 Θ(l) approximation algorithm for the maximum interval stretch.

Reviews

Required fields are marked *. Your email address will not be published.