Non-preemptive Throughput Maximization for Speed-Scaling with Power-Down

We consider the problem of scheduling a set of n jobs on a single processor. Each job is characterized by its release date r_j, its deadline d_j and its processing volume p_j. The processor can vary its speed and can switch into a sleep state in order to reduce its energy consumption. No energy is consumed in this state, but a fixed amount of energy, equal to L, is required for a transition from the sleep state to the active state. Here, we study the throughput maximization version of the problem where we are given a budget of energy E and our goal is to determine a feasible schedule maximizing the number of jobs that are executed between their respective release dates and deadlines without preemption. We first consider the case in which jobs have agreeable deadlines, i.e. for every pair of jobs i and j, one has r_i ≤ r_j  if and only if d_i ≤ d_j. Then we consider the case where the jobs have arbitrary release dates and deadlines, but the same processing volume. We propose polynomial-time algorithms for both cases.