Periodic scheduling with obligatory vacations

We consider a problem of repeatedly scheduling n jobs on m parallel machines. Each job is associated with a profit that is gained each time the job is completed, and the goal is to maximize the average profit per time unit. Once the processing of a job is completed, it goes on vacation and returns to the system, ready to be processed again, only after its vacation is over. This problem has many applications: in production planning, machine maintenance, video-on-demand and database query processing, among others.We show that the problem is NP-hard already for jobs with unit processing times and unit profits, and develop approximation algorithms as well as optimal algorithms for certain subclasses of instances. We first show that a 5/3-approximation algorithm can be obtained for instances with unit processing times, using known results for windows scheduling. We then present a preemptive greedy algorithm, which yields a ratio of e/(e−1) to the optimal for general instances, with arbitrary processing times and arbitrary profits. For the special case where all jobs have the same (unit) processing times and the same (unit) profits, we present a 1.39-approximation algorithm. For this case we also show that, when the load generated by an instance is sufficiently large (in terms of n and m), any algorithm which uses no intended idle times yields an optimal schedule.