Scheduling to Minimize Total Response Time

Abstract

Consider the following basic non-preemptive scheduling problem. You have one machine and a set of jobs that arrive at different times and have different processing times. The response time of a job is the time between when it arrives in the system and when it completes processing. The objective is to minimize the total response time, or equivalently, the average response time.

Unfortunately, this problem is NP-hard. Moreover, unless P=NP, there is no polynomial time algorithm that can even approximate this problem to within a sqrt(n) factor, where n is the total number of jobs. Yet this problem, and many variants and generalizations are fundamental scheduling problems, and we need ways to design and analyze algorithms for these problems.

In this talk, we give new algorithms and an analysis based on resource augmentation. That is, we give our algorithms some extra resources, and compare them to optimal algorithms that do not have these additional resources. In the language of resource augmentation, we give the first constant-speed, constant-approximation polynomial-time algorithms for several nonpreemptive min-sum scheduling problems where jobs arrive over time and must be processed on one machine, including weighted response time, total tardiness, throughput maximization and the broadcast scheduling version of response time.

Our main technical contribution is a new integer programming formulation whose relaxation is sufficiently close to the integer optimum, and which can be transformed to a schedule on a faster machine.

Joint work with Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, and Baruch Schieber. No prior knowledge of scheduling or resource augmentation will be assumed in this talk.