New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Approximation algorithms for scheduling with a variable machine maintenance

SpeakerGuochuan Zhang

Co-author Lin Chen and Wenchang Luo

In this talk, we investigate the problem of scheduling weighted jobs on a single machine with a maintenance whose starting time is prior to a given deadline and the duration is an function of the starting time. We are asked not only to schedule the jobs but also the maintenance such that the total weighted job completion time is minimum. The problem is shown to be weakly NP-hard. In the case that the duration of the maintenance is a concave (and nondecreasing) function of its starting time, we provide two approximation algorithms with worst-case ratio of 2 and at most $1+\sqrt{2}/2+\epsilon$, respectively. Finally, for the general case, we present a fully polynomial time approximation scheme.