Formal verification and performance evaluation of task scheduling heuristics for makespan optimization and workflow distribution in large-scale computing systems

There are various algorithms that are designed to satisfy the needs of high performance applications and exhaustive work ows in large-scale computing systems. This work analyzes the impact of optimizing the key performance parameters, such as makespan, power consumption, and resource utilization. Five state of the art heuristics are simulated utilizing a wide range of random work ows and different task distributions. Moreover, scheduling heuristics comprise list based algorithms for which theoretical performance guarantees are proven. The paper also presents important problems regarding the evaluated algorithms and their impact on performance of the scheduling system.