Publication
SIAM Journal on Computing
Paper

Fast algorithm for multiprocessor scheduling of unit-length jobs

View publication

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.

Date

Publication

SIAM Journal on Computing

Authors

Topics

Share