NC Algorithm for scheduling unit-time jobs with arbitrary release times and deadlines

Journal Article (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