Speedscaling Scheduling with powerdown states

We are given n jobs. Each job has a release time before which it is not available, a strict deadline by which it has to complete, and each job has some workload. We have 3 constant parameters L,g and α. A schedule determines when the computer must be on, and if on, at what speed it schedules which job, or if it is idle. The cost of turning the computer on is L. The cost of executing at speed s is sα+g per time unit. The goal is to find a schedule that minimizes total speed.

We present here an O(n3) algorithm for the special case of agreeable deadline instances (when jobs can be orderd such that both release times and deadlines increase).


Release times/deadlines/workload for every job