DocumentCode :
1436191
Title :
An algorithm for scheduling jobs in hypercube systems
Author :
Kwon, Oh-Heum ; Chwa, Kyung-yong
Author_Institution :
Dept. of Comput. Eng., Pukyong Nat. Univ., Pusan, South Korea
Volume :
9
Issue :
9
fYear :
1998
fDate :
9/1/1998 12:00:00 AM
Firstpage :
856
Lastpage :
860
Abstract :
In this paper, we consider the problem of nonpreemptively scheduling independent jobs so as to minimize overall finish time on an m-dimensional hypercube system. This problem is NP-hard. We propose a polynomial time approximation algorithm and prove that the absolute performance ratio of the algorithm does not exceed 1.875. This is the first algorithm achieving an absolute performance ratio less than two by a constant
Keywords :
hypercube networks; processor scheduling; NP-hard; hypercube system; nonpreemptive scheduling; performance ratio; polynomial time approximation; Approximation algorithms; Communication channels; Computer networks; Hypercubes; Optimized production technology; Polynomials; Processor scheduling; Scheduling algorithm; Virtual manufacturing;
fLanguage :
English
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1045-9219
Type :
jour
DOI :
10.1109/71.722219
Filename :
722219
Link To Document :
بازگشت