Certain Investigation on Improved PSO Algorithm for Workflow Scheduling in Cloud Computing Environments
©2017
Textbook
40 Pages
Summary
Cloud computing is a new prototype for enterprises which can effectively assist the execution of tasks. Task scheduling is a major constraint which greatly influences the performance of cloud computing environments. The cloud service providers and consumers have different objectives and requirements. For the moment, the load and availability of the resources vary dynamically with time. Therefore, in the cloud environment scheduling resources is a complicated problem. Moreover, task scheduling algorithm is a method by which tasks are allocated or matched to data center resources. All task scheduling problems in a cloud computing environment come under the class of combinatorial optimization problems which decide searching for an optimal solution in a finite set of potential solutions. For a combinatorial optimization problem in bounded time, exact algorithms always guarantee to find an optimal solution for every finite size instance. These kinds of problems are NP-Hard in nature. Moreover, for the large scale applications, an exact algorithm needs unexpected computation time which leads to an increase in computational burden. However, the absolutely perfect scheduling algorithm does not exist, because of conflicting scheduling objectives. Therefore, to overcome this constraint heuristic algorithms are proposed. In workflow scheduling problems, search space grows exponentially with the problem size. Heuristics optimization as a search method is useful in local search to find good solutions quickly in a restricted area. However, the heuristics optimization methods do not provide a suitable solution for the scheduling problem.
Researchers have shown good performance of metaheuristic algorithms in a wide range of complex problems. In order to minimize the defined objective of task resource mapping, improved versions of Particle Swarm Optimization (PSO) are put in place to enhance scheduling performance with less computational burden. In recent years, PSO has been successfully applied to solve different kinds of problems. It is famous for its easy realization and fast convergence, while suffering from the possibility of early convergence to local optimums. In the proposed Improved Particle Swarm Optimization (IPSO) algorithm, whenever early convergence occurs, the original particle swarm would be considered the worst positions an individual particle and worst positions global particle the whole swarm have experienced.
Researchers have shown good performance of metaheuristic algorithms in a wide range of complex problems. In order to minimize the defined objective of task resource mapping, improved versions of Particle Swarm Optimization (PSO) are put in place to enhance scheduling performance with less computational burden. In recent years, PSO has been successfully applied to solve different kinds of problems. It is famous for its easy realization and fast convergence, while suffering from the possibility of early convergence to local optimums. In the proposed Improved Particle Swarm Optimization (IPSO) algorithm, whenever early convergence occurs, the original particle swarm would be considered the worst positions an individual particle and worst positions global particle the whole swarm have experienced.
Excerpt
Table Of Contents
Narayanan, Sadhasivam: Certain Investigation on Improved PSO Algorithm for
Workflow Scheduling in Cloud Computing Environments, Hamburg, Anchor Academic
Publishing 2017
PDF-eBook-ISBN: 978-3-96067-692-8
Druck/Herstellung: Anchor Academic Publishing, Hamburg, 2017
Bibliografische Information der Deutschen Nationalbibliothek:
Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen
Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über
http://dnb.d-nb.de abrufbar.
Bibliographical Information of the German National Library:
The German National Library lists this publication in the German National Bibliography.
Detailed bibliographic data can be found at: http://dnb.d-nb.de
All rights reserved. This publication may not be reproduced, stored in a retrieval system
or transmitted, in any form or by any means, electronic, mechanical, photocopying,
recording or otherwise, without the prior permission of the publishers.
Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung
außerhalb der Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlages
unzulässig und strafbar. Dies gilt insbesondere für Vervielfältigungen, Übersetzungen,
Mikroverfilmungen und die Einspeicherung und Bearbeitung in elektronischen Systemen.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden und die Diplomica Verlag GmbH, die
Autoren oder Übersetzer übernehmen keine juristische Verantwortung oder irgendeine
Haftung für evtl. verbliebene fehlerhafte Angaben und deren Folgen.
Alle Rechte vorbehalten
© Anchor Academic Publishing, Imprint der Diplomica Verlag GmbH
Hermannstal 119k, 22119 Hamburg
http://www.diplomica-verlag.de, Hamburg 2017
Printed in Germany
TABLE OF CONTENTS
Chapter
No.
Topic
Page No.
Abstract
1
1
Introduction
3
1.1 Cloud Computing
3
1.2 Task Scheduling
4
1.3
Task Scheduling Algorithms
6
1.4
Metaheuristic Optimization
7
1.5
Task to Resource Scheduling Paradigm
8
1.6
Problem Formulation
10
1.7
Objective
11
1.8
Scheduling with Metaheuristic
11
1.9
Task to Resource Encoding
13
2
Literature Review
13
2.1
Task Scheduling Problem
13
2.2
Metaheuristic Methods for Task Scheduling
16
3
Improved PSO Algorithm for Workflow Scheduling
in Cloud Computing Environments
19
3.1
Particle Swarm Optimization
21
3.2
Improved Particle Swarm Optimization
23
4
Experimental Results and Analysis
25
5
Conclusion
30
6
References
31
1
CERTAIN INVESTIGATION ON IMPROVED PSO ALGORITHM
FOR WORKFLOW SCHEDULING IN CLOUD COMPUTING
ENVIRONMENTS
Dr. N. SADHASIVAM
Assistant Professor (Senior Grade),
Department of Computer Science and Engineering,
Bannari Amman Institute of Technology, Erode, India
E-mail: sadhasivamn82@gmail.com
ABSTRACT
Recent collaborative scientific experiments in domains such as molecular biology,
neuro-science and high-energy physics have made if necessary to involve the management
of distributed data sources. As a result, an analysis of their datasets is represented and
structured as scientific workflows. In general, these kind of scientific workflows need to
process a large amount of data and computationally intensive activities. To manage these
scientific experiments, a scientific workflow management system is used by hiding the
orchestration and integration details inherent while executing workflows on distributed
resources provided by cloud service providers.
Cloud computing is a new prototype for enterprises that can effectively assist the
execution of tasks. Task scheduling is a major constraint which greatly influences the
performance of cloud computing environment. The cloud service providers and consumers
have different objectives and requirements. For the moment, the load and availability of the
resources vary dynamically with time. Therefore, in the cloud environment scheduling
2
resources is a complicated problem. Moreover, task scheduling algorithm is a method by
which tasks are allocated or matched to data center resources.
All task scheduling problems in cloud computing environment come under the class
of combinatorial optimization problems which decide searching for an optimal solution in
a finite set of potential solutions. For a combinatorial optimization problem in bounded
time exact algorithms always guarantee to find an optimal solution for every finite size
instance. These kinds of problems are NP-Hard in nature. Moreover, for the large scale
applications, exact algorithm needs unexpected computation time which leads to the
increase in computational burden. However, absolutely perfect scheduling algorithm does
not exist, because of conflicting scheduling objectives. Therefore, to overcome this
constraint heuristic algorithms are proposed. In workflow scheduling problems, search
space grows exponentially with the problem size. Heuristics optimization is search
methods useful in local search to find good solutions quickly in a restricted area. The
Heuristics optimization methods do not provide a suitable solution for scheduling
problem.Researchers have shown good performance of metaheuristic algorithms in a wide
range of complex problems.
In order to minimize the defined objective of task resource mapping, improved
versions of Particle Swarm Optimization (PSO) is put in place to enhance scheduling
performance with less computational burden. In the recent years, PSO has been
successfully applied to solve different kinds of problems, ranging from multimodal and
topological mathematical problems to aerospace and chemical engineering. It is famous
for its easy realization and fast convergence, while suffering from the possibility of early
convergence to local optimums. In the proposed Improved Particle Swarm Optimization
(IPSO) algorithm, whenever early convergence occurs, the original particle swarm would
be considered the worst positions an individual particle and worst positions global particle
the whole swarm have experienced.
Keywords: Workflow Scheduling, Cloud Computing Environment, Scheduling
Algorithm, Optimization, Metaheuristic Optimization, PSO, IPSO
3
1.
Introduction
In the modern world, the scientific workflow applications in domains such as
molecular biology, neuro-science and high-energy physics have to involve the
management of distributed data sources. An analysis of the scientific applications
datasets can be represented as a structure of scientific workflows. In general, these kind
of scientific workflows need to process a large amount of data and computationally
intensive activities. Scientific workflow Management Systems are used to o manage these
scientific applications by hiding the inherent orchestration and integration details while
executing workflows on distributed resources provided by cloud service providers (Talia
2013).
1.
1 Cloud Computing
The word "cloud" comes from the terminology of those who built and sold client
server applications, software and hardware used to draw a picture with the Personal
Computer (PC) connected to a network and the network connected to a server.
The cloud
is a metaphor for delivery of hosted services over the internet. Technically, it is a
computing paradigm in which tasks are assigned to a combination of connections,
software and services accessed over a network. The network of servers and connections is
collectively known as the cloud computing. Physically, the resource may sit on a bunch
of servers at different data centres or even span across continents. Cloud computing is a
computing platform that resides in a service provider's large data centre and is capable of
dynamically providing servers the ability to address a wide range of needs of clients.
Computing at the scale of the cloud allows users to access supercomputer-level
power. Instead of operating their own data centres, firms might rent computing power and
storage capacity from a service provider, making them pay only for what they use, as they
do with electricity or water. The paradigm of cloud computing has also been referred to as
"utility computing," in which computing capacity is treated like any other metered utility
service-one pays only for what one uses.
Users can reach into the cloud for resources as they need from anywhere at anytime.
For this reason, cloud computing has also been described as "on-demand computing". It is
provided as a service by another company and accessed over the Internet, usually in a
4
completely seamless way. Exactly where the hardware and software are located and how
they all work do not matter to users. For the user it is just somewhere up in the nebulous
"cloud" that the Internet represents.
Cloud computing was coined for what happens when applications and services are
moved into the internet "cloud." Cloud computing is not something that suddenly
appeared overnight; in some form it may be traced back to a time when computer systems
remotely time-shared computing resources and applications. More currently though, cloud
computing refers to the many different types of services and applications being delivered
in the internet cloud. In many cases, the devices used to access these services and
applications do not require any special applications.
Many companies are delivering services from the cloud. Some notable examples as
of 2016 include the following:
Amazan has a private web services and allows users to upload and access music,
videos, documents, and photos from Web-connected devices. The service also enables
users to stream music to their devices and also provides different services. Google has a
private cloud that it uses for delivering many different services to its users, including
email access, document applications, text translations, maps, web analytics, and much
more.
Microsoft has Microsoft Share point online service that allows content and business
intelligence tools to be moved into the cloud, and Microsoft currently makes its office
applications available in a cloud.
Salesforce.com runs its application set for its customers in a cloud, and its Force.com
and Vmforce.com products provide developers with platforms to build customized cloud
services.
1.2 Task Scheduling
Cloud computing is a nascent prototype for enterprises that can effectively assist
in the execution of tasks. A scheduling algorithm for elastic processes is responsible for
finding a workflow execution plan which makes sure that all workflows are carried out
under the given constraints. These constraints could be defined in a Service Level
Agreement (SLA). Based on this scheduling plan, the reasoner is able to allocate, lease,
5
and release cloud-based computational resources. Scheduling has to be done continuously
for an unknown duration of time, across a system landscape including the business
process landscape as well as cloud resources so that:
All SLAs defined for workflows are met.
x Resources are utilized in an efficient way, i.e. the costs for leasing Virtual
Machines (VMs) over the reckoned time span should be optimized.
x Scheduling and reasoning need to be redone once the system landscape changes,
as new workflow requests arrive or the predicted resource utilization of VMs does
not apply.
x In addition, scheduling and reasoning are done at regular intervals. This interval
can be set by a system administrator.
In order to find a scheduling, one can make use of the following constraints:
x Each backend VMs hosts exactly one service instance, i.e. it is not possible that
different service types are instantiated at the same backend VMs.
x All VMs offer the same capabilities in terms of computational resources and
costs.
Task scheduling is a major concern which greatly influences the performance of
cloud computing environment. The cloud service providers and consumers have different
objectives and requirements. For the moment, the load and availability of the resources
vary dynamically with time. Therefore, in the cloud environment scheduling resources is
a complicated problem. Moreover, task scheduling algorithm is a method by which tasks
are allocated or matched to data center resources. However, absolutely perfect scheduling
algorithms do not exist because of conflicting scheduling objectives (Pandey et al. 2010).
Workflow scheduling is the problem of mapping each task to appropriate resource
and allowing the tasks to satisfy some performance criterion. A workflow consists of a
sequence of concatenated (connected) steps. Workflow mainly focuses on with the
automation of procedures and also in order to achieve the overall goal thereby files and
data are passed between participants according to a defined set of rules. The workflow
enables the structuring of applications in a directed acyclic graph form where each node
6
represents the task and edges represent the dependencies between the nodes of the
applications.
A single workflow consists of a set of tasks and each task communicates with
another task in the workflow. Workflows are supported by Workflow Management
Systems (WMS). Workflow scheduling discovers resources and allocates tasks on
suitable resources. Workflow scheduling plays a vital role in the workflow management.
Proper scheduling of workflow can have an efficient impact on the performance of the
system. However, for proper scheduling of workflows, various scheduling algorithms are
used.
1.3 Task Scheduling Algorithms
A good scheduler applies a combination of scheduling algorithms or implements a
suitable compromise according to the different applications. Depending on the algorithm
applied, a problem can be solved in seconds, hours or even years. Algorithm efficiency is
evaluated by the amount of time necessary to execute it. Task scheduling problem is the
problem of matching tasks to different sets of resources. Scheduling problem can be
classified into two types such as optimization problem and decision problem based on the
objectives (Omara & Afara 2010).
Scheduling problems belong to a broad class of combinational optimization
problem, aimed at finding an optimal matching of tasks to different sets of resources. A
hierarchy of task scheduling algorithms (Pandey et al. 2010) is shown in Figure 1.1. In
order to schedule the tasks efficiently and cost effectively, the schedulers have different
policies that vary according to the objective functions. They minimize the total cost to
execute, the total execution time and balance the load on resources used while meeting the
deadline constraints of the application and so forth.
Details
- Pages
- Type of Edition
- Erstausgabe
- Publication Year
- 2017
- ISBN (PDF)
- 9783960676928
- ISBN (Softcover)
- 9783960671923
- File size
- 730 KB
- Language
- English
- Publication date
- 2017 (September)
- Keywords
- Task scheduling Cloud environment Task scheduling algorithm Heuristics optimization Metaheuristic algorithm Particle Swarm Optimization Improved Particle Swarm Optimization
- Product Safety
- Anchor Academic Publishing
