Narayanan Certain Investigation on Improved PSO Algorithm for Workflow Scheduling in Cloud Computing Environments

1. Auflage 2018
ISBN: 978-3-96067-692-8
Verlag: Diplomica Verlag
Format: PDF
Kopierschutz: 0 - No protection

E-Book, Englisch, 40 Seiten

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.

Autoren/Hrsg.

Narayanan, Sadhasivam

Fachgebiete

• Mathematik | Informatik EDV | Informatik Computerkommunikation & -vernetzung Cloud-Computing, Grid-Computing

Leseproben

Text Sample:

Chapter 2. Literature Review:

This chapter provides precise elucidation of various works carried out by contemporary researchers on task scheduling problem and various scheduling algorithms for cloud environments based on the metaheuristic techniques. The complexity of the task scheduling problem belongs to NP-complete, involving extremely large search space with a correspondingly large number of potential solutions. In fact, it takes much longer time to find the optimal solution. There is no well-defined methodology to solve the problems under such circumstances.
However in cloud, it is sufficient to find near optimal solution, preferably in a short period of time. In this context IT practioners are focusing on heuristic methods. This chapter focuses on Particle Swarm Optimization (PSO) metaheuristic method of task scheduling used in cloud environment. The objective of the task scheduling problem is to minimize the computation cost.
2.1 Task Scheduling Problem:

Cloud computing is a new paradigm for enterprises that can effectively facilitate the execution of tasks. Task scheduling is an important hurdle which is greatly influencing the performance of cloud computing environment. The cloud service provider and clients have different objectives and requirements. In a dynamic environment resource availability and load on resources keep changing from time to time. Therefore, scheduling resources in clouds is a complicated problem.
Scheduling allows optimal allocation of resources among given tasks in a finite time to achieve the desired quality of service. Formally, scheduling problem involves tasks that must be scheduled on resources subject to some constraints to optimize some objective function. The aim is to build a schedule that specifies when and on which resource each task will be executed (Karger et al. 2010). Task scheduling algorithm is a method by which tasks are matched or allocated to data center resources. Generally no perfect task scheduling algorithm exists. A good scheduler implements a suitable compromise or applies a combination of scheduling algorithms according to different applications. A problem can be solved in seconds, hours or even years depending on the algorithm applied. The efficiency of an algorithm is evaluated by the amount of time necessary to execute it. The execution time of an algorithm is stated as a time complexity function relating to the input.
Task Scheduling in Cloud Computing Environment:

Tsai et al. (2014) implemented Hyper-Heuristic Scheduling Algorithm (HHSA) for providing effective cloud scheduling solutions. The diversity detection and improvement detection operators are utilized in this approach dynamically to determine better low-level heuristic for the effective scheduling. HHSA can reduce the makespan of task scheduling and improves the overall scheduling performance. The drawback is that the approach has high overhead of connection which reduces the importance of scheduling and thus reduces the overall performance.
Zhu et al. (2014) proffered real-time task oriented Energy Aware (EA) scheduling called EARH for the virtualized clouds. The proposed approach is based on Rolling- Horizon (RH) optimization and the procedures are developed for creation, migration, and cancellation of VMs dynamically to adjust the scale of cloud to achieve real time deadlines and reduce energy. The EARH approach has the drawback of the number of cycles assigned to the VMs that cannot be updated dynamically.
Maguluri & Srikant (2014) suggested a scheduling method for job scheduling with unknown duration in the cloud environment. The job sizes are assumed to be unknown not only at arrival, but also at the beginning of service. Hence the throughput-optimal scheduling and load-balancing algorithm for a cloud data center is introduced, when the job sizes are unknown. This algorithm is based on using queue lengths for weights in maxweight schedule instead of the workload.
Zuo et al. (2014) produced a Self-adaptive Learning Particle Swarm Optimization (SLPSO) based scheduling approach for deadline constraint task scheduling in hybrid Infrastructure as a Service (IaaS) clouds. The approach solves the problem of meeting the peak demand for preserving the quality-of-service constraints by using the PSO optimization technique. The approach provides better scheduling of the tasks by maximizing the profit of IaaS provider while guaranteeing QoS. The problem with this approach is the lack of priority determination which results in failure of deadline tasks. Thus scheduling tasks in a cloud computing environment is a challenging process.
Sahni & Vidyarthi (2015) offered a cost-effective deadline constraint dynamic scheduling algorithm for the scientific workflows. The workflow scheduling algorithms in the grid and clusters are efficient but could not be utilized effectively in the cloud environment because of the on demand resource provisioning and pay-as-you-go pricing model. Hence the scheduling using a dynamic cost-effective deadline-constrained heuristic algorithm has been utilized to exploit the features of cloud by considering the virtual machine performance variability and instance acquisition delay to determine the time scheduling. The problem with the approach is that VMs failures may adversely affect the overall workflow execution time.
Zhu et al. (2015) stipulated an agent-based dynamic scheduling algorithm for effective scheduling of tasks in the virtualized clouds. In this approach, a bidirectional announcement-bidding mechanism and the collaborative process are performed to improve the scheduling performance. To further improve the scheduling, elasticity is considered dynamically to add VMs. The calculation rules are generated to improve the bidding process that in turn reduces the delay. The problem with this approach is that it reduces the performance as it does not consider the communication and dispatching times.
Zhang et al. (2015) put forward a fine-grained scheduling approach called Phase and Resource Information-aware Scheduler for MapReduce (PRISM) for scheduling in the MapReduce model. MapReduce has been utilized for its efficiency in reducing the running time of the data-intensive jobs but most of the MapReduce schedulers are designed on the basis of task-level solutions that provide suboptimal job performance. Moreover, the tasklevel schedulers face difficulties in reducing the job execution time. Hence the PRISM was developed which divides tasks into phases. Each phase with a constant resource usage profile performs scheduling at the phase level. Thus the overall job execution time can be reduced significantly but the problem of meeting job deadlines in the phase level scheduling is a serious concern that requires specified attention.
Zhu et al. (2016) advanced an Evolutionary Multi-Objective (EMO) workflow scheduling approach to reduce the workflow scheduling problem such as cost and makespan. Due to the specific properties of the workflow scheduling problem, the existing genetic operations, such as binary encoding, real valued encoding and the corresponding variation operators are based on them in the EMO. The problem is that the approach does not consider monetary costs and time overheads of both communication and storage.