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.