DocumentCode
349848
Title
Chromatic scheduling of dedicated 2-processor UET tasks to minimize mean flow time
Author
Giaro, K. ; Kubale, M. ; Malafiejski, M. ; Piwakowski, K.
Author_Institution
Foundations of Inf. Dept., Tech. Univ. Gdansk, Poland
Volume
1
fYear
1999
fDate
1999
Firstpage
343
Abstract
Investigates the computational complexity of scheduling of biprocessor tasks on dedicated processors from a mean flow time point of view. Since the general problem is strongly NP-hard, we assume some restrictions on task lengths and the structure of scheduling graphs. In this way we identify a number of special cases that are either NP-hard or polynomially solvable
Keywords
computational complexity; graph colouring; minimisation; processor scheduling; resource allocation; biprocessor tasks; chromatic scheduling; dedicated 2-processor UET tasks; mean flow time; strongly NP-hard problem; Computational complexity; Computer networks; Fault tolerant systems; Informatics; Job shop scheduling; Multiprocessing systems; Polynomials; Processor scheduling; System testing; Tree graphs;
fLanguage
English
Publisher
ieee
Conference_Titel
Emerging Technologies and Factory Automation, 1999. Proceedings. ETFA '99. 1999 7th IEEE International Conference on
Conference_Location
Barcelona
Print_ISBN
0-7803-5670-5
Type
conf
DOI
10.1109/ETFA.1999.815375
Filename
815375
Link To Document