ICICES2014 - S.A.

Engineering College, Chennai, Tamil Nadu, India

Various Job Scheduling Algorithms in Cloud

Computing: A Survey
Yash P. Dave,Avani S. Shelat,Dhara S. Patel Rutvij H. Jhaveri
Department of Computer Science and Department of Computer Science and Information
Engineering Technology
Shri Sa’d Vidya Mandal Institute of Technology Shri Sa’d Vidya Mandal Institute of Technology
Bharuch, India. Bharuch, India.
E-mail: [email protected] E-mail: [email protected]

Abstract—Cloud Computing provides a Computing accessed as per the usage. Allocation of resources and proper
environment where different resources, infrastructures, scheduling has a considerable impact on the performance and
development platforms and software are delivered as a service to efficiency of the system. The main goal of cloud computing is
customers virtually on pay per time basis. Low cost, scalability, to provide efficient access to remote and geographically
reliability, utility-based computing are important aspects of cloud
distributed resources.
computing. Job scheduling is an essential and most important
part in any cloud environment. With increasing number of users, An efficient scheduling is a key to manage the access to
Job scheduling becomes a strenuous task. Ordering the jobs by different resources, load balancing as well as resource
scheduler while maintaining the balance between quality of allocation [4]. Different types of resource scheduling
services (QoS), efficiency and fairness of jobs is quite challenging.
Scheduling algorithms are implemented considering parameters
algorithms are available in cloud computing based on certain
such as throughput, resource utilization, latency, cost, priority, parameters like time, cost, performance, priority, utilization of
computational time, physical distances, performance, bandwidth, resources, throughput, bandwidth, resource availability and
resource availability. Though there are different scheduling physical distances.
algorithms available in cloud computing, a very less comparative
study has been done on performance of various scheduling
The paper is organized as follows: In section II, we have
algorithms with respect to above mentioned parameters. This discussed about the theoretical background of cloud
paper aims at a comparative study of various types of job computing. In section III, we have discussed about the
scheduling algorithms that provide efficient cloud services. literature survey we have done related to scheduling
algorithms used in cloud computing.
Keywords—Time Optimized Scheduling Algorithms, Cost
Optimized Scheduling Algorithms, Cloud Computing.
II. Theoretical Background
Resource scheduling and allocation are important features
I. Introduction that affect the performance of cloud computing [5]. Many
researchers have developed various algorithms for scheduling
Cloud computing is a horizon that is emerging out in and scaling of resources in an efficient manner in a cloud.
virtualization, computing and web technologies. Cloud These algorithms are round robin, first come first serve, min-
computing is a distributed computing environment which min, max-min, earliest dead line first, and greedy [6] [7].
includes a large set of virtualized computing resources,
various development platforms, infrastructures and useful Two major types of techniques are used to categorize
software are delivered as a service to customers on a pay as algorithms. They are Time-based optimization techniques and
per use basis usually over the Internet [1]. A major constraint Cost-based optimization techniques. Time-based algorithms
i.e. cutting down the operational expenses can be overcome by concentrate on minimization of execution time, excluding
the use of cloud computing technology. This will help grow other factors like cost as well as QoS levels. Cost-based
business organizations, government organizations as well as optimization techniques concentrate on satisfying QoS user
academic institutions. Cost effectiveness, scalability, level [8] [9].
reliability, fault tolerance, service-orientation, utility based, A. Taxonomy of Cloud Computing
virtualization and service level agreement (SLA) are some of
the salient features of Cloud Computing [2] [3]. Cloud Computing provides various services related to
infrastructure, software, and platform. The three basic models
Cloud provides on demand computational resources in the of Cloud Computing are Infrastructure as a service (Iaas),
form of virtual machines (VMs) deployed in a cloud Platform as a service (Paas), and Software as a service (Saas)
provider’s data center. The computational resources are shared as shown in Fig. 1 Service layers of Cloud Computing [10].
among different cloud consumers who pay for the service

ISBN No.978-1-4799-3834-6/14/$31.00©2014 IEEE

ICICES2014 - S.A.Engineering College, Chennai, Tamil Nadu, India

C. Scheduling in Cloud Computing

The allocation of system resources to various tasks is
known as scheduling. Scheduling is used in cloud computing
1) Infrastructure-as-a-Service (Iaas):Infrastructure-as-a- to achieve high performance and the best system throughput.
Service is the foundation layer of cloud computing. Iaas Speed, efficiency, utilization of resources in an optimized way
delivers hardware as a service. It includes servers, network, depends largely on the type of scheduling selected for the
storage, virtualization technology, file systems, and operating cloud computing environment. Various criteria for scheduling
systems. Iaas cloud providers supply the above mentioned are max CPU utilization, Max throughput, Min turnaround
resources on-demand from their large pools installed in data time, Min waiting time and Min response time. Throughput is
centers [11]. the number of processes that complete their execution per time
unit [13]. Turnaround time is the amount of time to execute a
particular process, which is the interval of time of submission
of a process to the time of completion. Waiting time is the sum
of the periods spent waiting in the ready queue. Response time
is the time from the submission of a request until the first
response is produced [14].
Various issues exist in scheduling algorithms based on
different optimization criteria. Turnaround time and
throughput are the two required criteria in batch systems,
response time and fairness are the two criteria required in
interactive system, whereas in real-time system meeting
deadlines is an important aspect [15]. Therefore a scheduling
algorithm must be selected in such a way that it satisfies the
required criteria and provide efficient service and proper
allocation of resources.

III. Literature Survey

In this section we have presented comprehensive briefing
of various algorithms. Based on the existing Cloud computing
Figure 1. Service layers of Cloud Computing related review, various scheduling algorithms are mentioned.
2) Platform-as-a Service (Paas): PaaS model includes A. Round Robin
development tools, database, webservers, Execution runtime Round Robin (RR) algorithm is one of the algorithms
environment. This model concentrates on providing cost- employed by process and network scheduler in computing.
effective, efficient environment for the development of high- Fairness is primarily focused in Round robin. RR scheduling
quality applications [11]. is simple, easy to implement, and starvation-free. The
3) Software-as-a-Service (SaaS): SaaS also known as “on- scheduler assigns a fixed time unit per process, and cycles
demand-software” is generally priced on a pay-per-use basis. through them.
In Saas model, the application software are installed on the RR uses the ring as its queue to store jobs. Each job has the
cloud by the cloud service providers and accessed by the cloud same execution time and it will be executed in turn. If a job
users from the cloud itself. This eliminates the need of can’t complete its work during its turn, it will be stored back
installing and running the applications on the cloud user’s to the queue waiting for the next turn. Main feature of RR
personal computers [12]. algorithm is execution of each job in turn and it doesn’t have
to wait for the previous one to get completed. But if the load is
B. Types of Cloud Computing found to be heavy, RR will take a long time to complete all the
Cloud computing environment can be categorized into jobs [16]. The CloudSim toolkit supports RR scheduling
private cloud, public cloud and hybrid cloud. A private cloud strategy for internal scheduling of jobs [17].The drawback of
is limited to only an organization managed by the organization RR is that the largest job takes enough time for completion.
itself or any third party cloud service provider. A public cloud
is available on the network and is open publicly. A hybrid B. Earliest Deadline First
cloud is basically the combination of a public cloud and a The basic principle of this algorithm is very intuitive and
private cloud. simple to understand. In this scheduling algorithm, at every
scheduling point the task having the shortest deadline is taken
up for scheduling. Earliest Deadline First (EDF) or Least Time

ISBN No.978-1-4799-3834-6/14/$31.00©2014 IEEE

ICICES2014 - S.A.Engineering College, Chennai, Tamil Nadu, India

to go is a dynamic scheduling algorithm used in real-time resource list is empty and reduces the relative resource list and
operating systems that places processes in a priority queue. reassigns the tasks.
Whenever a scheduling event occurs (end of task, release of
F. Genetic Algorithm
new task.) then the queue will be searched for the process that
is closest to its deadline, the found process will be the next Genetic Algorithm (GA) is a heuristic that mimics the
that is going to be scheduled for execution [18]. process of natural selection. It starts with a set of initial
solution and then with the help of genetic operators, will
C. Deadline Distribution Algorithm generate the new solution [25] [26]. This algorithm handles a
large search space, applicable to the complex objective
The deadline distribution algorithm [19] meets the
function with the help of a local optimum solution, avoiding
deadline for delivering results to minimize the cost. This
the trap. Authors have developed a genetic algorithm, which
algorithm partitions a workflow and distributes the overall
provide a cost based multi QoS scheduling in cloud [27] [28].
deadline into each task based on their workload and
Genetic algorithms belong to the larger class of Evolutionary
dependencies.
Algorithm (EA).
Deadline distribution algorithm uses Synchronization Task G. Modified ant colony optimization scheduling algorithm
Scheduling (STS) for synchronization tasks and Branch Task
Modified ant colony optimization is an approach for
Scheduling (BTS) for branch partition respectively. Each task
diversified service allocation and scheduling mechanism in
has its own sub deadline and a local optimal schedule can be
cloud paradigm. The main aim of this optimization method is
generated for every task. If each local schedule guarantees
to minimize the scheduling throughput to service all the
completion of their task execution within their sub-deadlines,
diversified requests according to the different resource
the whole workflow execution will be completed within the
allocator available under cloud computing environment [29].
overall deadline. Similarly, the result of the cost minimization
solution for each task leads to an optimized cost solution for H. Improved activity based cost based algorithm
the entire workflow [20]. Therefore, an optimized workflow This algorithm is used for efficient scheduling of tasks to
schedule can be constructed from all local optimal schedules. available resources in cloud. In this algorithm the cost and
The schedule allocates every workflow task to a selected computation performance are scheduled. It also improves the
service such that it can meet its assigned sub-deadline at a low computation or communication ratio by grouping the user
execution cost. tasks according to a particular cloud resource’s processing
capability and sends the grouped jobs to the resource [30].
D. Compromised-time-cost scheduling Algorithm
S Pandey et al. presented a compromised-time-cost I. Particle Swarm Optimization algorithm
scheduling algorithm in which they considered cost Particle swarm optimization is used to minimize the total
constrained workflows by compromising execution time and cost of execution of application workflows on Cloud
cost with user input [21]. This algorithm considers the computing environments. It calculates the total cost of
characteristics of cloud computing to accommodate instance- execution by varying the communication cost between
intensive cost-constrained workflows by compromising resources and the execution cost of computing resources [31].
execution time and cost with user input enabled on the fly
J. Market Oriented Hierarchical Scheduling
[22].
Market-oriented hierarchical scheduling strategy consists
E. Back-tracking Algorithm of service-level scheduling and task-level scheduling. Service-
Backtracking algorithm finds solutions to computational level scheduling deals the Task-to-Service assignment and the
problem that incrementally builds candidates to the solutions, task-level scheduling deals with the optimization of the Task-
and abandons each partial candidate c as soon as it to-VM assignment in local cloud data centers. It can be used
determines that c cannot possibly be completed to a valid to optimize the time and cost simultaneously [32].
solution [23]. The back-tracking algorithm [24] assigns
K. Profit-driven Service Request Scheduling
available tasks to the least expensive computing resources.
The unscheduled task’s parent tasks are scheduled. Two sets of profit-driven service request scheduling
algorithms are presented. These algorithms are devised
If more than one task is available, the algorithm assigns incorporating a pricing model using process sharing (PS) and
the task with the largest computational demand to the fastest two allowable delay metrics based on service and application.
resources in its available resource list. This process is repeated Authors have demonstrated the efficiency of consumer
until all tasks have been scheduled. After each step, the applications with interdependent services. The evaluation of
execution time of the current assignment is computed. If the the algorithm was done on the basis of maximum profit and
execution time exceeds the time constraint, the back tracks the utilization [33].
previous step, removes the resource with minimum expense
from its resource list and reassigns tasks with the reduced A comparative study has been done to analyse the working
resource set. Backtracking keeps the previous steps where the of different scheduling algorithms.

ISBN No.978-1-4799-3834-6/14/$31.00©2014 IEEE

ICICES2014 - S.A.Engineering College, Chennai, Tamil Nadu, India

IV. Result And Discussions Thus, based on customers requirement service providers
can use various algorithms for enhancing the efficiency and
The algorithm with the best efficiency for Cloud obtain optimized resource allocation based on certain
environment is determined by various parameters. Cloud parameters.
service providers also offer extra resources to users on demand
with some extra charges. Therefore, Scheduling policies must
work within the deadline and time constraints.
Scheduling algorithms are generally classified as Time TABLE II. FACTOR BASED CLASSIFICATION OF SCHEDULING
based and Cost based. Cost based algorithms include Deadline ALGORITHMS
distribution algorithm, Compromised time-cost algorithm, and
Genetic algorithm. Time based algorithms include Time Cost
Backtracking algorithm, Extended Min-Min algorithm, Round
robin algorithm, and Earliest deadline algorithm. Round Robin Dead line distribution
Cost optimization techniques minimize the cost for
running the applications whereas Time optimization Earliest Dead Line first Compromised time-cost
techniques minimize the completion time for applications.
Cloud service providers use several scheduling algorithms as Back Tracking Genetic algorithm
per the cloud environment to provide efficient services to the
cloud users. Some of the leading cloud providers have been Modified ant colony Improved activity based
mentioned in the TABLE I. along with the algorithms they use optimization cost
for allocation of resources [34] [35].
Extended Min-Min A particle swarm
TABLE I. SCHEDULING ALGORITHMS IN DIFFERENT CLOUD optimization
COMPUTING ENVIRONMENT
Compromised time cost Profit driven service
Cloud Open Scheduling algorithm used oriented algorithm
Provider Source

Eucalyptus Yes Greedy algorithm , First fit Conclusion

algorithm, Round Robin
In cloud computing environment, resources with diverse
algorithm characteristics are served virtually. To manage this type of
Rackspace Yes Round Robin algorithm , heterogeneous resources in optimized way efficient scheduling
Weighted round robin is imperative. Efforts have been put to study various
algorithm, Least connections scheduling algorithms in cloud environment. After a brief
algorithm, weighted least study, various scheduling algorithms have been classified on
connections algorithm the basis of factors such as cost and time and have been
presented in this paper. This comparative study shall be
Open Yes Rank matchmaker scheduling helpful in selection of appropriate scheduling algorithms for
Nebula algorithm, Preemption using different types of services as per the requirements of
scheduling algorithm cloud consumers as well as cloud service providers. This study
may be useful to cloud research enthusiasts for development
Nimbus Yes Virtual machine
of efficient algorithms to enhance the overall efficiency of
schedulers PBS and SGE
cloud computing environments in future.
Amazon No Xen ,swam, Genetic algorithm
References
RedHat Yes Breath first algorithm, Depth
first algorithm [1] 5CGGF 2CTUC CPF 4G\C 'PVG\CTK/CNGMK“RASA: A New Task
Scheduling Algorithm in Grid Environment” .World Applied Sciences
Journal 7 (Special Issue of Computer & IT): 152-160, 2009 ISSN
Lunacloud Yes Round Robin algorithm 1818.4952© IDOSI Publications, 2009J.
[2] Lu Huang, Hai-shan Chen, Ting-ting Hu,”Survey onResource Allocation
Policy and Job Scheduling Algorithms of Cloud Computing”Journal of
Based on the above study few parameters have been software, vol. 8, NO. 2, feb2013.
identified to classify the scheduling algorithms. Some [3] O. M. Elzeki, M. Z. Reshad and M. A. Elsoud, "Improved Max-Min
algorithms can optimize the time span whereas some can Algorithm in Cloud Computing",International Journal of Computer
Applications (0975 – 8887).
minimize the cost as shown in TABLE II.

ISBN No.978-1-4799-3834-6/14/$31.00©2014 IEEE

ICICES2014 - S.A.Engineering College, Chennai, Tamil Nadu, India
[4] Braun, T.D., Siegel, H.J., Beck, N., Boloni, L.L.,Maheswaran, M., [20] Kaur, P.D., Chana, I. ʊUnfolding the distributed computing paradigm
Reuther, A.I., Robertson, J.P., et al. “A comparison of eleven static ,In: International Conference on Advances in Computer Engineering, pp.
heuristics for mapping a class of independent tasks onto heterogeneous 339-342 (2010).
distributed computing systems”, Journal of Parallel and Distributed [21] “Overview of cloud computing and Scheduling policies 2.0”,
Computing, Vol. 61, No. 6, pp.810–837, 2001. http://archives.opennebula.org/documentation:archives:rel2.0:schg.
[5] Greg Boss, Padma Malladi, Dennis Quan, Linda Legregni, Harold Hall. [22] Ke Liu, Jinjun Chen, Hai Jin, Xiao Liu, Dong Yuan, “A Compromised
“Cloud Computing”, High Performance On Demand Time Cost Scheduling Algorithm in SwinDew C for Instance Intensive
Solutions(HiPODS). Cost Constrained Workflows on a Cloud Computing Platform”,July
[6] Chunmei Chi, Feng Gao.” The Trend of Cloud Computing “ in China[J]. 4,2012.
Journal of Software, VOL.6, NO.7, 2011,7:1230~1234. [23] Gilles Brassard, Paul Bratley(1995). Fundamentals of
[7] IsamAzawiMohialdeen. “ Comparitive Study of Scheduling Algorithm Algorithmics.Prentice-Hall.
in cloud computing environment”, in 2013 ISSN 1549-3636. [24] D. A. Menasc and E.Casalicchio, “A Framework for Resource
[8] Rodrigo N. Calheiros1,2, Rajiv Ranjan1, César A. F. De Rose2, and Allocation in Grid Computing”, Proc. of the 12th Annual International
RajkumarBuyya, “CloudSim: A Novel Framework for Modeling and Symposium on Modeling, Analysis, and Simulation of Computer and
Simulation of Cloud Computing Infrastructures and Services”,1Grid Telecommunications Systems, Volendam, The Netherlands, October,
Computing and Distributed Systems (GRIDS) Laboratory Department of 2004,pp 259-267.
Computer Science and Software Engineering The University of [25] Sung Ho Jang, Tae Young Kim, Jae Kwon Kim and Jong Sik Lee“The
Melbourne, Australia, Pontifical Catholic University of Rio Grande do Study of Genetic Algorithm-based Task Scheduling for Cloud
SulPortoAlegre, Brazil. Computing”.International Journal of Control and Automation Vol. 5,
[9] Jagbeer Singh, BichitranandaPatra, Satyendra Prasad Singh, “An No. 4, 2012.
Algorithm to Reduce the Time Complexity of Earliest Deadline First [26] ShaminderKaur ,AmandeepVerma, ”An Efficient Approach to Genetic
Scheduling Algorithm in Real-TimeSystem”,(IJACSA) International Algorithm for Task Scheduling in Cloud Computing Environment” I.J.
Journal of Advanced Computer Science and Applications, Vol. 2, No.2, Information Technology and Computer Science, 2012, 10, 74-79.
February 2011.
[27] J. Yu and R. Buyya, “Scheduling Scientific Workflow Applications
[10] Omar Serfaoui, Mohammed Aissaoui, MohsineEleuldj , “OpenStack: with Deadline and Budget Constraints using Genetic Algorithms”,
Toward an Open-Source Solution forCloud Computing”, International Scientific Programming Journal, 14(3-4), 217-230, IOS Press, 2006.
Journal of Computer Applications (0975 - 8887)Volume 55 - No. 03,
October 2012. [28] D Dutta,R C Joshi ,“A Genetic –Algorithm Approach to Cost-Based
Multi-QoS Job Scheduling in Cloud Computing Environment”,
[11] K. Keahey and T. Freeman, ʊScience Clouds: Early Experiences in International Conference and Workshop on Emerging Trends in
Cloud Computing for Scientific Applications, in proceedings of Cloud Technology (ICWET 2011) – TCET, Mumbai, India,2011.
Computing and Its Applications 2008, Chicago, IL. 2008.
[29] S Banerjee, I Mukherjee, and P.K. Mahanti “Cloud Computing Initiative
[12] B. Furht, and A. Escalante, “Handbook of cloud computing,” Cloud using Modified Ant Colony Framework” , World Academy of Science,
computing fundamentals chapter by B. Furht, Springer, 2010. Engineering and Technology, , 56 2009, pp 221-224.
[13] Salim Bitam,“Bees Life algorithms for job scheduling in cloud [30] Selvarani, S.; Sadhasivam ,G.S.,”Improvedcostbased algorithm for task
computing”, International Conference on computing and Information scheduling in cloud computing”, Computational Intelligence and
Technology, 2012. Computing Research (ICCIC), 2010 IEEE International conference on
[14] He. X, X-He Sun, and Laszewski. G.V, "QoS Guided Min-min 2010 , pp 1–5.
Heuristic for Grid Task Scheduling," Journal ofComputer Science and [31] K. Liu, Y. Yang, J. Chen, X. Liu, D. Yuan , H. Jin, “A Compromised-
Technology, Vol. 18, pp. 442-451, 2003. Time-Cost Scheduling Algorithm in SwinDeW-C for Instance-intensive
[15] Mei, L., Chan, W.K., Tse, T.H., ʊA Tale of Clouds: Paradigm Cost-Constrained Workflows on Cloud Computing Platform”, Int.
Comparisons and Some Thoughts on Research Issues , In: APSCC Journal of High Performance Computing Applications, Volume 24 Issue
2008, pp. 464-469. 4, 2010.
[16] S. Sadhasivam ,N.Nagaveni ,R. Jayarani,and R. Vasanth Ram , “Design [32] Meng Xu, Lizhen Cui, Haiyang Wang, Yanbing Bi, “A Multiple QoS
and Implementation of an efficient Twolevel Scheduler for Cloud Constrained Scheduling Strategy of Multiple Workflows for Cloud
Computing Environment’, International Conference on Advances in Computing”, in 2009 IEEE International Symposium on Parallel and
Recent Technologies in Communication and Computing,2009. Distributed Processing.
[17] Shin-ichiKuribayash, “Optimal Joint Multiple Resource Allocation [33] Young Choon Lee, Chen Wang, Albert Y. Zomaya, Bing
Method for Cloud Computing Environments”, International Journal of BingZhou,”Profit-driven Service Request Scheduling in Clouds”, 10th
Research and Reviews in Computer Science (IJRRCS) Vol. 2, No. 1, IEEE/ACM International Conference on Cluster, Cloud and Grid
March 2011. Computing,2010.
[18] J. Singh, B. Patra, S. P. Singh ,”An Algorithm to Reduce the Time [34] Sonali Yadav, “Comparative Study on Open Source Software for Cloud
Complexity of Earliest Deadline First Scheduling Algorithm in Real- Computing Platform: “ ,International Journal Of Engineering And
Time System”, (IJACSA) International Journal of Advanced Computer Science Vol.3, Issue 10 (October 2013), PP 51-54.
Science and Applications, Vol. 2, No.2, February 2011. [35] Anita S. Pillai , prof. L. S. . Swastimathi, “A Study on open source
[19] J. Yu, R. Buyya and C. K. Tham, “A Cost-based Scheduling of cloud computing platforms “,EXCEL International Journal of
Scientific Workflow Applications on Utility Grids”, Proc. of the 1st Multidisciplinary Management Studies Vol.2 Issue 7, July 2012, ISSN
IEEE International Conference on e-Science and Grid Computing, 2249 8834.
Melbourne, Australia, December 2005 , pp140-147.

ISBN No.978-1-4799-3834-6/14/$31.00©2014 IEEE