2015 7th International Conference on Intelligent Human-Machine Systems and Cybernetics

A Task Scheduling Algorithm Based on Genetic Algorithm and Ant Colony

Optimization Algorithm with Multi-QoS Constraints in Cloud Computing

Yangyang Dai1, Yuansheng Lou2, Xin Lu3

1. College of Computer & Information, Hohai University, Nanjing, China
Email: Daisy_daiyy@126.com, wise.lou@163.com, lvxin.gs@163.com

Abstract—Task scheduling problem in cloud computing opportunity of the two algorithms, the algorithm did not
environment is NP-hard problem, which is difficult to obtain consider the load balancing problem of resources.
exact optimal solution and is suitable for using intelligent On the basis of the above work, this paper proposes a
optimization algorithms to approximate the optimal solution. task scheduling algorithm MQoS-GAAC in cloud
Meanwhile, quality of service (QoS) is an important indicator computing, which is considering multi-dimensional QoS
to measure the performance of task scheduling. In this paper, a constraints and the combination of ACO and GA. MQoS-
novel task scheduling algorithm MQoS-GAAC with multi-QoS GAAC overcomes the shortcomings of traditional scheduling
constraints is proposed, considering the time-consuming, algorithm, which considers QoS for users as the fitness
expenditure, security and reliability in the scheduling process.
function to filter the appropriate resources. Dynamic fusion
The algorithm integrates ant colony optimization algorithm
strategy is used to determine the best fusion time for ACO
(ACO) with genetic algorithm (GA). To generate the initial
pheromone efficiently for ACO, GA is invoked. With the
and GA. Load balancing factor is considered when setting
designed fitness function, 4-dimensional QoS objectives are initial pheromone in ACO. Updating pheromone uses local
evaluated. Then, ACO is utilized to seek out the optimum and global updating rules, and the amount of changed
resource. The experiment indicates that the proposed pheromones is determined by the QoS value of resources.
algorithm has preferable performance both in balancing The algorithm not only improves the user QoS, but also
resources and guaranteeing QoS. keeps the resource load balancing. And further improve the
overall system performance.
Keywords-task scheduling; cloud computing; genetic
algorithm; ant colony optimization algorithm; QoS II. RELATED CONCEPTS
Task scheduling in cloud computing means based on the
I. INTRODUCTION current information of task and resource and in accordance
with a certain strategy to build a good mapping relationship
Cloud computing is an emerging computing model [1],
between tasks and resources. According to the mapping
which is developed by parallel computing, distributed
relationship, the appropriate tasks are allocated to the
computing and grid computing [2]. Task scheduling is an
appropriate resources to perform [9]. In this paper, the user’s
important part of cloud computing. According to the needs
demands for QoS of tasks are expressed as time, cost, safety
of QoS and using appropriate means, different tasks are
and reliability, and shown as membership function. Model is
assigned to the appropriate resource nodes, which is an NP-
as follows:
hard problem [3]. Currently around scheduling problems in
cloud computing environment, there are a lot of researches at Definition 1: task set T = {t1, t2, Ă, tn}, the current task
home and abroad. Tawfeek [4] proposed a cloud task queue has n pending tasks.
scheduling policy based on ant colony optimization Definition 2: cloud resources set R = { r1, r2, Ă, rm}, the
algorithm, of which the main goal was minimizing the current resource pool has m valid resources, resource refers
makespan of a given tasks set. In [5] and [6], a task to the basic unit for executing tasks in cloud computing .
scheduling based on genetic ant colony algorithm in cloud Definition 3: QoS mathematical model:
computing was proposed, which used the global search Time membership function Sch(i, j): In (1), ETij is the
ability of GA to find the optimal solution, and converted to expected execution time that task ti executed in resource rj,
the initial pheromone of ACO. But these papers didn’t take ET(i, j) is the actual execution time that task ti executed in
QoS into account. Duan [7] proposed a task scheduling resource rj.
strategy with QoS constraints based on GA and ACO, which
made use of the predicted cost of time and money to define ­1 − ET(i, j) / ETij , ET(i, j) > ETij
Sch ( i, j ) = ® (1)
fitness function and was more efficient in balancing ¯ 1, other
resources load and assuring QoS. However, the fusion time
of GA and ACO was not accurate considered. A QoS routing Cost effect of membership function Bug(i, j): In (2),
algorithm according to the combination of GA and ACO was Costij is the expected cost that task ti generated in resource rj,
proposed in [8]. Although the definition of control function Cost(i, j) is the actual cost that task ti generated in resource rj.
of GA was to control the appropriate combination

978-1-4799-8646-0/15 $31.00 © 2015 IEEE 425

428
DOI 10.1109/IHMSC.2015.186
 ­1 − Cost(i, j) / Costij , Cost(i, j) > Costij The initial system size in cloud environment is S. n tasks in
Bug ( i, j ) = ® (2)
¯ 1, other task set are randomly assigned to m available resources.
Chromosome length is n, the value of each gene is a random
Security membership function Saf(i, j): In (3), TSecij is number between 1 to m.
the desired security level that task ti hoped resource rj, Secij is b) The fitness function: The fitness is used to evaluate
the actual security level that resource rj offer to task ti. Secmax the quality of individuals in the population. In this paper, the
is the highest security level for the task. reciprocal of 4-dimensional QoS objective function is
chosen as fitness function. Four index coefficients of
­1 − (TSecij − Secij ) / ( Secmax - Secij ), TSecij > Secij (3) objective function meet w1+ w2+ w3+ w4=1. We can set the
Saf ( i, j ) = ®
¯ 1, other corresponding weights according to users’ needs.

n m
Reliability membership function Reb(i, j): In (4), TRelij is Fitness(I) = 1 / ¦¦ fit ( i, j ) (6)
the expected reliability that task ti hoped resource rj, SRelij is i =1 j =1

the actual reliability that that resource rj offer to task ti.

c) Select, crossover and mutation operation:
­°1 − exp ( SRelij ) / exp ( TRelij ) , TRelij > SRelij Select: Use roulette way to generate selection operator.
Reb ( i, j ) = ® (4)
°̄ 1, other
S
P(I) = Fitness(I) / ¦ Fitness(k) (7)
4 dimensional QoS objective function: In (5), w1ǃw2ǃ k =1

w3ǃw4 respectively express time, cost, safety and reliability

weights in the QoS objective function. Crossover: Use Davis sequential crossover method. The
crossover probability is constant Pc.
Mutation: Use reversal variation method. The mutation
fit ( i, j ) = w1 Sch ( i, j ) + w2 Bug ( i, j ) + w3 Saf ( i, j ) + w4 Reb ( i, j ) (5)
probability is constant Pm.
2) Fusion of Genetic Algorithm and Ant Colony
Optimization Algorithm
III. MQOS-GAAC ALGORITHM
The fusion of GA and ACO is difficult. In traditional
A. The Basic Idea of MQoS-GAAC Algorithm strategy, we set GA to run the fixed iterations. But end too
early or too late will affect the efficiency of algorithm. In this
Due to the solving efficiency in the later period of GA is paper, dynamic fusion strategy is used to ensure that the GA
not high, so it is easy to lead to a large number of redundant and ACO fuse at the right time [10].
iterations. And in the preliminary stage of ACO, lacking of Step 1: Set the minimum genetic iterations Genemin and
pheromone will lead to accumulate pheromone for a long the maximum genetic iterations Genemax.
time in the initial search. Thus, combining GA and ACO and Step 2: Count evolutionary rates of progeny population in
integrating QoS proposed MQoS-GAAC algorithm (task the genetic iterative process and set the minimum
scheduling algorithm based on genetic algorithm and ant evolutionary rates of progeny population Genemin-impro-ratio.
colony optimization algorithm with the multi-dimensional Step 3: If evolutionary rate for consecutive Genedie
QoS constraints in cloud computing). The algorithm is (Genemin İ Genedie İ Genemax) generations of progeny
divided into three parts, details are as follows: population is less than Genemin-impro-ratio, it can prove that the
Prat 1: Make full use of global fast search of GA and GA optimization speed is lower. So system can terminate the
convert the obtained global search information into the initial process of GA and go into ACO.
pheromone of ACO.
3) Ant Colony Optimization Algorithm Rules in
Part 2: Judge the appropriate time for GA and ACO
integration. MQoS-GAAC Algorithm
Part 3: Use the positive feedback of ACO and the a) Initialize Pheromone: This paper uses MMAS
characteristics of efficient convergence to finish the optimal algorithm. The initial value of the pheromone on each path
cloud task scheduling which meets the QoS constraints. is set to maximum max. According to the ratio of the load on
the resource j at the initial time and the load capacity of the
B. MQoS-GAAC Algorithm resource Lj (t)=Loadj(0)/Lj ,Lj (t) can represent the pheromone
1) Genetic Algorithm Rules in MQoS-GAAC on resource j at time t. On the basis of load balancing and
Algorithm initial pheromone distribution from GA, the initial value of
a) Chromosome coding: We use indirect encoding. pheromone on resource j sets as follows:
Chromosome length is defined as the quantity of tasks. The
value of gene in chromosome is the location of gene τ Sj (t) = τ C + τ Gj (t) + τ L ( t )
j
(8)
corresponding to the resource number that task occupied.

429
426
 In (8), C is a pheromone constant which is given based
on the size of specific solving problem and is equivalent to Input: List of Tasks and List of VMs
min in MMAS. Gj (t) is the pheromone value that is converted Output: The Best Solution for Tasks Allocation on VMs
from the solving result of GA. Steps:
b) Routing Rule: At time t, the probability that task i 1: Initialize Genemin-impro-ratio, w1, w2, w3, w4
was assigned to the resource j can be expressed as follows: 2: Define objective function according to (5)
3: Define fitness function according to (6)
4: While Genedie< Genemin-impro-ratio do
­ ªτ (t) ºα ªη º β 5: Randomly generated a set of real numbers
°° ¬ j ¼ α¬ j ¼ β , j , U ∈ available resources set
Pj (t) = ® ¦ [τ u (t) ] [ηu ]
k (9) 6: Selection, crossover and mutation
° u∈U 7: End while
°̄ 0, other 8: Generate several optimal solution groups
9: Initialize n, m, , , , NC-max
In (9), j(t) is the pheromone concentrates on resources j 10: Place m ants on n nodes
at time t. j represents visibility of the resource (i.e. heuristic 11: While NC < NC-max do
information). =aP+bB, P is the processing power of CPU 12: Initialize Tabu
(MIPS), B is the network bandwidth, a and b respectively 13: For all ants in ANT, antk ęANT
represent the proportion of processing power and bandwidth 14: For all tasks in meta-task T, tjęT
in resource visibility,  is the importance of pheromone,  15: Select the next task tj according to (9)
represents the importance of heuristic information. 16: Update Tabu, add the task tj into Tabu
c) Pheromone Updating: 17: Update the local phenomone j
Local Updating: When ants complete to assign resources 18: End for
for all tasks, update the pheromone for all allocated 19: End for
resources. Assume j(t) is the pheromone on resources rj at 20: Calculate the globally optimal scheduling
time t. Then, at time t+1, pheromone updating rules on scheme in this iteration according to (5)
resource rj is as follows: 21: Update the global pheromone only for the
best one
τ j (t + 1) = (1 − ρ )τ j (t) + ρΔτ (t) (10) 22: End while
23: Return the optimal solution
In (10),  represents pheromone volatile coefficient
(0<<1), 1- represents pheromone residual coefficient.  Figure 1. MQoS-GAAC algorithm process.
(t) can be get from (11), in which L represents the number
of resources.
IV. THE SIMULATION AND RESULTS ANALYSIS
n m This paper extends the cloud simulation platform
Δτ (t) = L / ¦ ¦ fit ( i, j ) (11) CloudSim3.0.2, rewrites some classes such as
i =1 j =1
DataCenterBroker and Cloudlet, and simulates the task
scheduling algorithm. Set the 4-dimensional QoS objective
Global Updating: When all ants have completed the first function weights: w1 = 0.2, w2 = 0.3, w3 = 0.22, w4 = 0.28.
iteration. According to (5), globally optimal scheduling Set the probability of selection parameter:  = 0.7,  = 0.3, 
scheme can be calculated in this iteration. And globally = 0.4. Simulation parameters for GA and ACO are shown in
update the pheromone that was allocated for all resources in Table 1:
optimal scheduling scheme.
TABLE I. THE PARAMETERS OF GENETIC ALGORITHM AND ANT
τ j (t + 1) = (1 − ρ )τ j (t) + Δτ '(t) (12) COLONY OPTIMIZATION ALGORITHM SETTING

Algorithm
Item
In (12), ’(t) is the increment of pheromone that can GA ACO
be get from (13). In (13), L’ is the number of allocated Population size S=50 Null
resources in optimal scheduling scheme and min ¦n ¦m fit (i, j )
k∈ Ant i =1 j =1 Crossover probability Pc=0.6 Null
represents QoS target that the optimal scheduling scheme Mutation probability Pm=0.6 Null
corresponding.
Minimum iterations 15 Null
n m
Δτ '(t) = L '/ min ¦ ¦ fit ( i, j )
Maximum iterations 30 100
(13)
k ∈Ant i =1 j =1
Minimum evolutionary rates 3% 0.5%

Fig. 1 shows the process of MQoS-GAAC algorithm. Continuous Generation 3 3

430
427
 Algorithm in this paper uses the user QoS as reference V. SUMMARY AND OUTLOOK
guidelines for task scheduling, and combines with the dual This paper proposes a task scheduling algorithm MQoS-
advantages of GA and ACO to improve the convergence GAAC, which is considering multi-QoS constraints and on
performance of solution. Compare this algorithm with GA the combination of ACO and GA. By fusing ACO and GA
and ACO, and realize the simulation examples. According to and converting the QoS into membership functions as a GA
the load balancing, compare the load balancing rates which fitness function, we can find that the optimal scheduling
can obtain from (14). scheme meets user quality of service. By CloudSim
platform, simulation results show that this algorithm in time
m
1 span and resource load balancing is superior to ACO and
LB =
m
¦ ( Load
j =1
j − Load avg ) 2 (14)
GA, and significantly improve the QoS. The next step will
consider more comprehensive QoS parameters, and
In (14), Loadj is the load on resources j, Loadavg is the dynamically adjust corresponding parameters of the
mean value of the load. The simulation results can be shown algorithm.
in Fig. 2 and Fig. 3.
ACKNOWLEDGMENT
In Fig. 2, with the quantity of tasks increasing, each
resource load rate also increases. But compared with GA and This research is partially supported by the National Key
ACO, the change of resource load rate of this algorithm is Technology Research and Development Program of the
small, and keeps at a lower level. Compared with GA and Ministry of Science and Technology of China under Grant
ACO, resource load rate of this algorithm is increased by No. 2013BAB06B04, No. 2013BAB05B00 and No.
28% and 24.1%. Therefore, the system resource allocation 2013BAB05B01. It is also supported by Jiangsu Water
result tends to be more rational and efficient, and the load Conservancy Science and Technology Project which is about
balancing degree of the whole system is also rising. the research of “Smart River” and its application of the
In Fig. 3, there is a positive correlation between the management of Chuhe in Liuhe district (2013025).
number of tasks and execution time. When quantity of tasks
is more than 500, with the number of tasks increasing, the REFERENCES
speed of execution time is significantly faster. Therefore, the [1] C. T. Ying, J. Yu, “Energy-aware genetic algorithms for task
task quantity affects the efficiency of the execution time. scheduling in cloud computing,” Proceeding of the 7th ChinaGrid
This algorithm in execution time is significantly better than Annual Conference (ChinaGrid), IEEE Press, Sept. 2012, pp. 43-48.
GA and ACO, and the execution time is maintained at a low [2] X. Y. Hua, J. Zheng, W. X. Hu, “Ant colony optimization algorithm
level. Therefore, no matter in time efficiency or in the for computing resource allocation based on cloud computing
efficiency of solving the optimal solution, MQoS-GAAC is environment,” Journal of East China Normal University (Natural
Science), vol.1, 2010, pp.127.
better than a single GA or ACO.
[3] H. L. Shi, “Research of job scheduling on cloud computing,”
Nanjing: Nanjing University of Science and Technology, 2012.
[4] M. A. Tawfeek, A. El-Sisi, A. E. Keshk, et al., “Cloud task
scheduling based on ant colony optimization,” Proceeding of the 8th
International Conference on Computer Engineering & Systems
(ICCES), IEEE Press, Nov. 2013, pp.64-69.
[5] C. Y. Liu, “A task scheduling algorithm based on genetic algorithm
and ant colony optimization in cloud computing,” Proceeding of the
13th International Symposium on Distributed Computing and
Applications to Business, Engineering and Science (DCABES), IEEE
Press, Nov. 2014, pp.68-72.
[6] Z. P. Yan, Y. C. Zhang, X. M. Fu, et al., “Research of a genetic
algorithm ant colony optimization based on cloud model,” Proceeding
Figure 2. Resource load comparing of International Conference on Mechatronics and Automation
(ICMA), IEEE Press, Aug. 2009, pp. 4725-4730.
[7] W. J. Duan, X. L. Fu, F. Wang, et al., “QoS constraints task
scheduling based on genetic algorithm and ant colony algorithm
under cloud computing environment,” Journal of Computer
Applications, vol.2, 2014, pp.66-69.
[8] P. Liu, F. Gao, and Y. Yang, “QoS routing algorithm based on the
combination of genetic algorithm and ant colony algorithm,”
Application Research of Computers, vol.24, 2007, pp.224-227.
[9] H. Wu, “Research of Task Scheduling Algorithm in the Cloud
Environment,” Nanjing: Nanjing University of Posts and
Telecommunications, 2013.
[10] Y. Zhang, F. Li, and T. Zhou, “Task scheduling algorithm based on
genetic ant colony algorithm in cloud computing environment,”
Computer Engineering and Applications, vol.50, 2014, pp.51-55.
Figure 3. Execution time comparing

431
428