Preemptive Multimachine Scheduling of Equal-Length Jobs to Minimize the Average Flow Time,
or P|rj;pmtn;pj=p|Σ Cj

Joint work with with Philippe Baptiste, Peter Brucker, Marek Chrobak, Svetlana A. Kravchenko and Francis Sourd.

We are given n jobs. Each job has a release time before which it is not available, and each job has the same processing time p. We wish to find a preemptive schedule on m processors, which minimizes the sum over the completion times.

The special case for two processors was shown to be solvable in polynomial time by Herrbach and Leung in 1990. The problem for an arbitrary number of machines, was shown to be polynomialy solvable by Brucker and Kravchenko in 2004. We found a simpler linear program caracterisation of the problem of size O(nm). Here is an implementation of it. We generate the linear program from the input (processing time, number of machines, release times), give to an LP solver and produce the picture of the resulting schedule. If "output in normal form" is checked, the schedule is shown as produced by the linear program. Otherwise the schedule is converted into an irreducible form and jobs are reassigned to machines in order to avoid unneccesary preemptions.

Input

Processing time
Number of machines
Release times
output the schedule in normal form
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