# Scheduling Algorithms for Procrastinators

**Authors:** Michael A. Bender, Raphael Clifford, Kostas Tsichlas  
**arXiv:** [cs/0606067](https://arxiv.org/abs/cs/0606067)  
**Date:** 2006-06-14  
**Summary page:** https://www.summarizepaper.com/en/paper/cs--0606067v2/

## Key points

- The paper presents scheduling algorithms for procrastinators, where the speed of executing a job increases as the due date approaches.
- Optimal off-line scheduling policies are provided for linearly increasing speed functions and computational/numerical issues involved in implementing this policy are explained.
- The online setting is explored and it is shown that there exist adversaries that force any online scheduling policy to miss due dates.
- The problem of minimizing the maximum interval stretch of any job is introduced, which is defined as the job's flow time divided by the difference between its due date and release time.
- Several common scheduling strategies have arbitrarily large maximum interval stretches, including "hit-the-highest-nail" strategy beloved by procrastinators.
- A new scheduling policy called "thrashing" is introduced and proved to be a $\Theta(1)$ approximation algorithm for minimizing the maximum interval stretch.
- This paper provides valuable insights into how to effectively schedule tasks for procrastinators while highlighting some of the challenges associated with doing so in an online setting.
- The authors' findings have important implications for individuals who struggle with procrastination as well as organizations seeking to optimize their operations through efficient task scheduling.

## Summary

This paper by Michael A. Bender, Raphael Clifford, and Kostas Tsichlas presents scheduling algorithms for procrastinators, where the speed at which a procrastinator executes a job increases as the due date approaches. The authors provide optimal off-line scheduling policies for linearly increasing speed functions and explain the computational/numerical issues involved in implementing this policy. The paper then explores the online setting and shows 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 defined as the job's flow time divided by the difference between its due date and release time. The authors show that several common scheduling strategies, including the "hit-the-highest-nail" strategy beloved by procrastinators, have arbitrarily large maximum interval stretches. To address this issue, they introduce a new scheduling policy called "thrashing" and prove that it is a $\Theta(1)$ approximation algorithm for minimizing the maximum interval stretch. Overall, this paper provides valuable insights into how to effectively schedule tasks for procrastinators while highlighting some of the challenges associated with doing so in an online setting. The authors' findings have important implications for individuals who struggle with procrastination as well as organizations seeking to optimize their operations through efficient task scheduling.