Journal of Ambient Intelligence and Humanized Computing

https://doi.org/10.1007/s12652-020-02614-7

ORIGINAL RESEARCH

Task scheduling optimization strategy using improved ant colony

optimization algorithm in cloud computing
Xianyong Wei1

Received: 15 July 2020 / Accepted: 10 October 2020

© Springer-Verlag GmbH Germany, part of Springer Nature 2020

Abstract
In order to solve the problems of unbalanced load, slow convergence speed and low utilization of virtual machine resources
existing in the previous task scheduling optimization strategies, this paper proposes a task scheduling optimization strategy
using improved ant colony optimization algorithm in cloud computing. Firstly, based on the principle of cloud computing task
scheduling, a scheduling model using improved ant colony algorithm is proposed to avoid the optimization strategy falling
into local optimization. Then, task scheduling satisfaction function is constructed by combining the three objectives of the
shortest waiting time, the degree of resource load balance and the cost of task completion to search the optimal solution of
task scheduling. Finally, the reward and punishment coefficient is introduced to optimize the pheromone updating rules of ant
colony algorithm, which speeds up the solution speed. Besides, we use dynamic update of volatility coefficient to optimize
overall performance of this strategy, and introduce virtual machine load weight coefficient in the process of local pheromone
updating, so as to ensure the load balance of virtual machine. The feasibility of our algorithm is analyzed and demonstrated
by experiments with Cloudsim. The experimental results show that the proposed algorithm has the fastest convergence speed,
the shortest completion time, the most balanced load and the highest utilization rate of virtual machine resources compared
with other methods. Therefore, our proposed task scheduling optimization strategy has the best performance.

Keywords Cloud computing · Task scheduling optimization · Improved ant colony algorithm · Load balancing · Penalty
coefficient · Cloudsim

1 Introduction scheduling mechanisms is an important method to enhance

the comprehensive performance of cloud computing (Garg
Cloud computing is a new revolution in the development and Chaurasia 2019).
of Internet computing. Compared with distributed com- Cloud computing integrates and manages a large number
puting, it has more outstanding advantages. It is a highly of idle computing resources by the Internet for management
efficient multifunctional computing system, and large-scale and redistribution. Its essence is to provide users with reli-
computing resources ensure the efficiency of cloud services able services quickly. Users only need to send tasks to the
(Yuan et al. 2019). The tasks that need to be processed in cloud data center on terminals, and they can use cloud plat-
cloud computing are scheduled and distributed among vari- forms to fulfill various requirements and finally obtain pro-
ous computing resources. Users can obtain computing and cessing results (Nayak and Tripathy 2019). However, a cloud
information services and efficient storage services according computing system is a large-scale complex system composed
to their needs by cloud computing (Guo et al. 2019; Hung of thousands of cloud resource nodes. Due to factors such
et al. 2019). As the core technology of cloud computing, task as the failure of internal components of physical machines,
scheduling is one of important links in the process of cloud the failure of links and the overload of systems, it is often
computing processing tasks. Therefore, optimizing task difficult to ensure that each computing node can work con-
tinuously without failure. The failure problem is often dif-
ficult to avoid during the operation of cloud systems (Abd
* Xianyong Wei Elaziz et al. 2019). In addition, with the increasing number
[email protected] of users, people consider the heterogeneity and complexity
1 of nodes in cloud computing networks. How to schedule
Shangqiu Polytechnic, Shangqiu 476000, Henan, China

13
Vol.:(0123456789)
X. Wei

tasks in a timely and efficient manner, rationally utilize cloud tion time is a key issue for cloud computing task sched-
computing resources, improve resource utilization and task uling.
execution efficiency have become one of the core issues in 6. Optimization of multiple objectives. Traditional cloud
cloud computing research (Haidri et al. 2019). computing task scheduling algorithms generally have a
As a business service, task scheduling in cloud comput- single optimization goal. If multiple factors are consid-
ing must not only consider efficient scheduling efficiency ered as scheduling optimization targets at the same time,
and high resource utilization, but also consider complex ser- the algorithm performance is insufficient. However,
vice quality and low economic cost (Matos et al. 2019; Jain there are differences between cloud computing systems
2020). Traditional cloud computing task scheduling algo- and traditional computing systems. Thus, optimization
rithms have insufficient performance to meet complex sched- of multiple objectives is also one of the issues that need
uling goals. With the maturity of computer technology and attention.
network technology, existing task scheduling optimization
strategies have achieved a lot of research results. However,
heterogeneous and diverse sources and dynamic changes, 2 Related work
different Quality of Service (QoS) requirements, unified load
balancing and multi-objective optimization are still the focus It has been more than 10 years since the concept of cloud
and difficulty of task scheduling research in cloud computing computing was proposed. Today, cloud computing has
(Chen et al. 2019). The details are as follows: attracted the attention of countless researchers and enter-
prises due to its scalability, high reliability, low cost and
1. Resources are heterogeneous and diverse. There are a lot on-demand services. It has become a research hotspot in
of computing resources, storage resources and service the current era (Marahatta et al. 2019). Cloud computing
resources in the cloud computing environment. Various aggregates computing and communication resources in a
resources form a resource pool, provide services to users networked manner. At the same time, it uses virtualization
after shielding differences by mature virtualization tech- technology to integrate a large number of low-cost, weak
nologies. computing power and wide-area distributed heterogeneous
2. Dynamic resource changes. The resources in the cloud resources into a shared resource pool with powerful comput-
computing environment are dynamic and scalable. ing power, and unified management. Resource scheduling
Resources can be accessed via the Internet or exit the strategy is an important technical means to achieve effective
cloud environment. Therefore, it is necessary to monitor allocation of computing resources and improve cloud system
the operation of resources in real time. performance. In order to improve the service performance of
3. Different needs of QoS. There are dynamic resource cloud computing more effectively, many experts and schol-
changes and diverse user choices in the cloud computing ars have conducted research on the problems encountered by
environment. User task goals generally also include mul- the task scheduling mechanism in cloud computing. Accord-
tiple requirements. The goal is not simple and unique, ing to different computing tasks and optimization goals,
not only to improve the profitability of cloud computing cloud resource scheduling algorithms can be roughly divided
providers as much as possible, but also to meet the dif- into considering resource load balancing and improving
ferent QoS needs of users with different resources. resource utilization (Reddy and Kumar 2019); meeting
4. System load balancing. An important issue in current constraints such as task execution time, energy consump-
cloud computing research is to achieve a relative bal- tion costs and user QoS; based on resource demand predic-
ance by resource management and maintenance in cloud tion Virtual machine resource dynamic allocation strategy
computing systems to avoid resource waste or form sys- on demand; multi-objective optimization algorithm (Shao
tem bottlenecks. Load balancing is mainly considered and Xie 2019). According to the characteristics of cloud
from three aspects: One is task scheduling algorithm. computing and task scheduling, the research results of task
The scheduling algorithm is highly targeted and should scheduling algorithms can be divided into four categories:
be selected according to application requirements. The heuristic task scheduling algorithm, game theory task sched-
second is load evaluation. Load evaluation includes node uling algorithm, trust mechanism task scheduling algorithm
load evaluation and system load evaluation. The third is and dynamically changing adaptive scheduling algorithm.
rescheduling. When the system nodes or system balance
fails, it is necessary to redistribute scheduling and adjust 2.1 Heuristic algorithms
the load.
5. Task completion time. For same application tasks, the Heuristic algorithms include genetic algorithm, ant colony
shorter task completion time, the easier it is to meet its algorithm, particle swarm optimization algorithm and their
QoS requirements. Therefore, minimizing task comple- improvement and fusion. Because the algorithm has the

13
Task scheduling optimization strategy using improved ant colony optimization algorithm in…

advantages of simple operability, good self-organization, genetic algorithms. The algorithm can effectively shorten the
good scalability and strong robustness, it can effectively maximum completion time of the task, but the robustness of
shorten the task scheduling time and solve the problems the algorithm needs to be improved.
of resource scheduling and load balancing. Mansouri et al.
(2019) introduced a local search operator to optimize the 2.3 Task scheduling algorithms of trust mechanism
particle swarm optimization algorithm, which can effectively
shorten the task completion time. Domanal et al. (2020) pro- Based on the trust mechanism task scheduling algorithm,
posed an ant colony optimization algorithm using the better trust mechanism was introduced in cloud computing task
feedback mechanism of the ant colony algorithm to solve scheduling. According to users’ preference in the corre-
the problem of virtual machine load in the task scheduling sponding resource pool selection, a trust-based scheduling
process, which can better improve the resource utilization strategy was proposed. They introduced trust factors into
rate. Sreenu and Malempati (2019) took advantage of the the scheduling objectives and formulated different schedul-
early search ability of the genetic algorithm and the informa- ing strategies to ensure that the new model performs well
tion feedback characteristics of the ant colony algorithm to in terms of effectiveness and user satisfaction (Wang et al.
combine the two algorithms to make up for their respective 2019). The main idea of the failure avoidance strategy was to
problems. The algorithm improved convergence speed while avoid the susceptible failure period of physical machine and
satisfying the quality of service required by users. Boveiri the virtual machine placed on it for scheduling. Wakil et al.
et al. (2019) improved the ant colony algorithm and con- (2019) defined the formal expression and derivation rules
sidered the computing power of virtual machines, network of subject trust for information security in an open network
bandwidth and other factors, and improved the load balanc- environment, and constructed a subjective trust management
ing and task execution time. Meshkati and Safi-Esfahani model based on trust evaluation mechanism. Xie et al. (2019)
(2019) was based on improving the quality of cloud comput- draw on the interpersonal relationship network in sociology
ing services, and by improving the bee colony algorithm, it and was based on the interpersonal relationship trust model.
can improve the algorithm’s global search ability to a certain It analyzed the historical interaction data between nodes and
extent, and can effectively meet the quality of service (QoS) evaluates the credibility of nodes, so that it can select the
requirements. But the convergence speed is slow and there computing resource with the largest credible dynamic level
is a problem of uneven distribution of tasks. The pheromone to execute cloud tasks Selvakumar and Gunasekaran (2019)
update method in the algorithm can be optimized in com- started from the study of resource failure rate, and through
bination with the characteristics of the scheduling mecha- statistical analysis of a large number of cloud system fail-
nism. By assigning weights to pheromone increments, the ure logs, it was found that the cloud resource failure time
computational efficiency of algorithm was improved (Neela- interval follows a fixed parameter distribution. In order to
kanteswara and Babu 2019). classify resource nodes, a strategy for dynamically providing
cloud resources based on stable resource pools and vulner-
2.2 Algorithms based on game theory able resource pools was proposed to shield a large number
of failed resource nodes. The limitation of task scheduling
To model the task scheduling problem in cloud computing, algorithm based on the trust mechanism was that it is dif-
the game strategy was used to assign the task rate to the ficult to determine the susceptibility to failure of physical
computing nodes. The utility function of the game provided machine and virtual machine placed on it for scheduling.
the ability to calculate the steady state of the node (Kaur
et al. 2019). The algorithm can balance the resource utili- 2.4 Adaptive scheduling algorithms with dynamic
zation rate of multiple nodes, improve service quality and changes
average resource utilization rate. Khan et al. (2019) used
the firework algorithm as the cloud computing task sched- The adaptive scheduling algorithm based on dynamic
uling algorithm. Optimization in terms of task execution changes focused on the real-time situation of tasks and sys-
time and load balancing had better results than particle tem resources, realized dynamic changes, updated the DAG
swarm optimization and genetic algorithms. Kaur and Sood status in time, and then scheduled tasks. It is superior to
(2020) and others proposed task scheduling methods based traditional task scheduling algorithms in terms of scheduling
on template-based genetic algorithm combined with user efficiency and resource utilization (Zhang 2019). Vila et al.
QoS constraints. Calculate the maximum size of tasks that (2019) based on the characteristics of cloud computing and
should be allocated to each processor based on factors such adaptive genetic algorithm, proposed a dual adaptive genetic
as the CPU and bandwidth of the processor. Using this as a algorithm based on time span and load balancing. The algo-
template, tasks were divided into multiple subsets and these rithm used a greedy algorithm to initialize population, and
subsets are reasonably distributed to each processor through introduced variance to describe load density between nodes

13
X. Wei

and the weight of multiple adaptation functions. Compared includes cloud software application services and interactive
with adaptive genetic algorithms, the algorithm had better interfaces. Figure 1 shows the different levels of cloud com-
load balancing and maximum completion time. Gong et al. puting architecture.
(2019) proposed an improved Memetic algorithm for the In view of the huge task volume in cloud computing, task
problem that task scheduling in cloud computing requires scheduling generally divides tasks. First, divide the task set
multiple target optimization. The algorithm can find the submitted by the user into multiple sub-tasks. Then accord-
global optimal solution faster, which improves the calcula- ing to the difference of each sub-task and considering the
tion efficiency. However, there are many parameters to be usage of the virtual resource node, the task and the virtual
set in the dynamic adaptive scheduling algorithm, and the resource are reasonably mapped. The principle diagram of
implementation process is relatively complicated, which cloud computing task scheduling is shown in Fig. 2.
needs to be improved in practice. The problem of cloud computing task scheduling can
In view of the above problems, a task scheduling opti- be described as: The problem can be described as: Distrib-
mization strategy using improved ant colony optimization uting n tasks generated by users to virtual resource nodes
algorithm in cloud computing is proposed. This strategy can (n > m) {of heterogeneous
} m according to a certain strategy.
find a global optimal solution to speed up algorithm conver- Let T = T1 , T2 , ⋯ , Tn denote the set of all subtasks to be
gence, achieve load balancing, and improve virtual machine executed,
{ and denote} the set of virtual resource nodes by
resource utilization. The main innovations are summarized V = V1 , V2 , ⋯ , Vm . Restricting a subtask to run on only
as follows: one virtual resource node, the mapping relationship between
the task and the virtual resource node is:
1. To some extent, existing cloud computing task schedul-
ing algorithms are prone to fall into local optimization. ⎧ T1 V1 T2 V1 ⋯ Tn V1 ⎫
⎪ T V T V ⋯ Tn V2 ⎪
Based on the principle of cloud computing task schedul- =⎨ 1 2 2 2 (1)
⋮ ⋮ ⋮ ⎬
TVmap
ing, the proposed strategy proposes a scheduling model ⎪ ⋮ ⎪
⎩ T1 Vm T2 Vm ⋯ Tn Vm ⎭
using an improved ant colony algorithm. And combined
with the shortest waiting time, the degree of resource where Tn Vm represents the correspondence between sub-
load balancing and the cost of task completion and other tasks and virtual machines. Task scheduling will eventually
three goals to construct a task scheduling satisfaction achieve the goals of minimum average execution time, full
function to search the optimal solution of task schedul- resource utilization, and good service quality.
ing.
2. Aiming at the problem of unbalanced task scheduling 3.2 Scheduling model based on improved ant
in cloud computing, a virtual machine load weight coef- colony algorithm
ficient is introduced during the update of local phero-
mones. Introduce reward and punishment coefficients to In the process of solving the task scheduling problem using
optimize the pheromone algorithm’s pheromone update the ant colony algorithm, the pheromone 𝜏ij (t) and the heu-
rules, speed up the solution speed, and use the dynamic ristic function 𝜂ij (t) are initialized according to the process-
update of the volatility coefficient to optimize the overall ing power of the virtual machine for each task. And initialize
performance of the strategy. the task set E ,{Ek represents} the task set that the k ant can
choose, Ek = t1 , t2 , ⋯ tn . According to the pheromone

3 Model establishment

3.1 Principles of cloud computing task scheduling

The nodes in the cloud computing system have the charac-

teristics of complexity and heterogeneity. As the number
of users increases, user tasks in the cloud computing task
queue increase dramatically. How to efficiently perform
task scheduling and improve task execution efficiency and
resource utilization is the top priority of cloud computing
research (Ray et al. 2019). Cloud platform layer is the core
layer of cloud computing system, which mainly includes
user management, resource management, task management
and security management. Cloud application layer mainly Fig. 1  Diagram of cloud computing architecture

13
Task scheduling optimization strategy using improved ant colony optimization algorithm in…

After completing an iteration, pheromone 𝜏ij (t) is

updated to:
𝜏ij (t + 1) = 𝜌 ⋅ 𝜏ij (t) + Δ𝜏ij (t) (3)

In the formula, 𝜏ij (t) represents the amount of informa-

tion that virtual machine vj pairs with task ti at time t . The
pheromone volatility coefficient 𝜌 is expressed as the
degree of accumulation of pheromones. The purpose is to
prevent some pheromones from accumulating too much
during the accumulation process, causing the algorithm to
fall into a local optimal solution. Δ𝜏ij (t) represents the
pheromone increment of the pairing of virtual machine vj
∑
n
and task ti after this iteration, where: Δ𝜏ij (t) = Δ𝜏ijk (t) .
k=1
The expression of optimal solution fbest is:
{
fa (t), fa (t) ≤ fbest
fbest = (4)
fbest , others
n ( )
In the formula, fa (t)= min timek (t) represents the
k=1
global optimal solution of the t iteration. Its physical
meaning is the time to complete tasks, n represents the
number of ants.

3.3 Constructing an objective function for cloud

computing task scheduling

Comprehensive evaluation of the excellent performance

Fig. 2  Schematic diagram of cloud computing task scheduling of cloud computing task scheduling needs to be carried
out from different perspectives such as the minimum wait-
ing time of customers, the load balancing degree of vir-
concentration and heuristic function, calculate the pairing
tual machine resources, and the cost of task completion
probability pkij (t) of the task and the virtual machine:
(Karthikeyan et al. 2019).
⎧ �𝜏 (t)�𝛼 ⋅ �𝜂 (t)�𝛽
⎪ ij ij 1. Minimum user waiting time WTi:
⎪ ∑ � �𝛼 � �𝛽 , j ∈ Ak sum(vj )
pkij (t) = ⎨ 𝜏ij (t) ⋅ 𝜂ij (t) (2) m ∑
⎪ j∈Ak WTi = max timeij (5)
⎪ 0, others j=1
i=1
⎩

In the formula, Ak represents{the set of virtual

} machines In the formula: timeij represents the time required for
that the k ant can choose, Ak = v1 , v2 , ⋯ , vm . pkij (t) repre- task( ti )to process on the allocated virtual machine vj ;
sents the probability that ant K will assign task ti to virtual sum vj represents the total number of tasks allocated to
machine vj at the t iteration. In addition, tabu is used to virtual machine vj . In summary, the shortest client wait-
denote the taboo list. The path the ant travels will be added ing time WTi represents the maximum value of the latest
to the taboo list to prevent the path from being
/ repeated.
/ The completion time of task ti assigned by each virtual machine
heuristic function expression is: 𝜂ij (t) = 1 Dij, Dij = 1 timeij to complete processing.
represents the/ execution time of virtual machine vj on task
ti . timeij =TLi VSj (TLi represents the instruction length of 2. The degree of virtual machine resource load balancing
task ti , and VSj represents the execution speed of virtual 𝜑:
machine vj ). The smaller the execution time Dij is, the larger
the heuristic function 𝜂ij (t) is (Wu et al. 2019).

13
X. Wei

�
�m � �2 ⎧ 1 𝜑 ≤ 𝜑min
�∑
� VLj − VLj � ⎪
� 𝜑max − 𝜑 � �
� j=1 (6) ⎪ 𝜑 ∈ 𝜑min , 𝜑max
𝜑= n O(𝜑) = ⎨ WTmax − WTmin (10)
m ⎪𝜀
⎪ 𝜑 ≥ 𝜑max
⎩𝜑
In the formula: VLj represents the load on virtual machine
vj, that is, the total time of task execution on virtual machine vj. ⎧
VLj represents the average load on virtual machine vj, that is, ⎪ 1 Cvj ≤ Cmin
the average time spent on task execution on virtual machine vj. ⎪ � �
� � ⎪ Cmax − Cvj
O Cvj = ⎨ C − C Cvj ∈ Cmin , Cmax (11)
3. The cost of task completion C: ⎪ 𝜀max min
⎪ Cvj ≥ Cmax
∑
m
( ) ( ) ⎪ Cvj
Cvj = sum vj × vcpuj × vramj × vbwj (7) ⎩
j=1
The geometric average method is used to fuse the above
three objectives, and the comprehensive satisfaction evalu-
The above formula represents the cost of processing tasks ation of task scheduling is:
on virtual machine vj . The cost is related to the CPU (vcpuj ), √
memory (vramj ) and bandwidth performance (vbwj ) of virtual ( ) ( )
CS = 3 O WTi × O(𝜑) × O CVj (12)
machines.
Therefore, the performance of cloud computing task sched-
uling is comprehensively measured from the three objectives The geometric average method is used to convert the three
of the minimum waiting time of users, the load balancing evaluation objectives into comprehensive satisfaction CS .
degree of virtual machine resources, and the cost of task com- Therefore, the comprehensive satisfaction CS is 1 only if
pletion. The mathematical model is as follows: and only if the satisfaction of the three evaluation targets is
1 at the same time.
min WTi , min 𝜑, min C
∑
m
(8)
s.t. aij = 1 aij ∈ [0, 1] i = 1, 2, ⋯ , n
j=1 4 Algorithm optimization
In the formula: objective functions min WT , min 𝜑 and
and implementation
min C represent the minimum user waiting time, the load bal-
4.1 Task scheduling algorithm optimization
ancing degree of the virtual machine resources, and the cost
of task completion. And the constraint is that the task can only
Ant colony algorithm has the problems of slow convergence
be executed by one virtual machine.
and low search efficiency when searching for the optimal
In addition, the performance of task scheduling is not deter-
path. In response to this problem, reward and punishment
mined solely by an objective function. Therefore, the proposed
coefficients are introduced into the pheromone update for-
strategy constructs a task scheduling satisfaction function
mula of the ant colony algorithm. When an ant finds the
based on a priori preferences. Transform the multi-objective
best (i.e., the shortest) path in the process of traveling, it
problem of task scheduling into a single-objective problem.
will immediately “reward” the current path according to the
[Suppose the interval
] of the user’s shortest waiting time is
reward and punishment coefficient. That is, the correspond-
WTmin , WTmax , the satisfaction interval
[ of virtual
] machine
ing value is added to the pheromone, thereby enhancing the
resource load balancing degree[ is 𝜑min , 𝜑]max , and the cost
pheromone concentration of the path. If the current path
interval of task completion is Cmin , Cmax . Introducing the
is longer than the last path, the current path is “punished”
minimum value 𝜀, the three goals are calculated as follows:
according to the reward and punishment coefficient. That
⎧1 WTi ≤ WTmin is, subtract the corresponding value of the pheromone to
� � ⎪ WTmax −WTi � � weaken the pheromone concentration of the changed path.
O WTi = ⎨ WTmax −WTmin WTi ∈ WTmin , WTmax (9) In the entire search process of the current ant, through
⎪ 𝜀 WTi ≥ WTmax
⎩ WTi comparison, the longest path (that is, the worst solution) is
found. Severely punish it, that is, subtract the larger value
of the worst path pheromone according to the reward and

13
Task scheduling optimization strategy using improved ant colony optimization algorithm in…

punishment coefficient. This minimizes its interference with ⎧ 𝜌min , 𝜌a (t) < 𝜌min
the ants’ path selection. ⎪
𝜌(t) = ⎨ 𝜌a (t), 𝜌min ≤ 𝜌a (t) ≤ 𝜌max
Use 𝜏ij (t + 1) for the pheromone concentration after the
upd
⎪ 𝜌 , 𝜌 (t) ≥ 𝜌 (14)
update, and 𝜏ij (t) for the pheromone concentration before
bef
⎩ max a max

the update. During each ant search, the pheromone will be 𝜌a (t) = 1 − ln (t)∕ln (t + c)
updated according to the following update formula:
In the formula, c is a constant
[ and] the size of the volatility
⎧ bef 𝜔Q coefficient 𝜌 is limited to 𝜌min , 𝜌max . This prevents the value
⎪ 𝜏ij (t) + , L minimum
Lcur cur of 𝜌 from being too large or too small, resulting in slower
⎪
⎪ bef 𝜔Q solution efficiency or weaker search capabilities, to ensure
upd
𝜏ij (t + 1) = ⎨ 𝜏ij (t) − , L < Llast
Lcur cur (13) the overall performance of the algorithm.
⎪
⎪ bef 𝜔2 Q
⎪ 𝜏ij (t) − , L maximum
Lcur cur
⎩ 4.2 Implementation process of improved ant colony
optimization algorithm
In the formula, 𝜔 is the introduced reward and punish-
ment coefficient and Q is the load coefficient introduced by
The implementation steps of the improved ant colony opti-
the algorithm, which is a fixed constant. Lcur is the total
mization algorithm are as follows:
length of the current path and Llast is the total length of the
last path. When the optimal path occurs, L𝜔Q is added to the
cur Step 1: Initialize the algorithm;
current pheromone concentration as a reward. When a rela- Step 2: Randomly assign x ants to the corresponding vir-
tively poor path occurs, the current pheromone concentra- tual machines;
tion is subtracted from L𝜔Q as a penalty. When the worst path Step 3: Calculate the probability pkij of each ant moving
cur 2
occurs, the current pheromone concentration minus 𝜔L Q is to the next node. Then move the ant to the node indicated
cur
taken as a severe punishment. by the calculation result;
In addition, the reasonable setting of pheromone vola- Step 4: After the ant moves to the new node, update the
tilization coefficient 𝜌 will affect the search ability and pheromone of its path and modify the tabu list;
calculation efficiency of the algorithm to find the optimal Step 5: Repeat steps 2, 3, and 4 until each ant in the entire
distribution plan. By dynamically changing the value of 𝜌, ant colony finds a feasible path;
the size of the pheromone can be adjusted adaptively. There- Step 6: Evaluate all feasible paths according to the objec-
fore, it can effectively strengthen the early search ability of tive function of the cloud computing resource scheduling
the algorithm and enrich the diversity of solutions. And as problem and select the current optimal path;
the number of iterations increases, the probability of the Step 7: Globally update the pheromone on all paths;
optimal allocation scheme is improved, ensuring the overall Step 8: If the number of iterations reaches the preset num-
performance of the algorithm. The adjustment strategy of ber of iterations, the search is terminated and the optimal
volatility coefficient 𝜌 is: solution is obtained.

In order to realize the improved ant colony optimization

algorithm, its pseudo code is shown in Algorithm 1.

13
X. Wei

5.1 Experimental environment

CloudSim is a cloud computing emulator. The simulator

can quantify and compare the performance of different
scheduling strategies. It can adjust performance bottle-
necks before implementation, which can save costs. The
hardware environment used in experiments is a notebook
computer, the specific configuration as Intel(R) Core (TM)
i5-7300HQ CPU @2.8GHZ, RAM: 4 GB, 64-bit Windows
10 operating system. Use Intellij Idea to build a CloudSim
operating environment.
The execution steps of CloudSim are as follows:

1. Initialize CloudSim.
2. Create a DataCenter and ServiceBroker to coordinate
and allocate resources and create virtual machines.
3. Add the virtual machine to the virtual machine list, and
submit the virtual machine list to ServiceBroker at the
same time;
4. Create a cloud task set, add the cloud task Cloudlet to
the cloud task set, and submit it to ServiceBroker;
5. Start the simulation, and print the results after the simu-
lation.

5.2 Experimental parameter settings

In the process of applying the improved ant colony opti-

mization algorithm to solve the task scheduling problem,
first, according to the processing capacity of the virtual
machine for each task, the pairing probability of the task
and the virtual machine is calculated. The ants allocate
tasks according to the pairing probability. After complet-
ing an iteration, update the target solution and pheromone.
The target solution is obtained when the algorithm has
converged. Due to the randomly selected method and feed-
back mechanism, it will lead to slower convergence and
premature phenomenon.
Parameter setting: the number of tasks to be processed
is set to 40, 80, 120, 160 and 200, respectively. The com-
mand length of the task is 5000–500000 MI. The num-
ber of virtual machines is 80, and the execution speed
is 1000–3000 MIPS. Test simulation through multiple
experiments to set the algorithm parameters. The algo-
rithm parameters are shown in Table 1.

5 Experimental results and analysis

Table 1  Parameters of task scheduling algorithm
The proposed optimization strategy uses CloudSim 4.0 to Parameter Value Parameter Value
conduct simulation experiments to verify the feasibility of
𝛼 2 𝜌min 0.2
(Meshkati and Safi-Esfahani 2019), (Xie et al. 2019), refer-
𝛽 2 𝜌max 0.8
ence (Vila et al. 2019) and the proposed strategy in cloud
Q 100 𝜔 1.1
computing task scheduling under the same initial conditions.

13
Task scheduling optimization strategy using improved ant colony optimization algorithm in…

5.3 Comparison and analysis of experimental and Vila et al. (2019). Similarly, each algorithm is executed
results ten times, and the results are averaged. The results are shown
in Fig. 4.
5.3.1 Convergence speed It can be seen from Fig. 4 that the proposed optimiza-
tion strategy uses an improved ant colony optimization
In order to verify the convergence speed of the improved ant algorithm, which is superior to the algorithms in reference
colony optimization algorithm applied to task scheduling in Meshkati and Safi-Esfahani (2019), Xie et al. (2019) and
cloud computing, for different number of tasks, the proposed Vila et al. (2019) in task execution time. The task comple-
optimization strategies and the methods in Meshkati and tion time is related to the convergence speed. The faster the
Safi-Esfahani (2019), Xie et al. (2019) and Vila et al. (2019) convergence speed, the shorter the task scheduling comple-
were calculated to find the most The number of iterations tion time. (Meshkati and Safi-Esfahani 2019) improves the
during optimal solution. The data in each group is the aver- bee colony algorithm, which can improve the algorithm’s
age of 10 experiments. The experimental results are shown global search ability to a certain extent. But the method
in Fig. 3. convergence speed is slow, so the task scheduling takes a
As can be seen from Fig. 3, compared with other meth- long time to complete. Xie et al. (2019) selects the comput-
ods, the proposed optimization strategy requires the lowest ing resource with the largest credible dynamic level to per-
number of iterations to complete convergence. Because the form cloud tasks by evaluating the credibility of the nodes.
proposed optimization strategy optimizes the pheromone Compared with the (Meshkati and Safi-Esfahani 2019), its
update rule and automatically adjusts the pheromone’s vola- task scheduling speed is faster. Vila et al. (2019) proposed
tilization coefficient. This speeds up the solution speed of a dual-adaptive genetic algorithm based on time span and
the improved ant colony algorithm. As the number of itera- load balancing. It introduces variance to describe the load
tions increases, the probability of the optimal target solution density between nodes and the weight of multiple adapta-
will increase. Therefore, the calculation efficiency of the tion functions. Therefore, the convergence speed is faster
algorithm is further accelerated, and the performance of the and the time spent in the task scheduling process is shorter.
algorithm is better improved. In addition, as the number of But compared with the improved ant colony algorithm, its
tasks increases, the speed of convergence will slow down, dynamic adjustment characteristics are still lacking.
and it takes more time to process huge amounts of data.
5.3.3 Deadline incomplete rate
5.3.2 Task completion time of different algorithms
Deadline is the most basic requirement for task schedul-
In the same experimental environment, the improved ant ing, and also the basic index for evaluating task scheduling.
colony algorithm is compared with the algorithms in refer- When the scheduling algorithm schedules a large number
ence Meshkati and Safi-Esfahani (2019), Xie et al. (2019) of tasks, it is difficult to complete all data processing before
the deadline. The deadline unfinished rate is the ratio of

Fig. 3  The number of iterations of the algorithm Fig. 4  Task execution time comparison of different algorithms

13
X. Wei

the number of unfinished tasks to the total number of tasks

at the deadline. By setting different amounts of tasks and
comparing the deadline incomplete rate of each algorithm,
the results are shown in Fig. 5.
As can be seen from Fig. 5, the relationship between the
total number of different tasks and the deadline unfinished
rate. As the number of tasks increases, the proposed sched-
uling algorithm and (Vila et al. 2019) both maintain a low
deadline incomplete rate. Comparing the two, the unfinished
rate of the proposed scheduling algorithm is low, which has
been kept below 10%. Since the objective function of the
proposed scheduling algorithm has the shortest waiting time
as an evaluation constraint goal, its deadline completion rate
is low. Xie et al. (2019) only uses the deadline as a con-
straint, and the optimization algorithm is not improved in
place, which restricts the final scheduling result. Meshkati
and Safi-Esfahani (2019) mainly considers the load ratio of
Fig. 6  Comparison of algorithm load balance
tasks and resources. The task completion deadline is not
used as a constraint for task scheduling, resulting in a high
rate of unfinished task deadlines. of ensuring the load balancing degree. Therefore, the pro-
posed scheduling algorithm has more advantages overall.
5.3.4 Comparison of algorithm load balance The algorithms in Meshkati and Safi-Esfahani (2019) and
Xie et al. (2019), because the load balancing coefficients in
In the same experimental environment, the improved ant the objective functions of both are not dynamically adjusted,
colony algorithm is compared with the algorithms in refer- the task scheduling effect in cloud computing is not ideal.
ence Meshkati and Safi-Esfahani (2019), Xie et al. (2019)
and Vila et al. (2019) for load balancing. Similarly, each 5.3.5 Comparison of resource utilization of virtual
algorithm is executed ten times. The obtained results are machines with different algorithms
averaged, and the results are shown in Fig. 6.
It can be seen from Fig. 6 that the proposed scheduling In the case of N tasks, randomly select ten virtual machines
algorithm has obvious advantages in achieving load bal- (6, 15, 17, 28, 39, 49, 53, 66, 77, and 80), and compare and
ancing compared to the algorithms in Meshkati and Safi- analyze the resource utilization of each algorithm on the
Esfahani (2019), Xie et al. (2019) and Vila et al. (2019). virtual machine. As shown in Fig. 7.
Compared with the algorithm in (Vila et al. 2019), it can
effectively reduce the task execution time under the premise

Fig. 7  Comparison of resource utilization of virtual machine with dif-

Fig. 5  Deadline incomplete of different algorithms ferent algorithms

13
Task scheduling optimization strategy using improved ant colony optimization algorithm in…

As can be seen from Fig. 7, the resource utilization of will further optimize and improve the resource utilization of
each algorithm on different virtual machines. In the case of this algorithm, and will also conduct research on ensuring
a certain number of tasks, the task scheduling of the algo- QoS and reducing energy consumption in cloud data centers.
rithm in this paper is relatively balanced. Virtual machine
resources are more fully utilized, and resource utilization Acknowledgements This work was supported by the Young Backbone
Teachers Funding Project of Henan Colleges and Universities (No.
is always maintained at above 95%. (Vila et al. 2019) inte- 2017GGJS263)
grated task execution cost and execution energy consump-
tion to balance the load among virtual machines, and also
achieved good results. Its resource utilization rate has always
remained above 90%. Meshkati and Safi-Esfahani (2019) References
and Xie et al. (2019) take the deadline or the implementation
of comprehensive energy consumption as the evaluation tar- Abd Elaziz M, Xiong S, Jayasena KPN et al (2019) Task scheduling
get, and the virtual machine balance cannot be satisfactorily in cloud computing based on hybrid moth search algorithm and
considered. Their resource utilization fluctuates greatly, and differential evolution. Knowl-Based Syst 169(04):39–52
Boveiri HR, Khayami R, Elhoseny M et al (2019) An efficient
the load among virtual machines is not balanced. Swarm-Intelligence approach for task scheduling in cloud-
based internet of things applications. J Ambient Intell Humaniz
Comput 10(9):3469–3479
6 Conclusion Chen W, Wang D, Li K (2019) Multi-user multi-task computation
offloading in green mobile edge cloud computing. IEEE Trans
Serv Comput 12(5):726–738
Cloud computing is a large-scale complex system composed Domanal SG, Guddeti RMR, Buyya R (2020) A hybrid bio-inspired
of thousands of cloud resource nodes and communication algorithm for scheduling and resource management in cloud
links. In a cloud environment with countless resource nodes, environment. IEEE Trans Serv Comput 13(1):3–15
Garg S, Chaurasia PK (2019) Application of genetic algorithms
how to obtain reliable virtual machine resources and dis- task scheduling in cloud computing. Int J Comput Sci Eng
tribute cloud tasks to trusted resource nodes for execution 7(6):782–787
has become the key to ensuring the successful execution of Gong X, Liu Y, Lohse N et al (2019) Energy- and labor-aware pro-
parallel tasks. Aiming at the problem of unbalanced task duction scheduling for industrial demand response using adap-
tive multiobjective memetic algorithm. IEEE Trans Industr Inf
scheduling load and low reliability in cloud computing envi- 15(2):942–953
ronment, this paper proposes a task scheduling optimization Guo S, Liu J, Yang Y et al (2019) Energy-efficient dynamic computa-
strategy using improved ant colony optimization algorithm tion offloading and cooperative task scheduling in mobile cloud
in cloud computing. Based on the proposed model, a task computing. IEEE Trans Mob Comput 18(2):319–333
Haidri RA, Katti CP, Saxena PC (2019) Cost-effective deadline-
scheduling satisfaction function is constructed to search the aware stochastic scheduling strategy for workflow applications
optimal solution of task scheduling combined with the three on virtual machines in cloud computing. Concurr Comp-Pract
objectives of minimum waiting time, resource load balanc- Exper 31(7):1–24
ing degree and task completion cost. Among them, we make Hung PP, Alam G, Hai N et al (2019) A dynamic scheduling method
for collaborated cloud with thick clients. Int Arab J Inf Technol
improvements from the two aspects of pheromone update 16(4):633–643
and pheromone volatilization for ant colony algorithm to Jain R (2020) EACO: an enhanced ant colony optimization algo-
speed up the convergence speed. And the load weight coef- rithm for task scheduling in cloud computing. Int J Secur Appl
ficient of virtual machines is introduced in the update pro- 13(4):91–100
Karthikeyan T, Vinothkumar A, Ramasamy P (2019) Priority based
cess of local pheromone to achieve load balancing. Simula- scheduling in cloud computing based on task—aware technique.
tion experiments are conducted using CloudSim, which are J Comput Theor Nanosci 16(5):1942–1946
compared with algorithms in Meshkati and Safi-Esfahani Kaur A, Sood SK (2020) Cloud-Fog based framework for drought
(2019), Xie et al. (2019) and Vila et al. (2019), respectively. prediction and forecasting using artificial neural network and
genetic algorithm. J Exp Theor Artif Intell 32(2):273–289
The results verified the feasibility of proposed scheduling Kaur A, Kaur B, Singh D (2019) Meta-heuristic based framework
optimization strategy. This strategy reduces the task schedul- for workflow load balancing in cloud environment. Int J Inf
ing completion time and convergence time while ensuring Technol 11(1):119–125
load balancing, which improves the resource utilization of Khan WU, Ye Z, Altaf F et al (2019) A novel application of fireworks
heuristic paradigms for reliable treatment of nonlinear active
virtual machines. noise control. Appl Acoustics 146(MAR):246–260
In the next step, we will consider to further refine the Mansouri N, Zade BMH, Javidi MM (2019) Hybrid task scheduling
failure type of the resource cloud node and corresponding strategy for cloud computing by modified particle swarm opti-
recovery strategy and perform quantitative analysis. At the mization and fuzzy theory. Comput Ind Eng 130(04):597–633
Marahatta A, Wang Y, Zhang F et al (2019) Energy-aware fault-
same time, the corresponding task scheduling algorithm is tolerant dynamic task scheduling scheme for virtualized cloud
proposed combining communication link failure, resource data centers. Mobile Netw Appl 24(3):1063–1077
node failure and node local security factors. In addition, it

13
X. Wei

Matos JGD, Marques CKDM, Liberalino CHP (2019) Genetic and Wakil K, Badfar A, Dehghani P et al (2019) A fuzzy logic-based
static algorithm for task scheduling in cloud computing. Int J method for solving the scheduling problem in the cloud environ-
Cloud Comput 8(1):1–19 ments using a non-dominated sorted algorithm. Concurr Pract
Meshkati J, Safi-Esfahani F (2019) Energy-aware resource utilization Exper 31(17):1–12
based on particle swarm optimization and artificial bee colony Wang H, Xiao G, Wei Z et al (2019) Network optimisation for improv-
algorithms in cloud computing. J Supercomput 75(5):2455–2496 ing security and safety level of dangerous goods transportation
Nayak SC, Tripathy C (2019) An improved task scheduling mechanism based on cloud computing. Int J Inf Comput Secur 11(2):160–177
using multi-criteria decision making in cloud computing. Int J Inf Wu L, Tian X, Wang H et al (2019) Improved ant colony optimiza-
Technol Web Eng 14(2):92–117 tion algorithm and its application to solve pipe routing design.
Neelakanteswara P, Babu PS (2019) Efficient trust management tech- Assembly Autom 39(1):45–57
nique using neural network in cloud computing. J Comput Netw Xie Y, Zhu Y, Wang Y et al (2019) A novel directional and non-
Wirel Mobile Commun 9(1):29–40 local-convergent particle swarm optimization based workflow
Ray K, Sharma T K, Rawat S, et al (2019). [Advances in Intelligent scheduling in cloud-edge environment. Fut Gener Comput Syst
Systems and Computing] Soft computing: theories and applica- 97(08):361–378
tions volume 742 (Proceedings of SoCTA 2017) || a PSO algo- Yuan H, Bi J, Zhou MC (2019) Spatial task scheduling for cost minimi-
rithm-based task scheduling in cloud computing 10(27): 295–301 zation in distributed green cloud data centers. IEEE Trans Autom
Reddy GN, Kumar SP (2019) Regressive whale optimization for work- Sci Eng 16(2):729–740
flow scheduling in cloud computing. Int J Comput Intell Appl Zhang Y (2019) Classified scheduling algorithm of big data under
18(04):147–156 cloud computing. Int J Comput Appl 41(3–4):262–267
Selvakumar A, Gunasekaran G (2019) A novel approach of load bal- Zhou Z, Xie H, Li F (2019) A novel task scheduling algorithm inte-
ancing and task scheduling using ant colony optimization algo- grated with priority and greedy strategy in cloud computing. J
rithm. Int J Softw Innov 7(2):9–20 Intell Fuzzy Syst 37(4):1–9
Shao X, Xie Z (2019) A scheduling algorithm for applications in a
cloud computing system with communication changes. Expert Publisher’s Note Springer Nature remains neutral with regard to
Syst 36(2):1–18 jurisdictional claims in published maps and institutional affiliations.
Sreenu K, Malempati S (2019) MFGMTS: epsilon constraint-based
modified fractional grey wolf optimizer for multi-objective task
scheduling in cloud computing. IETE J Res 65(2):201–215
Vila S, Guirado F, Lerida JL et al (2019) Energy-saving scheduling on
laaS HPC cloud environments based on a multi-objective genetic
algorithm. J Supercomput 75(3):1483–1495

13