DocumentCode
292869
Title
Improved lower bounds for the scheduling optimization problem
Author
Hu, Yuan ; Carlson, Bradley S.
Author_Institution
Dept. of Electr. Eng., State Univ. of New York, Stony Brook, NY, USA
Volume
1
fYear
1994
fDate
30 May-2 Jun 1994
Firstpage
295
Abstract
In this paper lower bounds for the performance constrained and resource constrained scheduling of tasks on multiprocessors are presented. The lower bounds derived here are sharper than previously known results and the time complexity of their computation is only slightly greater
Keywords
computational complexity; multiprocessing systems; optimisation; processor scheduling; scheduling; lower bounds; multiprocessors; performance constrained scheduling; resource constrained scheduling; scheduling optimization problem; time complexity; Constraint optimization; Design optimization; Integrated circuit modeling; Laboratories; NP-complete problem; Processor scheduling; Time measurement; Time sharing computer systems; Tree graphs; Upper bound;
fLanguage
English
Publisher
ieee
Conference_Titel
Circuits and Systems, 1994. ISCAS '94., 1994 IEEE International Symposium on
Conference_Location
London
Print_ISBN
0-7803-1915-X
Type
conf
DOI
10.1109/ISCAS.1994.408813
Filename
408813
Link To Document