Energy optimal schedules for jobs with multiple active intervals

In this paper, we study the scheduling problem of jobs with multiple active intervals. Each job in the problem instance has disjoint active time intervals where it can be executed and a workload characterized by the required number of CPU cycles. Previously, people studied multiple interval job scheduling problem where each job must be assigned enough CPU cycles in one of its active intervals. We study a different practical version where the partial work done by the end of an interval remains valid and each job is considered finished if total CPU cycles assigned to it in all its active intervals reach the requirement. The goal is to find a feasible schedule that minimizes energy consumption. By adapting the algorithm for single interval jobs proposed in Yao, Demers and Shenker (1995) [1], one can still obtain an optimal schedule. However, the two phases in that algorithm (critical interval finding and scheduling the critical interval) can no longer be carried out directly. We present polynomial time algorithms to solve the two phases for jobs with multiple active intervals and therefore can still compute the optimal schedule in polynomial time.