Breaking 1 - 1 barrier for nonpreemptive 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 nonpreemptively 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, and 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 nonpreemptive maximum throughput scheduling problem.