A Fast Algorithm for Multiprocessor Scheduling of Unit-Length Jobs
- 1 August 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 18 (4) , 690-710
- https://doi.org/10.1137/0218048
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(mn^2 )$ is obtained that is an improvement over the previous best running time of $O(n^3 \log \log n)$. The authors also present new NP-completeness results for two closely related problems.
Keywords
This publication has 7 references indexed in Scilit:
- A linear-time algorithm for a special case of disjoint set unionJournal of Computer and System Sciences, 1985
- Scheduling unit-time tasks with integer release times and deadlinesInformation Processing Letters, 1983
- Multiprocessor Scheduling of Unit-Time Jobs with Arbitrary Release Times and DeadlinesSIAM Journal on Computing, 1983
- Scheduling Unit–Time Tasks with Arbitrary Release Times and DeadlinesSIAM Journal on Computing, 1981
- A fast algorithm for single processor schedulingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- Complexity of Machine Scheduling ProblemsPublished by Elsevier ,1977
- NP-complete scheduling problemsJournal of Computer and System Sciences, 1975