Fast algorithm for multiprocessor scheduling of unit-length jobs

Abstract

An efficient polynomial time algorithm for the problem of scheduling n unit length jobs with rational release times and deadlines on m identical parallel machines is presented. By using preprocessing, a running time of O(mn2) is obtained that is an improvement over the previous best running time of O(n3 log log n). The authors also present new NP completeness results for two closely related problems.