Scholars@Duke

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

Publication ,  Journal Article
Frederickson, GN; Rodger, SH
Published in: SIAM Journal on Computing
January 1, 1994
Published version (DOI)

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.

Duke Scholars

Susan H. Rodger
Author Susan H. Rodger Computer Science

Published In

SIAM Journal on Computing

DOI

10.1137/S0097539790186716

ISSN

0097-5397

Publication Date

January 1, 1994

Volume

23

Issue

1

Start / End Page

185 / 211

Related Subject Headings

  • Computation Theory & Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Frederickson, G. N., & Rodger, S. H. (1994). NC Algorithm for scheduling unit-time jobs with arbitrary release times and deadlines. SIAM Journal on Computing, 23(1), 185–211. https://doi.org/10.1137/S0097539790186716
Frederickson, G. N., and S. H. Rodger. “NC Algorithm for scheduling unit-time jobs with arbitrary release times and deadlines.” SIAM Journal on Computing 23, no. 1 (January 1, 1994): 185–211. https://doi.org/10.1137/S0097539790186716.
Frederickson GN, Rodger SH. NC Algorithm for scheduling unit-time jobs with arbitrary release times and deadlines. SIAM Journal on Computing. 1994 Jan 1;23(1):185–211.
Frederickson, G. N., and S. H. Rodger. “NC Algorithm for scheduling unit-time jobs with arbitrary release times and deadlines.” SIAM Journal on Computing, vol. 23, no. 1, Jan. 1994, pp. 185–211. Scopus, doi:10.1137/S0097539790186716.
Frederickson GN, Rodger SH. NC Algorithm for scheduling unit-time jobs with arbitrary release times and deadlines. SIAM Journal on Computing. 1994 Jan 1;23(1):185–211.

Published In

SIAM Journal on Computing

DOI

10.1137/S0097539790186716

ISSN

0097-5397

Publication Date

January 1, 1994

Volume

23

Issue

1

Start / End Page

185 / 211

Related Subject Headings

  • Computation Theory & Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics