Breaking 1 − 1/e barrier for non-preemptive throughput maximization

In this paper we consider one of the most basic scheduling problems where jobs have their respective arrival times and deadlines. The goal is to schedule as many jobs as possible non-preemptively by their respective deadlines on m identical parallel machines. For the last decade, the best approximation ratio known for the single machine case (m = 1) has been 1 − 1/e − ɛ ≈ 0.632 due to [Chuzhoy-Ostrovsky-Rabani, FOCS 2001 and MOR 2006]. We break this barrier and give an improved 0.644-approximation. For the multiple machine case, we give an algorithm whose approximation guarantee becomes arbitrarily close to 1 as the number of machines increases. This improves upon the previous best 1−1/(1+1/m)^m approximation due to [Bar-Noy et al., STOC 1999 and SICOMP 2009], which converges to 1−1/e as m goes to infinity. Our result for the multiple-machine case extends to the weighted throughput objective where jobs have different weights, and the goal is to schedule jobs with the maximum total weight. Our results show that the 1 − 1/e approximation factor widely observed in various coverage problems is not tight for the non-preemptive maximum throughput scheduling problem.