Please use this identifier to cite or link to this item:

Optimizing Static Job Scheduling in a Network of Heterogeneous Computers

Authors Tang, Xueyan HKUST affiliated (currently or previously).
Chanson, Samuel HKUST affiliated (currently or previously)
Issue Date 2000
Source Proceedings of the International Conference on Parallel Processing , 2000, p. 373-382, Article number 876153
Summary This paper investigates static job scheduling schemes that distribute workload in a network of computers with different speeds. Static schemes involve very low overhead and complexity compared to dynamic schemes, but can still provide significant performance improvement over the case of no load balancing. Optimization techniques are proposed for workload allocation and job dispatching. Workload allocation is modeled as a non-linear optimization problem and solved mathematically: It is shown that allocating a disproportionately high percentage of jobs to the more powerful computers improves system performance. The proposed job dispatching algorithm is an extension of the traditional round-robin scheme. The objective is to reduce burstiness in the job arrival stream to each computer The schemes are evaluated by simulation experiments. Performance results verify their effectiveness in terms of mean response time, mean response ratio, and fairness. The Optimized Round-Robin (ORR) strategy which combines both techniques out-performs other static scheduling algorithms examined.
Note International Conference on Parallel Processing, ICPP 2000; Toronto; Canada; 21 August 2000 through 24 August 2000; Category numberPR00768; Code 116506
ISSN 0190-3918
ISBN 0769507689
Language English
Format Conference paper
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Files in this item:
File Description Size Format
icpp2000.pdf 167909 B Adobe PDF