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

or P|r_{j};pmtn;p_{j}=p|Σ C_{j}

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

## Output