A hybrid genetic algorithm for optimization of scheduling workflow applications in heterogeneous computing systems

摘要

Workflow scheduling is a key component behind the process for an optimal workflow enactment. It is a well-known NP-hard problem and is more challenging in the heterogeneous computing environment. The increasing complexity of the workflow applications is forcing researchers to explore hybrid approaches to solve the workflow scheduling problem. The performance of genetic algorithms can be enhanced by the modification in genetic operators and involving an efficient heuristic. These features are incorporated in the proposed Hybrid Genetic Algorithm (HGA). A solution obtained from a heuristic is seeded in the initial population that provides a direction to reach an optimal (makespan)solution. The modified two fold genetic operators search rigorously and converge the algorithm at the best solution in less amount of time. This is proved to be the strength of the HGA in the optimization of fundamental objective (makespan) of scheduling. The proposed algorithm also optimizes the load balancing during the execution side to utilize resources at maximum. The performance of the proposed algorithm is analyzed by using synthesized datasets, and real-world application workflows. The HGA is evaluated by comparing the results with renowned and state of the art algorithms. The experimental results validate that the HGA outperforms these approaches and provides quality schedules with less makespans.