Speedscaling Scheduling

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. :-(

Input

alpha
Release times/deadlines/workload for every job

Output

wj=workload of job j, C=completion time, E=energy