Approximation Algorithms for Machine Minimization

In this paper we consider a classic scheduling problem known as Machine Minimization (MM). The input to MM is a set J of n jobs, where each job j has processing time p_j, release time r_j, and deadline d_j. The goal is to schedule the jobs to run non-preemptively on minimum number of machines such that each job is fully scheduled within its [r_j,d_j] interval and each machine runs at most one job at a time. This problem generalizes several NP-hard problems (e.g. the case of identical release time and deadlines reduces to the bin packing problem). Using Randomized Rounding [Prabhakar Raghavan and Clark D. Thompson, 1987] one can get an O((log n)/(log log n))-approximation. Chuzhoy et al. [Julia Chuzhoy and Paolo Codenotti, 2009] presented an algorithm that uses O(opt²) machines (i.e. O(opt)-approximation). Combined with the earlier work this yields an O(√{(log n)/(log log n)})-approximation and this remains the best known result for over 20 years. Even for when the ratio of largest to smallest processing time p_{max}/p_{min} is bounded, or the number of distinct processing times are bounded, there is no (universal) constant approximation. In this paper, we present a number of results. When p_max/p_min = ρ we present an algorithm that yields an asymptotic (2+ε)-approximation in time n^{O(ρ⁴/ε⁴)}. When the number of distinct processing times is c, we present a 2-approximation with run time n^{O(c²log³ n)}. If we have c distinct processing times and p_max/p_min = ρ we present an asymptotic (1+ε)-approximation that runs in time n^O(c²⋅ρ²⋅log³n/ε²).