Title :
Job Scheduling for Campus-scale Global Computing with Machine Availability Constraints
Author :
Sun, Guangzhong ; Shan, Jiulong ; Chen, Guoliang
Author_Institution :
Dept. of Comput. Sci. & Technol., Univ. of Sci. & Technol. of China
Abstract :
The rapid improvement of commodity components makes the global computing platform increasingly viable for many applications. This paper studied the problem of job scheduling for campus-scale global computing on theoretical level. Based on system modeling, we first proved the scheduling problem is a NP-hard problem, and then chose the approximation algorithm LS (list scheduling) as a solution. Finally, the theoretical analysis showed that it is a (m+1)-approximation algorithm for our model
Keywords :
computational complexity; grid computing; peer-to-peer computing; scheduling; NP-hard problem; approximation algorithm; campus-scale global computing; job scheduling; list scheduling; machine availability constraints; Algorithm design and analysis; Application software; Approximation algorithms; Computer science; Distributed computing; Grid computing; Internet; Processor scheduling; Resource management; Sun;
Conference_Titel :
Computer and Computational Sciences, 2006. IMSCCS '06. First International Multi-Symposiums on
Conference_Location :
Hanzhou, Zhejiang
Print_ISBN :
0-7695-2581-4
DOI :
10.1109/IMSCCS.2006.82
