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
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;
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
DOI :
10.1109/ETFA.1999.815375
