Title :
Job scheduling on a hypercube
Author :
Zhu, Yahui ; Ahuja, Mohan
Author_Institution :
Dept. of Comput. & Inf. Sci., Ohio State Univ., Columbus, OH, USA
fDate :
28 May-1 Jun 1990
Abstract :
The problem of scheduling n independent jobs on an m -dimensional hypercube system to minimize the finish time is discussed. After some preliminary definitions are given, it is shown that a simple nonpreemptive algorithm, called largest dimension first, can have an asymptotic optimal performance and an absolute bound no worse than 2-1/2m. An absolute lower bound for the schedules generated by any algorithm using decreasing dimension lists is proved. A preemptive scheduling algorithm is also given
Keywords :
hypercube networks; scheduling; asymptotic optimal performance; finish time; largest dimension first; m-dimensional hypercube system; nonpreemptive algorithm; preemptive scheduling algorithm; scheduling; Algorithm design and analysis; Approximation algorithms; Communication channels; Computer networks; Heuristic algorithms; Hypercubes; Information science; Processor scheduling; Scheduling algorithm;
Conference_Titel :
Distributed Computing Systems, 1990. Proceedings., 10th International Conference on
Conference_Location :
Paris
Print_ISBN :
0-8186-2048-X
DOI :
10.1109/ICDCS.1990.89321
