Optimal and suboptimal reliable scheduling of precedence-constrained tasks in heterogeneous distributed computing

Abstract

This paper introduces algorithms which can produce both optimal and suboptimal task assignments to minimize the probability of failure of an application executing on a heterogeneous distributed computing system. A cost function which defines this probability under a given task assignment is derived. To find optimal and suboptimal task assignments efficiently, the reliable matching and scheduling problem is converted to the state-space search problem in which the cost function derived is used to guide the search. The A* algorithm for finding optimal task assignments and the A* m, and hill-climbing algorithms for finding suboptimal task assignments are presented. The simulation results are provided to confirm the performance of the proposed algorithms