NC Algorithm for scheduling unit-time jobs with arbitrary release times and deadlines
Published
Journal Article
The problem of scheduling n unit-time jobs with real-valued release times and deadlines is shown to be in NC. The solution is based on characterizations of a canonical schedule and best subset of jobs to be scheduled in a given time interval. The algorithm runs on a CREW PRAM in O((log n)2 time and uses O(n4/log n) processors.
Full Text
Duke Authors
Cited Authors
- Frederickson, GN; Rodger, SH
Published Date
- January 1, 1994
Published In
Volume / Issue
- 23 / 1
Start / End Page
- 185 - 211
International Standard Serial Number (ISSN)
- 0097-5397
Digital Object Identifier (DOI)
- 10.1137/S0097539790186716
Citation Source
- Scopus