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
fDate :
30 May-2 Jun 1994
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;
Conference_Titel :
Circuits and Systems, 1994. ISCAS '94., 1994 IEEE International Symposium on
Conference_Location :
London
Print_ISBN :
0-7803-1915-X
DOI :
10.1109/ISCAS.1994.408813
