Zhiao Shi (2006)
Scheduling tasks with precedence constraints on heterogeneous distributed computing systems
PhD thesis, University of Tennessee, Knoxville.
Efficient scheduling is essential to exploit the tremendous potential of high performance computing systems. Scheduling tasks with precedence constraints is a well studied problem and a number of heuristics have been proposed.
In this thesis, we first consider the problem of scheduling task graphs in heterogeneous distributed computing systems (HDCS) where the processors have different capabilities. A novel, list scheduling-based algorithm to deal with this particular situation is proposed. The algorithm takes into account the resource scarcity when assigning the task node weights. It incorporates the average communication cost between the scheduling node and its node when computing the Earliest Finish Time (EFT). Comparison studies show that our algorithm performs better than related work overall.
We next address the problem of scheduling
task graphs to both minimize the makespan and maximize the robustness
in HDCS. These two objectives are conflicting and an epsilon-constraint method is employed to solve the bi-objective
optimization problem. We give two definitions of robustness based on
tardiness and miss rate. We also prove that slack is an effective
metric to be used to adjust the robustness. The overall performance of
a schedule must consider both the makespan and robustness. Experiments
are carried out to validate the performance of the proposed algorithm.
uncertainty nature of the task execution times and data transfer rates
is usually neglected by traditional scheduling heuristics. We model
those performance characteristics of the system as random variables. A
stochastic scheduling problem is formulated to minimize the expected
makespan and maximize the robustness. We propose a genetic algorithm
based approach to tackle this problem. Experiment results show that our
heuristic generates schedules with smaller makespan and higher robustness compared with other deterministic approaches.