Computer cluster scheduling algorithm based on time bounded dynamic programming

Author

Grudenic, I. ; Bogunovic, N.

Author_Institution

Fac. of Electr. Eng. & Comput., Dept. of Electron., Microelectron., Comput. & Intell. Syst., Univ. of Zagreb, Zagreb, Croatia

fYear

2011

fDate

23-27 May 2011

Firstpage

722

Lastpage

726

Abstract

Computer clusters are currently the most used distributed computer architecture. Efficient utilization of computer cluster depends on a scheduling policy that is applied. Scheduling of jobs in computer cluster is a complicated task due to frequent changes in the workload. In this paper we present scheduling algorithm that is based on EASY backfilling scheduling strategy. Dynamic programming with time restriction is used to calculate as good schedule as possible within given time constraints. Algorithm is evaluated on several computer cluster workloads and is shown to outperform original backfilling strategy.

Keywords

dynamic programming; parallel machines; processor scheduling; resource allocation; workstation clusters; EASY backfilling scheduling strategy; computer cluster scheduling algorithm; computer cluster workload; distributed computer architecture; job scheduling; nonpreemptive rigid parallel jobs; resource utilization; scheduling policy; supercomputers; time bounded dynamic programming; time constraint; time restriction; Algorithm design and analysis; Clustering algorithms; Computers; Heuristic algorithms; Optimization; Processor scheduling; Scheduling;

fLanguage

English

Publisher

ieee

Conference_Titel

MIPRO, 2011 Proceedings of the 34th International Convention

Conference_Location

Opatija

Print_ISBN

978-1-4577-0996-8

Type

conf

Filename

5967148