Reliable scheduling of precedence-constrained tasks using a genetic algorithm

This paper investigates the problem of reliable matching and scheduling of an application, which is composed of tasks with precedence constraints, in a heterogeneous distributed computing system. The reliable matching and scheduling problem is posed as finding a task assignment to minimize the probability of failure of the application. A cost function which defines this probability under a given task assignment is derived. Because the time complexity of the reliable matching and scheduling problem is exponential, to find optimal and suboptimal solutions efficiently, ct novel genetic algorithm is devised. The simulation results are provided to confirm the performance of the proposed genetic algorithm.