The International Arab Journal of Information Technology, Vol. 12, No.

2, March 2015 129

Cloud Task Scheduling Based on Ant Colony

Optimization
Medhat Tawfeek, Ashraf El-Sisi, Arabi Keshk and Fawzy Torkey
Faculty of Computers and Information, Menoufia University, Egypt

Abstract: Cloud computing is the development of distributed computing, parallel computing and grid computing, or defined
as the commercial implementation of these computer science concepts. One of the fundamental issues in this environment is
related to task scheduling. Cloud task scheduling is an NP-hard optimization problem and many meta-heuristic algorithms
have been proposed to solve it. A good task scheduler should adapt its scheduling strategy to the changing environment and
the types of tasks. In this paper, a cloud task scheduling policy based on Ant Colony Optimization (ACO) algorithm compared
with different scheduling algorithms First Come First Served (FCFS) and Round-Robin (RR), has been presented. The main
goal of these algorithms is minimizing the makespan of a given tasks set. ACO is random optimization search approach that
will be used for allocating the incoming jobs to the virtual machines. Algorithms have been simulated using cloudsim toolkit
package. Experimental results showed that cloud task scheduling based on ACO outperformed FCFS and RR algorithms.

Keywords: Cloud computing, task scheduling, makespan, ACO, cloudsim.

Received July 3, 2013; accepted September 2, 2013; published online April 23, 2014

1. Introduction problem, vehicle routing problem and scheduling

problem [5, 8]. In this paper, we use ACO algorithm to
Cloud computing is associated with a new paradigm for find the optimal resource allocation for tasks in the
provisioning different computing resources, usually dynamic cloud system to minimize the makespan of
addressed from three fundamental aspects: tasks on the entire system. Then, this scheduling
Infrastructure as a Service (IaaS), Platform as a Service strategy was simulated using the cloudsim toolkit
(PaaS) and Software as a Service (SaaS) [20]. Due to package. Experimental results compared to First Come
fast growth of cloud computing in the IT landscape, First Served (FCFS) and Round Robin (RR) showed
several definitions have emerged. The cloud computing the ACO algorithm satisfies expectation. The
can be defined as a type of parallel and distributed organization of paper is as following: Section 2
system consisting of a collection of inter-connected and introduces background and scans the related work.
virtualized computers that are dynamically provisioned Cloudsim toolkit is presented in section 3. Section 4
and presented as one or more unified computing covers the basic ACO and the details of cloud
resource(s) based on service-level agreements scheduling based ACO algorithm. The implementation
established through negotiation between the service and simulation results are seen in section 5. Finally,
provider and consumers [8]. With the support of section 6 concludes this paper.
virtualization technology cloud platforms enable
enterprises to lease computing power in the form of
virtual machines to users [6]. Because hundreds of 2. Background and Related Work
thousands of Virtual Machines (VMs) are used, it is 2.1. Cloud Computing Environment
difficult to manually assign tasks to computing
resources in clouds [17]. So, we need an efficient Cloud computing is a virtual pool of resources which
algorithm for task scheduling in the cloud environment. are provided to users. It gives users virtually unlimited
A good task scheduler should adapt its scheduling pay-per-use computing resources without the burden
strategy to the changing environment and the types of of managing the underlying infrastructure. The goal of
tasks [7]. Therefore, a dynamic task scheduling cloud computing service providers is to use the
algorithm, such as Ant Colony Optimization (ACO), is resources efficiently and gain maximum profit [16].
appropriate for clouds. ACO algorithm is a random This leads to task scheduling as a core and challenging
search algorithm [4]. This algorithm uses a positive issue in cloud computing. Cloud has an extra layer
feedback mechanism and imitates the behaviour of real called virtualization layer. This layer acts as a creation,
ant colonies in nature to search for food and to connect execution, management and hosting environment for
to each other by pheromone laid on paths travelled. application services [11]. The modelled VMs in the
Many researchers used ACO to solve NP-hard problems above virtual environment are contextually isolated
such as travelling salesman problem, graph colouring but, still they need to share computing resources-
130 The International Arab Journal of Information Technology, Vol. 12, No. 2, March 2015

processing cores, system bus etc., [21]. Hence, the exploiting the search space, learning strategies are
amount of hardware resources available to each VM is used to structure information in order to find
constrained by the total processing powers such CPU, efficiently near-optimal solutions [18].
the memory and system bandwidth available within the
host [21]. 2.3. Related Work
2.2. Combinatorial Optimization Problem Millions of user share cloud resources by submitting
their computing task to the cloud system. Scheduling
In combinatorial optimization problems, we are looking these millions of task is a challenge to cloud
for an object from a finite or possibly countably infinite computing environment. Optimal resource allocation
set. This object is typically an integer number, a subset, or task scheduling in the cloud should decide optimal
a permutation or a graph structure [15]. A combinatorial number of systems required in the cloud so that the
optimization problem P=(S, f) can be defined by: total cost is minimized. Cloud service scheduling is
• A set of variables X ={x1, x2, …, xn}. categorized at user level and system level [6]. At user
• Variable domains D1, …, Dn. level scheduling deals with problems raised by service
• Constraints among variables. provision between providers and customers [17, 21].
The system level scheduling handles resource
• An objective function f to be minimized where,
f: D1*…* Dn →R+. management within data centers [8, 11, 16]. A novel
approach of heuristic-based request scheduling at each
The set of all possible feasible assignments is: S={s= server, in each of the geographically distributed data
{(x1,v1), …, (xn,vn)}|vi ∈ Di, s satisfies all the constraints} centers, to globally minimize the penalty charged to
S is usually called a search (or solution) space, as each the cloud computing system is proposed in [1]. A
element of the set can be seen as a candidate solution. new fault tolerant scheduling algorithm MaxRe is
To solve a combinatorial optimization problem one has proposed in [23]. This algorithm incorporates the
to find a solution s* ∈ S with minimum objective reliability analysis into the active replication schema
function value [15]. Examples for, combinatorial and exploits a dynamic number of replicas for
optimization problems are the Travelling Salesman different tasks. Scheduling based genetic algorithm is
Problem (TSP), the Quadratic Assignment Problem proposed in [12, 14, 22]. This algorithms optimizes the
(QAP), time tabling and scheduling problems. Due to energy consumption, carbon dioxide emissions and
the practical importance of combinatorial optimization the generated profit of a geographically distributed
problems, many algorithms to tackle them have been cloud computing infrastructure. The QoS Min-Min
developed. These algorithms can be classified as either scheduling algorithm is proposed in [10]. An
complete or approximate algorithms. Complete optimized algorithm for VM placement in cloud
algorithms are guaranteed to find for every finite size computing scheduling based on multi-objective ant
instance of a combinatorial optimization problem an colony system algorithm in cloud computing is
optimal solution in bounded time. In approximate proposed in [8]. Scheduling in grid environment based
methods we sacrifice the guarantee of finding optimal ACO algorithms are proposed in [13, 14, 19]. The
solutions for the sake of getting good solutions in a existing scheduling techniques in clouds, consider
significantly reduced amount of time especially for parameter or various parameters like performance,
combinatorial optimization problems that are NP-hard makespan, cost, scalability, throughput, resource
[18]. Among the basic approximate methods we usually utilization, fault tolerance, migration time or
distinguish between constructive methods and local associated overhead. In this paper, cloud task
search methods. Constructive algorithms generate scheduling based ACO approach has been presented
solutions from scratch by adding components to an for allocation of incoming jobs to VMs considering in
initially empty partial solution until a solution is our account only makespan to help in utilizing the
complete. Local search algorithms start from some available resources optimally, minimize the resource
initial solution and iteratively try to replace the current consumption and achieve a high user satisfaction.
solution by a better solution in an appropriately defined
neighbourhood of the current solution [15]. In past, four
decades, a new kind of approximate algorithm has
3. Cloudsim
emerged which basically tries to combine basic Simulation is a technique where a program models the
heuristic methods in higher level frameworks aimed at behaviour of the system (CPU, network etc.,) by
efficiently and effectively exploring a search space. calculating the interaction between its different entities
This class of algorithms includes ACO, simulated using mathematical formulas, or actually capturing and
annealing, tabu search and others [18]. A metaheuristic playing back observations from a production system
is formally defined as an iterative generation process [3]. Cloudsim is a framework developed by the
which guides a subordinate heuristic by combining GRIDS laboratory of university of Melbourne which
intelligently different concepts for exploring and enables seamless modelling, simulation and
Cloud Task Scheduling Based on Ant Colony Optimization 131

experimenting on designing cloud computing • Data Center Broker: It models a broker, which is
infrastructures [3]. responsible for mediating negotiations between
SaaS and cloud providers.
3.1. Cloudsim Characteristics • VM Allocation: A provisioning policy which is run
Cloudsim can be used to model datacenters, host, in data center level helps to allocate VMs to hosts.
service brokers, scheduling and allocation policies of a • VM Scheduler: This is an abstract class
large scaled cloud platform. Hence, the researcher has implemented by a host component that models the
used cloudsim to model datacenters, hosts, VMs for policies (space-shared, time-shared) required for
experimenting in simulated cloud environment [9]. allocating processor cores to VMs. It is run on
Cloud supports VM provisioning at two levels: every host in data center.
• Host: It models a physical server.
1. At the host level: It is possible to specify how much • VM: It models a VM which is run on cloud host to
of the overall processing power of each core will be deal with the cloudlet.
assigned to each VM known as VM policy • Cloudlet: It models the cloud-based application
Allocation. services.
2. At the VM level: The VM assigns a fixed amount of • Cloudlet Scheduler: This abstract class is extended
the available processing power to the individual by the implementation of different policies that
application services (task units) that are hosted determine the share (space-shared, time-shared) of
within its execution engine known as VM processing power among cloudlets in a VM [9].
Scheduling [9].
In this paper, the ACO algorithm will be used for CIS

allocation of incoming batch jobs to VMs at the VM Data Center

level (VM Scheduling). All the VMs in a data center 1
Data Center Broker
not necessary have a fixed amount of processing power
n
but, it can vary with different computing nodes, and
Host VM Allocation
then to these VMs of different processing powers, the 1
tasks/ requests (application services) are assigned or
allocated to the most powerful VM and then to the n VM Scheduler
lowest and so on. Hence, the performance parameter VM
such as overall makespan time is optimized (increasing 1

resource utilization ratio) and the cost will be Cloudlet Scheduler

decreased. n
Cloudlet

3.2. Cloudsim Data Flow Figure 1. Main parts of cloudsim related to our experiments.

Each datacenter entity registers with the Cloud

Information Service registry (CIS). CIS provides 4. Cloud Scheduling Based ACO
database level match-making services; it maps user The basic idea of ACO is to simulate the foraging
requests to suitable cloud providers. The data center behaviour of ant colonies. When an ants group tries to
broker consults the CIS service to obtain the list of
search for the food, they use a special kind of chemical
cloud providers who can offer infrastructure services
that match application’s quality of service, hardware to communicate with each other. That chemical is
and software requirements. In the case match occurs the referred to as pheromone. Initially, ants start search
broker deploys the application with the cloud that was their foods randomly. Once the ants find a path to food
suggested by the CIS [3]. source, they leave pheromone on the path. An ant can
follow the trails of the other ants to the food source by
3.3. The Cloudsim Platform sensing pheromone on the ground. As this process
continues, most of the ants attract to choose the
The main parts of cloudsim that are related to our shortest path as there have been a huge amount of
experiments in this paper and the relationship between pheromones accumulated on this path [4]. The
them are shown in Figure 1. advantages of the algorithm are the use of the positive
• CIS: It is an entity that registers data center entity feedback mechanism, inner parallelism and extensible.
and discovers the resource. The disadvantages are overhead and the stagnation
• Data Center: It models the core infrastructure-level phenomenon, or searching for to a certain extent, all
services (hardware), which is offered by cloud individuals found the same solution exactly, can’t
providers. It encapsulates a set of compute hosts that further search for the solution space, making the
can either be homogeneous or heterogeneous. algorithm converge to local optimal solution [4]. It is
132 The International Arab Journal of Information Technology, Vol. 12, No. 2, March 2015

clear that an ACO algorithm can be applied to any The pseudo code of the proposed ACO algorithm and
combinatorial problem as far as it is possible to define: scheduling based ACO algorithm are shown in
Algorithms 1 and 2 respectively.
1. Problem representation which allows ants to The main operations of the ACO procedure are
incrementally build/ modify solutions. initializing pheromone, choosing VM for next task
2. The heuristic desirability η of edges. and pheromone updating as following:
3. A constraint satisfaction method which forces the
Algorithm 1: ACO algorithm
construction of feasible solutions.
4. A pheromone updating rule which specifies how to Input: List of Cloudlet (Tasks) and List of VMs
modify pheromone trail τ on the edges of the graph. Output: The best solution for tasks allocation on VMs Steps:
5. A probabilistic transition rule of the heuristic 1. Initialize:
desirability and of pheromone trail [2]. Set Current_iteration_t=1.
Set Current_optimal_solution=null.
In this section, cloud task scheduling based ACO Set Initial value τij(t)=c for each path between tasks and VMs.
algorithm will be proposed. Decreasing the makespan 2. Place m ants on the starting VMs randomly.
3. For k:=1 to m do
of tasks is the basic ideas from the proposed method. Place the starting VM of the k-th ant in tabuk.
1. Problem Representation: The problem is represented Do ants_trip while all ants don't end their trips
Every ant chooses the VM for the next task according to
as a graph G=(N, E) where the set of nodes N Equation 1.
represents the VMs and tasks and the set of edges E Insert the selected VM to tabuk.
the connections between the task and VM as shown End Do
in Figure 2. All ants are placed at the starting VMs 4. For k:=1 to m do
Compute the length Lk of the tour described by the k-th ant
randomly. During an iteration ants build solutions to
according to Equation 4.
the cloud scheduling problem by moving from one Update the current_optimal_solution with the best founded
VM to another for next task until they complete a solution.
tour (all tasks have been allocated). Iterations are 5. For every edge (i, j), apply the local pheromone according to
indexed by t, 1< t< tmax, where tmax is the Equation 5.
6. Apply global pheromone update according to Equation 7.
maximum number of iterations allowed. 7. Increment Current_iteration_t by one.
8. If (Current_iteration_t < tmax)
Empty all tabu lists.
T1 VM1 Goto step 2
Else
Print current_optimal_solution.
T2 End If
VM2
9. Return
.
T3 . Algorithm 2: Scheduling based ACO algorithm
. .
Input: Incoming Cloudlets and VMs List
. VMn Output: Print “scheduling completed and waiting for more
. Cloudlets”Steps:
Tn VMs
1. Set Cloudlet List=null and temp_List_of_Cloudlet=null
Tasks
2. Put any incoming Cloudlets in Cloudlet List in order of their
arriving time
Figure 2. Problem representation of task scheduling based ACO. 3. Do ACO_P while Cloudlet List not empty or there are more
incoming Cloudlets
2. Heuristic Desirability: A very simple heuristic is Set n= size of VMs list
used the inverse of expected execution time of the If (size of Cloudlet List greater than n)
task i on VM j. Transfer the first arrived n Cloudlets from Cloudlet List
3. Constraint Satisfaction: The constraint satisfaction and put them on temp_List_of_Cloudlet
method is implemented as a simple, short-term Else
Transfer all Cloudlets.from Cloudlet List and put them on
memory of the visited VM, in order to, avoid visiting temp_List_of_Cloudlet
a VM more than once in one ACO procedure and End If
minimize time of the assigned couplings (task and Execute ACO procedure with input temp_List_of_Cloudlet
VM). and n
4. Pheromone Updating Rule: It is the one typical of End Do
ant system as shown in Equations 3, 4, 5, 6 and 7. 4. Print “scheduling completed and waiting for more Cloudlets”
5. Stop
Pheromone evaporates on all edges and new
pheromone is deposited by all ants on visited edges;
its value is proportional to the quality of the solution 4.1. Initializing Pheromone
built by the ants. The amount of virtual pheromone trail τij(t) on the
5. Probabilistic Transition Rule: The probabilistic edge connects task i to VMj. The initial amount of
transition rule, called random proportional, is the one pheromone on edges is assumed to be a small positive
typical of ant system as shown in Equation 1.
Cloud Task Scheduling Based on Ant Colony Optimization 133

constant τ0 (homogeneous distribution of pheromone at ∆τ ij (t ) = ∑ m

k
k =1 ∆τ (t ) (6)
time t=0). ij

When all ants complete a traverse, an elitist is an ant

4.2. VM Choosing Rule for Next Task which reinforces pheromone on the edges belonging to
During an iteration of the ACO algorithm each ant k, the best tour found from the beginning of the trial (T+),
k=1, ..., m (m is the number of the ants), builds a tour by a quantity Q/L+, where L+ is the length of the best
executing n (n is number of tasks) steps in which a tour (T+). This reinforcement is called global
probabilistic transition rule is applied. The k-ant pheromone update and computed by Equation 7.
chooses VMj for next task i with a probability that is Q
computed by Equation 1. τ ij (t ) = τ ij (t ) + if (i, j ) ∈T + (7)
L+
α β
 [τ ij (t )] * [η ij ]
 if j ∈ allowed k
k  ∑ s ∈allow ed k [τ is (t )]α * [η is ]β 5. Implementation and Experimental
p ij (t ) =  (1)
 Results
 0 otherwise
We assume that tasks are mutually independent i.e.,
Where, τij(t) shows the pheromone concentration at the there is no precedence constraint between tasks and
t time on the path between task i and VMj, allowed tasks are not preemptive and they cannot be
k={0,1,…,n-1}-tabuk express the allowed VMs for ant k interrupted or moved to another processor during their
in next step and tabuk records the traversed VM by execution.
ant k, and ηij=1/dij is the visibility for the t moment,
calculated with heuristic algorithm and dij which 5.1. Parameters Setting of Cloudsim
expresses the expected execution time and transfer time
of the task i on VMj can be computed with Equation 2. The experiments are implemented with 10 Datacenters
with 50 VMs and 100-1000 tasks under the simulation
TL _ Task i InputFileSize platform. The length of the task is from 1000 Million
d ij = + (2)
Pe _ num j * Pe _ mips j VM _ bw j Instructions (MI) to 20000 MI. The parameters setting
of cloud simulator are shown in Table 1.
Where, TL_Taski is the total length of the task that has
been submitted to VMj, Pe_numj is the number of VMj Table 1. Parameters setting of cloudsim.
processors, Pe_mipsj is the MIPS of each processor of Entity Type Parameters Value
VMj, InputFileSize is the length of the task before Task (cloudlet)
Length of Task 1000-20000
execution and VM_bwj is the communication bandwidth Total Number of Task 100-1000
Total Number of VMs 50
ability of the VMj. Finally, the two parameters α and β
MIPS 500-2000
in Equation 1 are used to control the relative weight of VM Memory(RAM) 256-2048
the pheromone trail and the visibility information Virtual Machine Bandwidth 500-1000
respectively. Space_shared and
Cloudlet Scheduler
Time_shared
Number of PEs Requirement 1-4
4.3. Pheromone Updating Number of Datacenter 10
Number of Host 2-6
After the completion of a tour, each ant k lays a quantity Data Center
Space_shared and
of pheromone ∆ τijk(t) computed by Equation 3 on each VM Scheduler
Time_shared
edge (i, j) that it has used.
 Q
5.2. ACO Parameters Evaluation and Setting

k
k if ( i , j ) ∈ T (t )
∆τ ij (t ) =  Lk (t ) (3) We implemented the ACO algorithm and investigated
 0 k
if ( i , j ) ∉ T (t ) their relative strengths and weaknesses by
experimentation. The parameters (α, β, p, tmax, m the
Where, Tk(t) is the tour done by ant k at iteration t, Lk(t) number of ants and Q) considered here are those that
is its length (the expected makespan of this tour) that is affect directly or indirectly the computation of the
computed by Equation 4 and Q is a adaptive parameter. algorithm. We tested several values for each parameter
Lk (t )=arg max j ∈J {sumi ∈IJ (d ij )} (4) while all the others were held constant on 100 tasks.
The default value of the parameters was α=1, β=1,
Where, ij is the set of tasks that assigned to the VMj. ρ=0.5, Q=100, tmax=150 and m=8. In each experiment
After each iteration pheromone updating which is only one of the values was changed, The values tested
applied to all edges is refreshed by Equation 5. were: α ∈ {0, 0.1, 0.2, 0.3, 0.4, 0.5}, β ∈ {0, 0.5, 1.5, 2,
2.5, 3}, ρ ∈ {0, 0.1, 0.2, 0.3, 0.4, 0.5}, Q ∈ {1, 100, 500,
τ ij (t ) = (1 − ρ )τ ij (t ) + ∆τ ij (t ) (5) 1000}, tmax ∈ {50, 75, 100, 150} and m ∈ {1, 5, 8, 10,
Where, ρ is the trail decay, 0< ρ< 1 and ∆τij(t) is 15, 20}. We also use the time in the cloudSim to
computed by Equation 6. record the makespan. The ACO performance for
134 The International Arab Journal of Information Technology, Vol. 12, No. 2, March 2015

different values of parameters (α, β, p, tmax, m the 120

100
number of ants and Q) has been evaluated. The ACO 100
74.98 73 75 73.29
performance for different values of parameters (m: The 80 67

Makespan
number of ants, tmax, Q, ρ, α and β) are shown from 60
Figures 3 to 8. It can be seen that the best value of α is 40
0.3, the best value of β is 1, the best value of ρ is 0.4, 20
the best value of Q is 100, the best value of tmax is 150 0
and the best values of m is 10. In the following 0 0.1 0.2 α 0.3 0.4 0.5
experiments we select the best value for α, β, ρ, Q and β=1, ρ=0.4, Q=100, tmax=100 and m=10.
m parameters but, the value 100 is selected for the tmax Figure 7. ACO performance for different values of alpha.
parameter to reduce the overhead of the ACO
algorithm. Table 2 shows the selected best parameters 120
100
of ACO. 100
73 72 73
80 67 67

Makespan
140 60
117
120 104 40
100 83 80 20
77 76
Makespan

80
0
60
0 0.5 1 1.5 2 2.5
40 β
α=0.3, ρ=0.5, Q=100, tmax=100 and m=10.
20
0 Figure 8. ACO performance for different values of beta.
1 5 8 M 10 15 20
α=1, β=1, r=0.5, Q=100, and tmax=200. Table 2. Selected parameters Of ACO.

Figure 3. ACO performance for different values of ant numbers. Parameter α β ρ Q m tmax

Value 0. 3 1 0.4 100 10 100

90
87
85
80
5.3. Implementation Results of ACO, FCFS
and RR
Makespan

80
76
75
74
75 The following experiments, we compared the average
70
makespan with different tasks set. The average
makespan of the ACO, RR and FCFS algorithms are
65 shown in Figure 9. It can be seen that, with the
50 75 tmax 100 125 150 increase of the quantity task, ACO takes the time less
α=1, β=1, r=0.5, Q=100 and m=10. than RR and FCFS algorithms. This indicates that
Figure 4. ACO performance for different values of tmax. ACO algorithm is better than RR and FCFS
75.5
algorithms.
75
75
1200
74.5 74
Makespan

74 1000 FCFS
73.5 800 RR
Makespan

73 73
73 600 ACO
72.5
400
72
200
1 100 Q 500 1000
0
α=1, β=1, r=0.5, tmax=100 and m=10.

Figure 5. ACO performance for different values of Q.

Number of Tasks
140
118 Figure 9. Average makespan of FCFS, RR and ACO.
120 103
100 87 84
In statistics and probability theory, standard
Makespan

80 71 70.5

60
deviation (σ) shows how much variation or dispersion
40 exists from the average (mean), or expected value. A
20 low standard deviation indicates that the data points
0 tend to be very close to the mean; high standard
0 0.1 0.2
ρ
0.3 0.4 0.5 deviation indicates that the data points are spread out
α=1, β=1, Q=100, tmax=100 and m=10. over a large range of values (solving stagnation
Figure 6. ACO performance for different values of RHO.
problem). Since, the standard deviation of never drops
Cloud Task Scheduling Based on Ant Colony Optimization 135

to zero, we are assured that the algorithm actively Also, the comparison between our approach and other
searches solutions which differ from the best-so-far metaheuristics approaches will be performed.
found, which gives it the possibility of finding better
ones. Figure 10 shows the evolution of the standard References
deviation of the ACO over 10 runs.
[1] Boloor K., Chirkova R., Salo T., and Viniotis
7 Y., “Heuristic-Based Request Scheduling
6 Subject to a Percentile Response Time SLA in
Standard Deviation

5
a Distributed Cloud,” in Proceedings of the
4
3
IEEE International Conference on Global
2 Telecommunications Conference, Florida, USA,
1 pp. 1-6, 2010.
0 [2] Bonabeau E., Dorigo M., and theraulaz G.,
Swarm Intelligence: From Natural to Artificial
Number of Tasks Intelligence, Oxford University Press, New
Figure 10. Standard deviation of ACO over 10 runs. York, USA, 1999.
[3] Buyya R., Ranjan R., and Calheiros N.,
The Degree of Imbalance (DI) measures the “Modeling and Simulation of Scalable Cloud
imbalance among VMs, which is computed by Computing Environments and the CloudSim
Equations 8 and 9. Toolkit: Challenges and Opportunities,” in
TL _ Tasks Proceedings of the 7th High Performance
Ti = (8)
Pe _ num j * Pe _ mips j Computing and Simulation Conference, Leipzig,
Germany, pp. 1-11, 2009.
Where, TL_Tasks is the total length of tasks which are [4] Dorigo M. and Blum C., “Ant Colony
submitted to the VMi. Optimization Theory: A Survey,” in Theoretical
T max − T min
Computer Science, vol. 344, no. 2, pp. 243-278,
DI = (9) 2005.
T avg
[5] Dorigo M., Birattari M., and Stutzel T., “Ant
Where, Tmax, Tmin and Tavg are the maximum, minimum Colony Optimization,” IEEE Computational
and average Ti respectively among all VMs. The Intelligence Magazine, vol. 1, no. 4, pp. 28-39,
average DI of each algorithm with the number of tasks 2006.
varying from 100 to 1000 is shown in Figure 11. It can [6] Fangzhe C., Ren J., and Viswanathan R.,
be seen that the ACO can achieve better system load “Optimal Resource Allocation in Clouds,” in
balance than RR and FCFS algorithms. Proceedings of the 3rd International Conference
on Cloud Computing, Florida, USA, pp. 418-
4.5 425, 2010.
[7] Gao K., Wang Q., and Xi L., “Reduct Algorithm
Degree of Imbalance (DI)

4
3.5 FCFS
3 Based Execution Times Prediction in
2.5 RR Knowledge Discovery Cloud Computing
2
1.5
ACO Environment,” the International Arab Journal of
1 Information Technology, vol. 11, no. 3, pp. 268-
0.5 275, 2014.
0
[8] Gao Y., Guan H., Qi Z., Hou Y., and Liu L., “A
Multi-Objective Ant Colony System Algorithm
Number of Tasks for Virtual Machine Placement in Cloud
Figure 11. Average DI of FCFS, RR and ACO. Computing,” Journal of Computer and System
Sciences, vol. 79, no. 8, pp. 1230-1242, 2013.
[9] Ghalem B., Tayeb F., and Zaoui W.,
6. Conclusions and Future Work
“Approaches to Improve the Resources
In this paper, ACO algorithm for achieving cloud Management in the Simulator Cloudsim,” in
computing tasks scheduling has been presented. Firstly, Proceedings of the Conference on Interaction
the best values of parameters for ACO algorithm, and Confidence Building Measures in Asia,
experimentally determined. Then, the ACO algorithm Lecture Notes in Computer Science, Istanbul,
in applications with the number of tasks varying from Turkey, pp. 189-196, 2010.
100 to 1000 evaluated. Simulation results demonstrate [10] Hsu C. and Chen T., “Adaptive Scheduling
that ACO algorithm outperforms FCFS and RR Based on Quality of Service in Heterogeneous
algorithms. In future work the effect of precedence Environments,” in Proceedings of the IEEE
between tasks and load balancing will be considered. International Conference on Multimedia and
136 The International Arab Journal of Information Technology, Vol. 12, No. 2, March 2015

Ubiquitous Engineering, California, USA, pp. 1- Genetic Algorithm in Cloud Computing,” in

6, 2010. Proceedings of the IEEE International
[11] Ijaz S., Munir E., Anwar W., and Nasir W., Conference on Wireless Communications,
“Efficient Scheduling Strategy for Task Graphs in Networking and Mobile Computing, China, pp.
Heterogeneous Computing Environment,” the 1-4, 2009.
International Arab Journal of Information [23] Zhao L., Ren Y., Xiang Y., and Sakurai K.,
Technology, vol 10, no. 5, pp. 486-492, 2013. “Fault-Tolerant Scheduling with Dynamic
[12] Kessaci Y., Melab N., and Talbi E., “A Pareto- Number of Replicas in Heterogeneous Systems,”
Based GA for Scheduling HPC Applications on in Proceedings of the IEEE International
Distributed Cloud Infrastructures,” in Conference on High Performance Computing
Proceedings of the IEEE International and Communications, Washington, USA, pp.
Conference on High Performance Computing and 434-441, 2010.
Simulation, Istanbul, Turkey, pp. 456-462, 2011. [24] Zhu K., Song H., Liu L., Gao J., and Cheng G.,
[13] Lorpunmanee S., Sap M., Abdul A., and “Hybrid Genetic Algorithm for Cloud
Chompoo C., “An Ant Colony Optimization for Computing Applications,” in Proceedings of the
Dynamic Job Scheduling in Grid Environment,” IEEE International Conference on Asia-Pacific
in Proceedings of World Academy of Science, Services Computing Conference, Jeju, Korea, pp.
English and Technology, 2007. 182-187, 2011.
[14] Mahamud K. and Nasir H., “Ant Colony
Algorithm for Job Scheduling in Grid Medhat Tawfeek received the BSc
Computing,” in Proceedings of the 4th Asia and MSc degrees in computers and
International Conference on Mathematical/ information from Menofia
Analytical Modelling and Computer Simulation, University, Faculty of Computers
Kota Kinabalu, Malaysia, pp. 40-45, 2010. and Information in 2005 and 2010,
[15] Nemhauser G. and Wolsey A., Integer and respectively. Currently, hold PhD
Combinatorial Optimization, John Wiley and degree student in Faculty of
Sons, New York, USA, 1988. Computers and information, Menofia University. His
[16] Paul M. and Sanyal G., “Survey and Analysis of research interest includes cloud computing, smart card
Optimal Scheduling Strategies in Cloud security, distributed system, fault tolerance.
Environment,” in Proceedings of the IEEE
International Conference on Information and Ashraf El-Sisi received the BSc
Communication Technologies, Georgia, USA, pp. and MSc degrees in electronic
789-792, 2012. engineering and computer science
[17] Qiyi H. and Tinglei H., “An Optimistic Job engineering from Menofyia
Scheduling Strategy based on QoS for Cloud University, Faculty of Electronic in
Computing,” in Proceedings of the IEEE 1989 and 1995, respectively and
International Conference on Intelligent received his PhD degree in
Computing and Integrated Systems, Guilin, computer engineering and control from Zagazig
China, pp. 673-675, 2010. University, Faculty of Engineering in 2001. His
[18] Reeves C., Modern Heuristic Techniques for research interest includes cloud computing, privacy
Combinatorial Problems, Blackwell Scientific preserving data mining, AI approaches in software
Publishing, Oxford, England, 1993. testing, intelligent agent, testing biometric security
[19] Singh M., “GRAAA: Grid Resource Allocation algorithms and devices, and intelligent systems.
Based on Ant Algorithm,” the Journal of
Advances in Information Technology, vol. 1, no. Arabi Keshk received the BSc
3, pp.133-135, 2010. degree in electronic engineering and
[20] Weiss A., “Computing in the Clouds,” Net MSc degree in computer science
Worker on Cloud computing: PC functions move and engineering from Menofia
onto the web, vol. 11, no. 4, pp. 16-25, 2007. University, Faculty of Electronic
[21] Xu M., Cui L., Wang H., and Bi Y., “A Multiple Engineering in 1987 and 1995,
QoS Constrained Scheduling Strategy of Multiple respectively and received his PhD
Workflows for Cloud Computing,” in degree in electronic engineering from Osaka
Proceedings of the IEEE International University, Japan in 2001. His research interest
Conference on Parallel and Distributed includes software testing, distributed system, data
Processing with Applications, Chendu and mining and bioinformatics.
JiuZhai Valley, China, pp. 629-634, 2009.
[22] Zhao C., Zhang S., Liu Q., Xie J., and Hu J.,
“Independent Tasks Scheduling Based on
Cloud Task Scheduling Based on Ant Colony Optimization 137

Fawzy Torkey received the BSc

degree in industrial electronics in
1974 from the Faculty of Electronic
Engineering, Menoufia University,
Egypt. He received the MSc degree
in electrical engineering and
electronics, in 1980 from the Faculty
of Engineering, Cairo University, Egypt. He received
the PhD degree in computer engineering, Liverpool
University, England, in 1985. He was the Faculty Dean
in the period from 2001 to 2006, Faculty of Computers
and Information, Menoufia University, Egypt. He also
was the president of Kafrelsheikh University, Egypt, in
the period from 2006 to 2011. He is presently a
professor in the Department of Computer Science,
Faculty of Computers and Information, Menoufia
University, Egypt. His research interests include
computer architecture, parallel processing, database and
distributed systems.