# Minimizing total waiting time in preemptive equal job length scheduling
or 1|r_{j};p_{j}=p;pmtn|Σ w_{j}C_{j}

This is an open problem. If you make some progress it would be nice to let us know: Ph. Baptiste, Marek Chrobak, C. Dürr, Jiri Sgall. The notes above are not ready papers, but rough research drafts.
We are given *n* jobs. Each job *j* has a release time *r*_{j} before
which it is not available, a priority weight *w*_{j}
and each job has the same processing
time *p*.
Without loss of generality we assume that jobs are indexed according to their release times, that is *r*_{1} <=...<=r_{n}.
A preemptive schedule is a mapping which associates to every job a sequence of time intervals of total length *p*.
For technical reasons the intervals are closed at the beginning and open at the end. All intervals -- including those of different jobs -- have to be disjoint. To be feasible the smallest starting time of the intervals associated to job *j* must be not earlier than *r*_{j}. The latest ending time of the intervals is called the completion time of job *j* and denoted *C*_{j}.
We wish to find a feasible preemptive schedule on one machine, which minimizes the total weighted completion time, which is defined as *Σ w*_{j} C_{j}.

r1=0 r2=1 r3=3 r4=4 p=3
|___________________________________ w1=3
|_________________________________ w2=100
|_____________________________ w3=3
|___________________________ w4=10
|1|2 2 2|4 4 4|1 1|3 3 3| optimal schedule of cost 521

Fig 1: an example of an optimal schedule
## Conjecture: the time-indexed linear program has always an integer optimum

It is easy to model the problem as an integer linear program with 0-1 variables *X*_{i,t}, where *X*_{i,t}=1 indicates that job *i* completes at time *t*. This linear program has two kind of natural constraints, (1) saying that a job completes eventually at some point not earlier than *r*_{i}+p,
and (2) that for any time interval *[s,t]* the number of jobs that are fully executed (the sum of *X*_{i,u} over *u* in *[s,t]* and over *i* such that *r*_{i} ≥= s ) is at most *(t-s)/p*.

The conjecture is that the relaxed linear program (where you removed the integrality constraint) has always an integer solution. The linear program is not totally unimodular, that is the simplex described by it might have some fractional vertices, but there is still hope that in the direction of the objective function, there is always an integer vertex. This property of a linear program may sound strange to you, but it happens sometimes, see [Durr,Hurand'06:Finding total...].

In fact we were able to show this conjecture for the special case when *r*_{j}=j-1 and *p=n*. This proof lead us to the dynamic program below.

## A dynamic program for the special case *p>max r*_{j}

## A simple open special case

If you try to find a polynomial algorithm for this problem, the simplest special case to start with could be to assume *r*_{j}=j and *p=2* and arbitrary weights of course.