Title :
Scheduling jobs on a tree-connected processor system
Author :
Kawaguchi, Tsuyoshi ; Onaga, Kenji ; Kyan, Seiki
Author_Institution :
Dept. of Electron. & Inf. Eng., Univ. of the Ryukyus, Okinawa, Japan
Abstract :
A tree-connected processor system (TPS) is one where m (>or=1) processors are connected to constitute a rooted tree. The authors study the problem of finding a feasible schedule for a TPS for n jobs with release times and deadlines. It is shown that the problem can be solved in O(mn log n) time if jobs have unit processing times.<>
Keywords :
directed graphs; multiprocessing systems; scheduling; supervisory programs; trees (mathematics); deadlines; multiprocessing system; operating systems; release times; rooted tree; scheduling jobs; tree-connected processor system; unit processing times; Circuits and systems; Polynomials; Processor scheduling;
Conference_Titel :
Circuits and Systems, 1988., IEEE International Symposium on
Conference_Location :
Espoo, Finland
DOI :
10.1109/ISCAS.1988.15226
