Scheduling jobs with equal processing times and time windows 
on identical parallel machines

Peter Brucker (Universität Osnabrück)
Svetlana A. Kravchenko (United Institute of Informatics Problems)

Abstract
We present a linear programming approach to the problem of scheduling
equal processing time jobs with release dates and deadlines on identical 
parallel machines. The known algorithm with complexity O(n3 log log n) 
of B. Simons schedules all the jobs while minimizing both the maximum 
completion time and the mean flow time. Our approach permits also to 
minimize the weighted sum of completion times and total tardiness in 
polynomial time for the problems without deadlines. The complexity 
status of these problems was open.

Keywords: scheduling, parallel machines, linear programming