Scheduling equal-length jobs on identical parallel machines

We study the situation where a set of n jobs with release dates and equal p rocessing times have to be scheduled on m identical parallel machines. We s how that, if the objective function can be expressed as the sum of n functi ons f(i) of the completion time C-i of each job J(i), the problem can be so lved in polynomial time for any fixed value of m. The only restriction is t hat functions f(i) have to be non-decreasing and that for any pair of jobs (J(i),J(j)), the function f(i)-f(j) has to be monotonous. This assumption h olds for several standard scheduling objectives, such as the weighted sum o f completion times or the total tardiness. Hence, the problems (Pm \ p(i) = p,r(i)\ Sigma w(i)C(i)) and (Pm \ p(i) = p,r(i)\ Sigma T-i) are polynomial ly solvable. (C) 2000 Elsevier Science B.V. All rights reserved.