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.
There is a constant parameter α between 2 and 3.
A schedule determines when to schedule which job at what speed. The cost of executing at speed s is sα per time unit. The goal is to find a schedule that minimizes total cost.
This is the implementation of the
O(n3) algorithm by Yao, Demers, Shenker that solves this problem.
There is a O(n2 log n) algorithm for the same problem, but we were too lazy to implement it. :-(
wj=workload of job j, C=completion time, E=energy