Quand la préemption ne sert à rien

Philippe Baptiste

CNRS - IBM Watson


Abstract. McNaughton's theorem (1959) states that preemptions in 
scheduling arbitrary processing time jobs on identical parallel machines 
to minimize the total weighted completion time are redundant. Since 
then, preemption redundancy has been investigated by many papers 
and non-preemptive optimization techniques have been successfully ap- 
plied to solve preemptive problems. In this paper, we consider the 
problem of scheduling n unit execution time jobs with arbitrary in- 
teger release dates on parallel machines. We show that preemptions 
are redundant for any sum objective function "sum f_i" when the func- 
tions f_i are non-decreasing and linear between consecutive integer time 
points. Hence, like its non-preemptive counterpart, the preemptive 
problem is solvable in polynomial time. As a special case, this en- 
ables us to establish the status of the weighted tardiness problem 
P|pmtn; r i ; p i = 1| sum w_i T_i . This is a generalization of the 
recent results of Brucker, Heitman and Hurink (2002).

Keywords: scheduling, preemption, computational complexity, linear 
programming