A Task Scheduling Algorithm Based on Genetic Algorithm and Ant Colony Optimization Algorithm with Multi-QoS Constraints in Cloud Computing

Task scheduling problem in cloud computing environment is NP-hard problem, which is difficult to obtain exact optimal solution and is suitable for using intelligent optimization algorithms to approximate the optimal solution. Meanwhile, quality of service (QoS) is an important indicator to measure the performance of task scheduling. In this paper, a novel task scheduling algorithm MQoS-GAAC with multi-QoS constraints is proposed, considering the time-consuming, expenditure, security and reliability in the scheduling process. The algorithm integrates ant colony optimization algorithm (ACO) with genetic algorithm (GA). To generate the initial pheromone efficiently for ACO, GA is invoked. With the designed fitness function, 4-dimensional QoS objectives are evaluated. Then, ACO is utilized to seek out the optimum resource. The experiment indicates that the proposed algorithm has preferable performance both in balancing resources and guaranteeing QoS.

I. Introduction

Cloud computing is an emerging computing model [1], which is developed by parallel computing, distributed computing and grid computing [2]. Task scheduling is an important part of cloud computing. According to the needs of QoS and using appropriate means, different tasks are assigned to the appropriate resource nodes, which is an NP-hard problem [3]. Currently around scheduling problems in cloud computing environment, there are a lot of researches at home and abroad. Tawfeek [4] proposed a cloud task scheduling policy based on ant colony optimization algorithm, of which the main goal was minimizing the makespan of a given tasks set. In [5] and [6], a task scheduling based on genetic ant colony algorithm in cloud computing was proposed, which used the global search ability of GA to find the optimal solution, and converted to the initial pheromone of ACO. But these papers didn't take QoS into account. Duan [7] proposed a task scheduling strategy with QoS constraints based on GA and ACO, which made use of the predicted cost of time and money to define fitness function and was more efficient in balancing resources load and assuring QoS. However, the fusion time of GA and ACO was not accurate considered. A QoS routing algorithm according to the combination of GA and ACO was proposed in [8]. Although the definition of control function of GA was to control the appropriate combination opportunity of the two algorithms, the algorithm did not consider the load balancing problem of resources.