A DAG task scheduling scheme on heterogeneous cluster systems using discrete IWO algorithm

摘要

A scheduling problem that aims to minimize makespan plays an important role in various applications in heterogeneous cluster systems. This problem becomes extremely challenging in heterogeneous cluster systems, even if parallel applications are considered. Recently, the invasive weed optimization (IWO) algorithm has been proven to be extremely effective in many fields. IWO is a novel bionic intelligent optimization algorithm that exhibits fast convergence and this is easy to implement. This study focuses on a task scheduling scheme for heterogeneous cluster systems using a discrete IWO task scheduling (IWOTS) algorithm. The basic concept of our approach is to maximize the advantages of both meta-heuristic based and heuristic-based algorithms while minimizing their drawbacks. The proposed IWOTS algorithm incorporates the IWO approach to assign a priority to each task while using an efficient heuristic-based earliest finish time (En') approach to perform task-to-computing-nodes mapping. Results of extensive simulation experiments show that IWOTS generally exhibits outstanding convergence performance and can produce an optimal scheduling solution to achieve good makespan. (C) 2016 Elsevier B.V. All rights reserved.