Preemptive Scheduling to Minimize Energy,
or 1|rj;pmtn|E

We are given n jobs. Each job has a release time before which it is not available, a processing time and a strict deadline by which it has to complete. We wish to find a preemptive schedule on a single machine, which minimizes the consumed energy: if a gap (maximal idle time interval) is long enough we shut the machine down during the gap. Formally the cost of a gap of a gap of length k is the minimum of k and L, for a given boot-time L, and the cost of a schedule is the total cost of its gaps.

Input

release time/processing time/deadline for every job
Boot-time L

Output

The optimal schedule, and below for every job, the interval spanned between its release time and its deadline. The black prefix of the interval indicates the processing time of the job. The red number inside each gap indicates its cost.

[src, all]