Multimachine Scheduling of Equal-Length Jobs to Minimize the Average Flow Time,
or P|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 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(n3loglog n). Recently Brucker and Kravchenko (2005), gave a different algorithm for it. Based in their approach we provide an O(n4) algorithm for the problem, which is very simple to implement.

Input

Processing time
Number of machines
Release times/deadlines for every job
output the schedule with one job per row and one color per machine
(otherwise one machine per row and one color per job)
zoom x2

Output