Task scheduling techniques in cloud computing: A literature survey

doi:10.1016/j.future.2018.09.014

Future Generation Computer Systems

Volume 91, February 2019, Pages 407-415

https://doi.org/10.1016/j.future.2018.09.014 Get rights and content

Highlights

•
Presents a comprehensive survey of task scheduling strategies and the associated metrics suitable for cloud computing environments.
•
Discusses the various issues related to scheduling methodologies and the limitations to overcome.
•
Distinctive scheduling procedures are studied to discover which characteristics are to be included in a given system and which ones to disregard.
•
Literature survey organized based on three different perspectives: methods, applications, and parameter-based measures utilized.
•
Future research issues related to cloud computing-based scheduling identified.

Abstract

Cloud computing manages a variety of virtualized resources, which makes scheduling a critical component. In the cloud, a client may utilize several thousand virtualized assets for every task. Consequently, manual scheduling is not a feasible solution. The basic idea behind task scheduling is to slate tasks to minimize time loss and maximize performance. Several research efforts have examined task scheduling in the past. This paper presents a comprehensive survey of task scheduling strategies and the associated metrics suitable for cloud computing environments. It discusses the various issues related to scheduling methodologies and the limitations to overcome. Distinctive scheduling procedures are studied to discover which characteristics are to be included in a given system and which ones to disregard. The literature survey is organized based on three different perspectives: methods, applications, and parameter-based measures utilized. In addition, future research issues related to cloud computing-based scheduling are identified.

Introduction

The collection of interconnected computers that consists of more than one united computing resource is known as the Cloud. In recent years, the advancement of cloud computing has helped simulate the quick arrangement of inter-connected data centers that are geographically dispersed for offering high quality and dependable services [1]. These days, cloud computing has turned into an efficient paradigm to offer computational abilities on a “pay-per-utilize” premise [2]. Cloud computing brings the conformity and change in the IT business. With its developing application and promotion, cloud computing offers tremendous open doors, as well as confronts many difficulties in the advancement of traditional IT [3]. Recently, cloud computing has risen as another Internet-based model for empowering clients. It can organize access to a shared pool of configurable assets on-request, which can be immediately provided and discharged with very little administration or cloud provider cooperation [4]. Because of this innovation, many advantages such as improved benefits in the market place with respect to time, cost, stack adjusting, and storage can be realized. With this innovation, all applications can keep running on a virtual platform and every one of the resources is distributed among the virtual machines [5]. Every last application is distinctive and independent.

Some of the parallel applications show a decrease in utilization of CPU resources whenever there is an increase in parallelism. If the jobs are not scheduled correctly, performance reduces because the cloud processes a huge amount of data. Thus, the scheduling mechanism plays a vital role in cloud computing. A scheduling algorithm is utilized to plan the task with greatest evaluated gain or benefit and execute the task. However, computing ability in the distributed system shifts from various resources to the cost of resource utilized. The distributed computing administrative tasks such as stockpiling and data transfer processes are easy to manage and bring down expenses. These tasks are scheduled in view of client’s necessity. Additionally, if the number of clients using the cloud increases, scheduling becomes quite difficult and an appropriate scheduling algorithm needs to be utilized. In the early stage, some of the scheduling algorithms were developed in the context of grid computing and based on their performance many were adapted for distributed computing. In cloud computing, users may utilize hundreds or thousands of virtualized resources and it is impossible for everyone to allocate each task manually. Due to commercialization and virtualization, cloud computing handles the task scheduling complexity in the virtual machine layer. Thus, scheduling plays an important role in cloud computing to assign the resources to each task efficiently and effectively. Nowadays, different types of scheduling mechanisms are available such as cloud service scheduling, heuristics scheduling, workflow scheduling, static scheduling and dynamic scheduling. In the cloud, the internal and external requirements of the resources are maintained and the requirements such as bandwidth, storage, resource expenses, and response time may differ for each task. Load balancing, scalability, reliability, performance and dynamic re-allocation of resources to the computing nodes are all the major problems that manifest in task scheduling. Hence, an efficient scheduling algorithm is needed for task scheduling in the cloud computing environment.

In order to develop effective scheduling algorithms, we need to clearly understand the various problems associated with different scheduling methodologies and the limitations to overcome. Thus, the objective of this paper is to present a comprehensive survey of task scheduling strategies and the associated metrics suitable for cloud computing environments. As part of this work, we have studied the different distinctive scheduling procedures to identify which characteristics are to be included in a given system and which ones to disregard. The literature survey is organized based on different perspectives.

The remainder of this article is organized as follows. Section 2 presents a detailed survey of the different scheduling approaches that have been reported in the literature in the last decade. Section 3 organizes the existing task scheduling works based on technique, applications, and parameter-based measures utilized. Section 4 provides conclusion and future work.

Section snippets

Survey of scheduling in cloud computing

All articles that had the word “scheduling” in the title or keyword, published from January 2005 to March 2018, were first selected from scientific journals including IEEE, Elsevier, Springer and other international journals. A huge number of studies have been devoted to machine learning and other techniques to work through problems in cloud computing. This section surveys and categorizes the various task scheduling techniques. They can be subdivided into ten broad categories: QoS-based task

Categorization and discussion

In this section, we categorize all the articles considered in the survey, based on three different criteria: technique, application, and parameter-based measures. Each category is briefly described in the following sub-sections.

Conclusion and future research

Cloud computing is user-oriented technology wherein users get to choose from hundreds of thousands of virtualized resources for each task. Here, scheduling is considered a major factor for task execution in the cloud environment. In this survey article, we have analyzed various scheduling algorithms and tabulated different parameters used under the cloud and grid environments. In all, 65 articles associated with scheduling, from 2003 to 2018, have been examined. The articles are categorized,

Acknowledgment

The research work by Vijayan Sugumaran has been supported by the 2018 School of Business Administration Spring/Summer Research Fellowship from Oakland University, United States .

AR. Arunarani is currently a Teaching Fellow at the Faculty of Computer Science and Engineering, CEG Campus, Anna University, Chennai, India. She received her Ph.D. from the Faculty of Information and Communication Engineering in 2018, M.E. degree from the Department of Computer Science and Engineering in 2011, and B.Tech. degree from the Department of Information Technology in 2008, all at the CEG campus, Anna University, Chennai. Her specializations include Networking, Data Mining, Big data

References (74)

KeshanchiB. et al.
An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: formal verification, simulation, and statistical testing
J. Syst. Softw.
(2017)
WuX. et al.
A task scheduling algorithm based on Qos -driven in cloud computing
Proc. Comput. Sci.
(2013)
AlbodourR. et al.
QoS within business grid quality of service (BGQoS)
Future Gener. Comput. Syst.
(2015)
HayyolalamV. et al.
A systematic literature review on QoS-aware service composition and selection in cloud environment
J. Netw. Comput. Appl.
(2018)
GaoJ. et al.
A hybrid of genetic algorithm and bottleneck shifting for multi-objective flexible job shop scheduling problems
Comput. Ind. Eng..
(2007)
DasguptaK. et al.
A genetic algorithm (GA) based load balancing strategy for cloud computing
Proc. Tech.
(2013)
XuY. et al.
A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues
Inf. Sci.
(2014)
KeshanchiB. et al.
An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: Formal verification. Simulation, and statistical testing
J. Syst. Softw.
(2017)
KwokY.K. et al.
On multiprocessor task scheduling using efficient state space search approaches
J. Parallel Distrib. Comput.
(2005)
FahmyM.M.
A fuzzy algorithm for scheduling non-periodic jobs on soft real-time single processor system
Ain Shams Eng. J.
(2010)

SuerG.A. et al.

Evaluation of feedback among multiple scheduler profiles in fuzzy genetic scheduling

Procedia Comput. Sci.

(2012)

QinX. et al.

A dynamic and reliability-driven scheduling algorithm for parallel real-time jobs executing on heterogeneous clusters

J. Parallel Distrib. Comput.

(2005)

PapazachosZ.C. et al.

The impact of task service time variability on gang scheduling performance in a two-cluster system

Simul. Modelling Practice Theory

(2009)

AbrahamG.T. et al.

Group-based parallel multi-scheduler for grid computing

Future Gener. Comput. Syst.

(2015)

YokoyamaD. et al.

Affinity aware scheduling model of cluster nodes in private clouds

J. Netw. Comput. Appl.

(2017)

AbrishamiS. et al.

Deadline-constrained workflow scheduling in software as a service Cloud

Sci. Iranica

(2012)

AbrishamiS. et al.

Deadline-constrained workflow scheduling algorithms for Infrastructure as a Service Clouds

Future Gener. Comput. Syst.

(2013)

SuS. et al.

Cost-efficient task scheduling for executing large programs in the cloud

Parallel Comput.

(2013)

SonJ.H. et al.

Extracting the workflow critical path from the extended well-formed workflow schema

J. Comput. System Sci.

(2005)

SenkulP. et al.

An architecture for workflow scheduling under resource allocation constraints

Inf. Syst.

(2005)

WangW. et al.

Cloud-DLS: dynamic trusted scheduling for cloud computing

Expert Syst. Appl.

(2012)

LeeS. et al.

Efficient scheduling algorithm for component-based networks

Future Gener. Comput. Syst.

(2007)

KaiyueW. et al.

Distributed online scheduling and routing of multicast-oriented tasks for fitness function-driven cloud computing

IEEE Commun. Lett.

(2016)

ZhuX. et al.

ANGEL: Agent-based scheduling for real-time tasks in virtualized clouds

IEEE Trans. Comput.

(2015)

ChengC. et al.

An energy-saving task scheduling strategy based on vacation queuing theory in cloud computing

Tsinghua Sci. Technol.

(2015)

LovászG. et al.

Performance tradeoffs of energy-aware virtual machine consolidation

Cluster Comput.

(2013)

HeX. et al.

QoS guided Min-Min heuristic for grid task scheduling

J. Comput. Sci. Technol.

(2003)

PatelS. et al.

QoS based user driven scheduler for grid environment

Adv. Comput.: Int. J. (ACIJ)

(2011)

LiB. et al.

A distributed QoS-constraint task scheduling scheme in cloud computing environment: Model and algorithm

Adv. Inf. Sci. Serv. Sci.

(2012)

DubeyS. et al.

QoS driven task scheduling in cloud computing

Int. J. Comput. Appl. Technol. Res.

(2013)

AliH.E.D. et al.

Grouped tasks scheduling algorithm based on QoS in cloud computing network

Egyptian Inform. J.

(2017)

FarukM.N. et al.

Multi-layer QOS based task scheduling algorithm for cloud environments

Int. J. Adv. Comput. Technol.

(2014)

MathiyalaganP. et al.

Grid scheduling using enhanced ant colony algorithm

ICTACT J. Soft Comput.

(2010)

MathiyalaganP. et al.

Modified ant colony algorithm for grid scheduling

Int. J. Comput. Sci. Eng.

(2010)

MaruthanayagamD. et al.

Enhanced ant colony system based on RASA algorithm in grid scheduling

Int. J. Comput. Sci. Inf. Technol.

(2011)

DelavarA.G. et al.

Task scheduling in grid environment with ant colony method for cost and time

Int. J. Comput. Sci. Eng. Appl.

(2012)

SrikanthU. et al.

Tasks scheduling using Ant Colony Optimization

J. Comput. Sci.

(2012)

Cited by (339)

Joint optimization of multi-dimensional resource allocation and task offloading for QoE enhancement in Cloud-Edge-End collaboration
2024, Future Generation Computer Systems
Cloud-Edge-End Collaboration (CEEC) computing architecture inherits many merits from both edge computing and cloud computing and thus is considered as a promising candidate for future network services. In CEEC, user’s QoE is impacted by offload performance which should consider offload strategy, computational resources and network status simultaneously. However, previous offload optimization studies neglect the joint consideration of dependent task offloading, computational resources and channel resources, which may not produce potential performance improvement. In this paper, we investigate the joint optimization of dependent task offloading, computational resource allocation, user transmission power control, and channel resource allocation in the CEEC scenario, with the goal of maximizing user’s QoE. Initially, a new QoE metric is defined to capture the impacts of delay and energy consumption on user’s QoE. Following this definition, we formulate the joint optimization problem as a Mixed Integer Nonlinear Programming (MINLP) problem and introduce a method of multi-agent deep reinforcement learning to solve our MINLP problem with high computation complexity. Extensive experiments are performed, and experimental results show that our proposed scheme outperforms baselines in a series of metrics.
Detection of quality of service degradation on multi-tenant containerized services
2024, Journal of Network and Computer Applications
Computational services are progressively migrating to container-based solutions due to their faster provision time and lower resource allocation overhead. Service providers rely on container multi-tenancy to share their computing infrastructure and pave their way to profit. Yet, the Quality of Service (QoS) impact due to container multi-tenancy on deployed services is still widely overlooked in the literature. This paper proposes a new service provider monitoring model for detecting container multi-tenancy that can lead to QoS degradation, split into two phases. First, we monitor the container resource usage through the container engine and the associated process namespace, thus, keeping container isolation. The main assumption is that the assessment of resource utilization, as measured by the container engine, should be complemented by the concurrent reporting of resource utilization from the container processes. Second, we detect QoS degradation of distributed containerized services through a time-series classification approach coped with a feature reduction technique. The feature reduction selects the prominent performance features from the deployed distributed service, whereas the time-series classifier ensures the evaluation of the deployed service over time, improving the system detection accuracy. Thanks to an extensive experimental assessment considering a containerized distributed Big Data processing platform, we show that container multi-tenancy can affect the processing performance and the QoS of deployed services. In addition, we show that the proposed model can detect QoS degradation at the service provider domain with a true-positive rate up to 90%, a false-positive rate of 8%, and an average F1-Score up to 0.94.
METSM: Multiobjective energy-efficient task scheduling model for an edge heterogeneous multiprocessor system
2024, Future Generation Computer Systems
Along with the growth of computing requirements, edge devices, such as satellites and unmanned aerial vehicles, are equipped with heterogeneous multiprocessor systems to cope with complicated missions, including attitude control, signal processing, and objective detection. Concerning the extremely limited power on these devices, reducing the energy and time overhead of task execution evolves into a crucial challenge. Therefore, a multiobjective energy-efficient task scheduling technique (METSM) is proposed. First, a mathematical model is established for the energy-efficient task scheduling problem on edge heterogeneous multiprocessor systems. In this model, both makespan and total energy consumption are the optimization objectives. The decision variables include the task execution sequence, processor assignment, and dynamic voltage and frequency scaling level for each processor. Second, a problem-specific algorithm, namely, iterated greedy-based multiobjective optimizer (IMO), is proposed. Specifically, destruction–reconstruction and local search are redesigned for optimizing task scheduling and resource allocation. Considering local optima avoidance, a probabilistic mutation operation is developed. In addition, multiobjective-oriented strategies of optimal solution selection and acceptance criteria are adopted to accelerate the convergence. Finally, our proposed IMO is compared with several of the latest algorithms through multiple performance metrics. The experimental results show that IMO can obtain optimal Pareto fronts among several multiobjective methods. Savings of approximately 10% and 12% in time and power consumption, respectively, can be achieved by IMO. Moreover, in comparison with classic list-based heuristics for solving test cases, while IMO maintains a similar makespan, energy is reduced by nearly 90%.
Variable Neighborhood Search for precedence-constrained tasks optimization on heterogeneous systems
2024, Expert Systems with Applications
Supercomputing power is one of the fundamental pillars of the digital society, which depends on the accurate scheduling of parallel applications in High-Performance Computing (HPC) centers to minimize computing times. However, precedence-constraint task scheduling is a well-known NP-Hard optimization problem, and no optimal polynomial-time algorithm exists to solve it. Therefore, as accurate as possible to the optimal values, heuristic algorithms are of relevant interest. Our new scheduling proposal name is EFT-GVNS, which stands for Earliest Finish Time - General Variable Neighborhood Search. EFT-GVNS uses a Composite Local Search (CLS), making our proposal more efficient than traditional GVNS. EFT-GVNS accuracy against four high-performance algorithms from the state-of-the-art (EDA, EFT-ILS, GRASP-CPA, MPQGA) and one reference algorithm in the literature (HEFT) is studied. Experimental results over four real-world applications (Fpppp, LIGO, Robot, Sparse) and 14 synthetic instances from the literature show that EFT-GVNS outperforms in terms of the median achieved results, with a global improvement of 37.6%, 27.4%, 17.8%, 6.1%, 2.2% to HEFT, EDA, EFT-ILS, GRASP-CPA, and MPQGA, respectively. EFT-GVNS achieves all the 14 optimal values of the synthetic benchmark.
Energy efficient task scheduling based on deep reinforcement learning in cloud environment: A specialized review
2024, Future Generation Computer Systems
The expanding scale of cloud data centers and the diversification of user services have led to an increase in energy consumption and greenhouse gas emissions, resulting in long-term detrimental effects on the environment. To address this issue, scheduling techniques that reduce energy usage have become a hot topic in cloud computing and cluster management. The Deep Reinforcement Learning (DRL) approach, which combines the advantages of Deep Learning and Reinforcement Learning, has shown promise in resolving scheduling problems in cloud computing. However, reviews of the literature on task scheduling that employ DRL techniques for reducing energy consumption are limited. In this paper, we survey and analyze energy consumption models used for scheduling goals, provide an overview of the DRL algorithms used in the literature, and quantitatively compare the model differences of Markov Decision Process elements. We also summarize the experimental platforms, datasets, and neural network structures used in the DRL algorithm. Finally, we analyze the research gap in DRL-based task scheduling and discuss existing challenges as well as future directions from various aspects. This paper contributes to the correlation perspective on the task scheduling problem with the DRL approach and provides a reference for in-depth research on the direction of DRL-based task scheduling research. Our findings suggest that DRL-based scheduling techniques can significantly reduce energy consumption in cloud data centers, making them a promising area for further investigation.
A survey on energy-efficient workflow scheduling algorithms in cloud computing
2024, Software - Practice and Experience

View all citing articles on Scopus

Dr. D. Manjula is the Professor and Head of the Computer Science and Engineering Department, CEG Campus, Anna University, Chennai, India. She received her B.E. degree in Electronics and Communication Engineering from Thiagarajar College of Engineering, Madurai in 1983 and her M.E. degree in Computer Science and Engineering degree from Anna University, Chennai in 1987. She obtained Ph.D. degree in Information and Communication Engineering from Anna University in 2004. She has nearly 35 years of teaching experience in CEG campus, Anna University, Chennai, one of the top most State Government University in India since 1987. Her research interests spans over Cloud Computing, Social Network Analysis, Information Retrieval, Language Technologies, Data and Text Mining, Machine Learning, Imaging and Networks. Under her guidance, 11 Ph.D. Scholars are awarded and 9 Ph.D. scholars are doing their research in her areas of expertise. She has guided more than 50 post graduate students to complete their projects in her research fields. She has published over 130 technical national and international Journal as well as Conference papers. She has authored three books published by well-known publisher, Pearson Education Inc. She is the Convenor of CoMSE 2015 and DaSAA 2016. She is the life time member of ISTE. She has delivered many tutorials and Invited talks at different Universities and Institutions across India. She is currently coordinating Big Data Analytics Project under UGC-DSA Phase II. She has successfully completed the Database and Web Technology Project under the UGC-DSA Phase I. She has also coordinated three research projects funded by Tamil Virtual University of Tamil Nadu Government with a passion to render Tamil language in Mobile phones. She was actively involved in a project named RCILTS funded by Ministry of Information Technology, intended to provide knowledge tools in Indian languages (Tamil Language). Apart from the academic responsibilities, she was one of the Deputy Directors in the Centre for Distance Education. She has served as a Director, Planning & Development of Anna University which is directly related to the planning & development of every sector in the University. Moreover, she was the ex-officio member of all the executive committees constituted by the Vice-Chancellor. She has also acted as the Director, Centre for Faculty Development, Anna University. Through the Centre for faculty development, she has conducted numerous faculty development training programs.

Vijayan Sugumaran is Professor of Management Information Systems and Chair of the Department of Decision and Information Sciences at Oakland University, Rochester, Michigan, USA. He received his Ph.D. in Information Technology from George Mason University, Fairfax, Virginia, USA. He is also the Co-Director of the Center for Data Science and Big Data Analytics at Oakland University. His research interests are in the areas of Big Data Management and Analytics, Ontologies and Semantic Web, Intelligent Agent and Multi-Agent Systems. He has published over 200 peer-reviewed articles in Journals, Conferences, and Books. He has edited twelve books and serves on the Editorial Board of eight journals. He has published in top-tier journals such as Information Systems Research, ACM Transactions on Database Systems, Communications of the ACM, IEEE Transactions on Big Data, IEEE Transactions on Engineering Management, IEEE Transactions on Education, and IEEE Software. Dr. Sugumaran is the editor-in-chief of the International Journal of Intelligent Information Technologies. He is the Chair of the Intelligent Agent and Multi-Agent Systems mini-track for Americas Conference on Information Systems (AMCIS 1999–2019). Dr. Sugumaran has served as the program co-chair for the 14th Workshop on E-Business (WeB2015), the International Conference on Applications of Natural Language to Information Systems (NLDB 2008, NLDB 2013 and NLDB 2016) and 29th Australasian Conference on Information Systems (ACIS 2018). He also regularly serves as a program committee member for numerous national and international conferences.

View full text

Task scheduling techniques in cloud computing: A literature survey

Highlights

Abstract

Introduction

Section snippets

Survey of scheduling in cloud computing

Categorization and discussion

Conclusion and future research

Acknowledgment

J. Syst. Softw.

Proc. Comput. Sci.

Future Gener. Comput. Syst.

J. Netw. Comput. Appl.

Comput. Ind. Eng..

Proc. Tech.

Inf. Sci.

J. Syst. Softw.

J. Parallel Distrib. Comput.

Ain Shams Eng. J.

Procedia Comput. Sci.

J. Parallel Distrib. Comput.

Simul. Modelling Practice Theory

Future Gener. Comput. Syst.

J. Netw. Comput. Appl.

Sci. Iranica

Future Gener. Comput. Syst.

Parallel Comput.

J. Comput. System Sci.

Inf. Syst.

Expert Syst. Appl.

Future Gener. Comput. Syst.

Distributed online scheduling and routing of multicast-oriented tasks for fitness function-driven cloud computing

IEEE Commun. Lett.

ANGEL: Agent-based scheduling for real-time tasks in virtualized clouds

IEEE Trans. Comput.

An energy-saving task scheduling strategy based on vacation queuing theory in cloud computing

Tsinghua Sci. Technol.

Performance tradeoffs of energy-aware virtual machine consolidation

Cluster Comput.

QoS guided Min-Min heuristic for grid task scheduling

J. Comput. Sci. Technol.

QoS based user driven scheduler for grid environment

Adv. Comput.: Int. J. (ACIJ)

A distributed QoS-constraint task scheduling scheme in cloud computing environment: Model and algorithm

Adv. Inf. Sci. Serv. Sci.

QoS driven task scheduling in cloud computing

Int. J. Comput. Appl. Technol. Res.

Grouped tasks scheduling algorithm based on QoS in cloud computing network

Egyptian Inform. J.

Multi-layer QOS based task scheduling algorithm for cloud environments

Int. J. Adv. Comput. Technol.

Grid scheduling using enhanced ant colony algorithm

ICTACT J. Soft Comput.

Modified ant colony algorithm for grid scheduling

Int. J. Comput. Sci. Eng.

Enhanced ant colony system based on RASA algorithm in grid scheduling

Int. J. Comput. Sci. Inf. Technol.

Task scheduling in grid environment with ant colony method for cost and time

Int. J. Comput. Sci. Eng. Appl.

Tasks scheduling using Ant Colony Optimization

J. Comput. Sci.