A hybrid particle swarm optimization and hill climbing algorithm for task scheduling in the cloud environments

Abstract

Task scheduling is one of the most important issues in heterogeneous environments when high efficiency is required. Because task scheduling is a Nondeterministic Polynomial (NP)-hard problem, many evolutionary algorithms have been adopted to solve this problem. Since the convergence speed of solutions in population-based algorithms is low, they are integrated with local search algorithms. Thus, in this paper, to optimize the task scheduling makespan, a hybrid particle swarm optimization and hill climbing algorithm is proposed. The experimental results on random and scientific Directed Acyclic Graph (DAG) showed that the proposed algorithm performs effectively in terms of the makespan compared to the current well-known heuristic and particle swarm optimization algorithms. Keywords: Cloud computing, Directed acyclic graph, Hill climbing, PSO, Task scheduling