Modelling and scheduling of heterogeneous computing systems

Abstract

Distributed computing system (DCS) reliability and the completion time of an application are the two most important factors in defining the performance of DCSs. This dissertation focuses on the development of algorithms to maximize reliability and/or minimize the completion time of more practical DCS models. A more practical reliabilitya??oriented allocation model was proposed. To solve this NP-complete problem, a Genetic Algorithm and Tabu Search were developed, the latter outperforming the former. Further improvements in performance were obtained by using a Parallel Tabu Search. To solve a completion time oriented task scheduling problem, an iterative list algorithm was proposed, which outperformed most existed scheduling algorithms. To consider DCS reliability and completion time simultaneously, a multi-objective optimization problem was formulated and a Tabu Search proposed to solve the problem. In addition, a general centralized heterogeneous distributed system model was formulated and a solution algorithm developed to compute the distributed service reliability.