Faster Approximation Algorithms for Scheduling with Fixed Jobs

Jansen, K. Praedel, L., Schwarz, U. M. and Svensson, O.

We study the problem of scheduling jobs on identical parallel machines without preemption. In the consid- ered setting, some of the jobs are already assigned machines and starting times, for example due to external constraints not explicitly modelled. The objective is to assign the rest of the jobs in order to minimize the makespan. It is known that this problem cannot be approximated better than within a factor of 3/2 unless P = NP. An algorithm that achieves 3/2 + ε for any ε > 0 was presented by Diedrich and Jansen [DJ09], but its running time is doubly exponential in 1/ε. We present an improved algorithm with approximation ratio 3/2 and polynomial running time. We also give matching results for the related problem of scheduling with reservations. The new algorithm is both faster and conceptually simpler than the previously known algorithms.

Cite as: Jansen, K. Praedel, L., Schwarz, U. M. and Svensson, O. (2011). Faster Approximation Algorithms for Scheduling with Fixed Jobs. In Proc. Computing: The Australasian Theory Symposium (CATS 2011) Perth, Australia. CRPIT, 119. Alex Potanin and Taso Viglas Eds., ACS. 3-10

(from crpit.com) (local if available)