# Single Scheduling of Equal-Length Jobs to Minimize the Average Flow Time,

or 1|r_{j};p_{j}=p;D_{j}|Σ C_{j}

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(n^{2}), which is implemented here.

## Input

## 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.