Single Scheduling of Equal-Length Jobs to Minimize the Average Flow Time,
or 1|rj;pj=p;Dj|Σ Cj

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 the same processing time p. We wish to find a feasible non-preemptive schedule on a single machine, which minimizes the sum over the completion times.

The problem can be solved in time O(n log n) with an algorithm by Garey, Johnson, Simons, Tarjan (1981). In this paper they first present a simpler algorithm running in time O(n2), which is implemented here.

Input

Processing time
Release times/deadlines for every job
output the schedule with one job per row
(otherwise all jobs in a same row)
zoom x2

Output

The shaded area represent the regions computed by the algorithm in which it is forbidden to start a job, because otherwise it would be impossible to complete all jobs before their deadlines.