Minimizing total waiting time in preemptive equal job length scheduling or 1|rj;pj=p;pmtn|Σ wjCj

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 rj before which it is not available, a priority weight wj 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 r1 <=...<=rn. 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 rj. The latest ending time of the intervals is called the completion time of job j and denoted Cj. We wish to find a feasible preemptive schedule on one machine, which minimizes the total weighted completion time, which is defined as Σ wj Cj.

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 Xi,t, where Xi,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 ri+p, and (2) that for any time interval [s,t] the number of jobs that are fully executed (the sum of Xi,u over u in [s,t] and over i such that ri ≥= 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 rj=j-1 and p=n. This proof lead us to the dynamic program below.

A dynamic program for the special case p>max rj

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 rj=j and p=2 and arbitrary weights of course.