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

or P|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 *m*
processors, which minimizes the sum over the completion times.
The problem has been solved in 1978 by Barbara Simons who gave a greedy-backtrack algorithm running in time O(n^{3}loglog n). Recently Brucker and Kravchenko (2005), gave a different
algorithm for it. Based in their approach we provide an O(n^{4}) algorithm for
the problem, which is very simple to implement.

## Input

## Output