We discuss new approaches to the design of approximation algorithms for several NP-hard scheduling problems in which the objective is to minimize the average completion time.
If we schedule a set of jobs on a set of machines, each job j finishes at some time C(j); our goal is to minimize the (weighted) average of all the C(j). Minimizing this metric tends creates schedules with good throughput, i.e. many jobs are completed quickly.
If all the jobs are available at time 0 and there are no precedence constraints between the jobs, this problem is known to be solvable in polynomial time. Once we introduce release dates, or precedence constraints, or add weights to the jobs, the problem becomes NP-hard. Until about five years ago, no non-trivial approximation algorithms were known for even the “simplest” NP-hard average completion time problems. Over the past five years, there has been a flurry of activity in this area, and a large class of scheduling problems now have (small) constant-factor approximation algorithms, and some have polynomial-time approximation schemes.
A few fundamental underlying ideas have driven the work in this area. We will describe these ideas in the context of the “simplest” NP-hard average completion time problem: a set of jobs arrive over time (have release dates), and the objective is to minimize the average completion time. We will give three approximation algorithms for this problem: a 2-approximation which orders jobs based on a preemptive relaxation, a randomized e/(e-1)-approximation algorithm, and a polynomial-time approximation scheme. We will also describe briefly the experimental implications of these algorithms, and show how these ideas apply to more general problems such as those with parallel or unrelated machines, or precedence constraints among the jobs.
The work we discuss is mainly from several papers joint with Chandra Chekuri (Bell Labs), David Karger (MIT), Rajeev Motwani (Stanford), Balas Natarajan (HP), Cynthia Phillips (Sandia National Labs), and Joel Wein (Polytechnic).