Improving the Scheduling Precedence Constrained Stochastic Tasks on Heterogeneous Cluster Systems

Scheduling such precedence constrained stochastic tasks with communication time on a heterogeneous cluster systems- with processors of different computing capabilities- is an important and difficult problem in parallel and distributed computing to minimize the parallel application’s expected completion time. The most common objective of scheduling tasks is to call and map tasks of a parallel application onto processors of a cluster system and order their executions, so that task precedence constraints are satisfied and the minimum makespan is achieved. In this paper, we propose the stochastic dynamic level scheduling (SDLS) algorithm based on stochastic bottom levels and stochastic dynamic levels to solve the problem of scheduling precedence constrained stochastic tasks. The evaluation of results show that the proposed stochastic task scheduling algorithm, by decreasing the factor of complexity, causes the decreasing of the execution time of the algorithm. This improvement is particularly more obvious when the number of tasks is higher.