An Analytical Review and Performance Measures of State-of-Art Scheduling Algorithms in Heterogenous Computing Enviornment

Task scheduling and resource utilization have always been among the most critical issues for high performance in heterogeneous computing. The heterogeneity of computation costs on a given set of computing elements and the communication costs among computing elements increase the complexity of the scheduling problem. Extensive research proves that the list-based task scheduling algorithms generate the most efficient schedules for complex workflow applications in the heterogeneous computing environment. The workflow applications comprise thousands of interconnected tasks with dependencies. In the last decades, various list-based scheduling algorithms have been proposed to achieve some kinds of performance objectives such as minimization of makespan and energy consumption and maximization of resource utilization and reliability. In this article, various list-based workflow scheduling algorithms have been reviewed from the last two decades with the assumption of heterogeneous computing systems being used as the underlying computing infrastructure. This review process categorizes the algorithms based on scheduling objectives. For a better analysis of the algorithms, each algorithm is compared with other algorithms based on its objectives, merits, comparison metrics, workload type, experimental scale, experimental environment, and results compared. Finally, experimental analysis of seven state-of-art algorithms has been conducted on randomly generated workflow to understand the working of list-scheduling algorithms. The main purpose of this article is to give proper direction to new researchers who are willing to work in workflow scheduling in heterogeneous computing environments.