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

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.

Échantillon de lecture
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.