Scheduling algorithms for procrastinators |
| |
Authors: | Michael A Bender Raphaël Clifford Kostas Tsichlas |
| |
Affiliation: | (1) Department of Computer Science, Stony Brook University, Stony Brook, NY 11794-4400, USA;(2) Department of Computer Science, University of Bristol, Merchant Venturers Building, Woodland Road, Bristol, BS8 1UB, UK;(3) Computer Engineering and Informatics Department, University of Patras, 26500 Patras, Greece |
| |
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.
Research of M.A. Bender was supported in part by NSF Grants CCR-0208670, CCF-0621439/0621425, CCF-0540897/05414009, CCF-0634793/0632838,
and CNS-0627645. |
| |
Keywords: | Hit-the-highest-nail Interval stretch NP-complete Online scheduling Procrastinate Procrastinator Stretch Sum-of-squares problem |
本文献已被 SpringerLink 等数据库收录! |
|