AN NC ALGORITHM FOR SCHEDULING UNIT-TIME JOBS WITH ARBITRARY RELEASE TIMES AND DEADLINES

Authors
FREDERICKSON GN RODGER SH
Citation
Gn. Frederickson et Sh. Rodger, AN NC ALGORITHM FOR SCHEDULING UNIT-TIME JOBS WITH ARBITRARY RELEASE TIMES AND DEADLINES, SIAM journal on computing, 23(1), 1994, pp. 185-211
Citations number
15
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
23
Issue
1
Year of publication
1994
Pages
185 - 211
Database
ISI
SICI code
0097-5397(1994)23:1<185:ANAFSU>2.0.ZU;2-C
Abstract
The problem of scheduling n unit-time jobs with real-valued release ti mes and deadlines is shown to be in NC. The solution is based on chara cterizations of a canonical schedule and best subset of jobs to be sch eduled 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.