Current Perspective in Task Scheduling Techniques in Cloud Computing: A Review
---
paper_title: A Particle Swarm Optimization-Based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments

paper_content:

Cloud computing environments facilitate applications by providing virtualized resources that can be provisioned dynamically. However, users are charged on a pay-per-use basis. User applications may incur large data retrieval and execution costs when they are scheduled taking into account only the ‘execution time’. In addition to optimizing execution time, the cost arising from data transfers between resources as well as execution costs must also be taken into account. In this paper, we present a particle swarm optimization (PSO) based heuristic to schedule applications to cloud resources that takes into account both computation cost and data transmission cost. We experiment with a workflow application by varying its computation and communication costs. We compare the cost savings when using PSO and existing ‘Best Resource Selection’ (BRS) algorithm. Our results show that PSO can achieve: a) as much as 3 times cost savings as compared to BRS, and b) good distribution of workload onto resources.
---
paper_title: Cost-Aware Scheduling Algorithm Based on PSO in Cloud Computing Environment

paper_content:

Traditional scheduling algorithms typically aim to minimize the total time cost for processing all tasks. However, in cloud computing environments, computing capability differs for different resources, and so does the cost of resource usage. Therefore, it is vital to take into consideration the usage cost of resources. Along this line, in this paper, we proposed a modified algorithm based on PSO to solve the task scheduling problem in cloud computing environments. Specifically, by adding a cost-aware fitness function to quantify the cost of resource usage, along with the fitness function for time cost, our method can achieve the goal of minimizing both the processing time and resource usage, and therefore reach a global optimal solution. Besides, our experiment on a simulated cloud computing environment proves the efficiency of our proposed algorithm.
---
paper_title: A modified particle swarm optimizer

paper_content:

Evolutionary computation techniques, genetic algorithms, evolutionary strategies and genetic programming are motivated by the evolution of nature. A population of individuals, which encode the problem solutions are manipulated according to the rule of survival of the fittest through "genetic" operations, such as mutation, crossover and reproduction. A best solution is evolved through the generations. In contrast to evolutionary computation techniques, Eberhart and Kennedy developed a different algorithm through simulating social behavior (R.C. Eberhart et al., 1996; R.C. Eberhart and J. Kennedy, 1996; J. Kennedy and R.C. Eberhart, 1995; J. Kennedy, 1997). As in other algorithms, a population of individuals exists. This algorithm is called particle swarm optimization (PSO) since it resembles a school of flying birds. In a particle swarm optimizer, instead of using genetic operators, these individuals are "evolved" by cooperation and competition among the individuals themselves through generations. Each particle adjusts its flying according to its own flying experience and its companions' flying experience. We introduce a new parameter, called inertia weight, into the original particle swarm optimizer. Simulations have been done to illustrate the significant and effective impact of this new parameter on the particle swarm optimizer.
---
paper_title: Enhanced Particle Swarm Optimization for Task Scheduling in Cloud Computing Environments

paper_content:

Abstract The most important requirement in cloud computing environment is the task scheduling which plays the key role of efficiency of the whole cloud computing facilities. Task scheduling in cloud computing means that to allocate best suitable resources for the task to be execute with the consideration of different parameters like time, cost, scalability, make span, reliability, availability, throughput, resource utilization and so on. The proposed algorithm considers reliability and availability. Most scheduling algorithms do not consider reliability and availability of the cloud computing environment because the complexity to achieve these parameters. We propose mathematical model using Load Balancing Mutation (balancing) a particle swarm optimization (LBMPSO) based schedule and allocation for cloud computing that takes into account reliability, execution time, transmission time, make span, round trip time, transmission cost and load balancing between tasks and virtual machine .LBMPSO can play a role in achieving reliability of cloud computing environment by considering the resources available and reschedule task that failure to allocate. Our approach LBMPSO compared with standard PSO, random algorithm and Longest Cloudlet to Fastest Processor (LCFP) algorithm to show that LBMPSO can save in make span, execution time, round trip time, transmission cost.
---
paper_title: Multi Objective Task Scheduling in Cloud Environment Using Nested PSO Framework

paper_content:

Abstract Cloud computing is an emerging computing paradigm with a large collection of heterogeneous autonomous systems with flexible computational architecture. Task scheduling is an important step to improve the overall performance of the cloud computing. Task scheduling is also essential to reduce power consumption and improve the profit of service providers by reducing processing time. This paper focuses on task scheduling using a multi-objective nested Particle Swarm Optimization(TSPSO) to optimize energy and processing time. The result obtained by TSPSO was simulated by an open source cloud platform (CloudSim). Finally, the results were compared to existing scheduling algorithms and found that the proposed algorithm (TSPSO) provide an optimal balance results for multiple objectives.
---
paper_title: A Chaotic Particle Swarm Optimization-Based Heuristic for Market-Oriented Task-Level Scheduling in Cloud Workflow Systems

paper_content:

Cloud workflow system is a kind of platform service based on cloud computing. It facilitates the automation of workflow applications. Between cloud workflow system and its counterparts, market-oriented business model is one of the most prominent factors. The optimization of task-level scheduling in cloud workflow system is a hot topic. As the scheduling is a NP problem, Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO) have been proposed to optimize the cost. However, they have the characteristic of premature convergence in optimization process and therefore cannot effectively reduce the cost. To solve these problems, Chaotic Particle Swarm Optimization (CPSO) algorithm with chaotic sequence and adaptive inertia weight factor is applied to present the task-level scheduling. Chaotic sequence with high randomness improves the diversity of solutions, and its regularity assures a good global convergence. Adaptive inertia weight factor depends on the estimate value of cost. It makes the scheduling avoid premature convergence by properly balancing between global and local exploration. The experimental simulation shows that the cost obtained by our scheduling is always lower than the other two representative counterparts.
---
paper_title: Reliability-driven scheduling of time/cost-constrained grid workflows

paper_content:

Abstract Workflow scheduling in Grids and Clouds is a NP-Hard problem. Constrained workflow scheduling, arisen in recent years, provides the description of the user requirements through defining constraints on factors like makespan and cost. This paper proposes a scheduling algorithm to maximize the workflow execution reliability while respecting the user-defined deadline and budget. We have used ant colony system to minimize an aggregation of reliability and constraints violation. Three novel heuristics have been proposed which are adaptively selected by ants. Two of them are employed to find feasible schedules and the other is used to enhance the reliability. Two methods have been investigated for time and cost considerations in the resource selection. One of them assigns equal importance to the time and cost factors, and the other weighs them according to the tightness of satisfaction of the corresponding constraints. Simulation results demonstrate the effectiveness of the proposed algorithm in finding feasible schedules with high reliability. As it is shown, as an additional achievement, the Grid profit loss has been decreased.
---
paper_title: An ACO-LB Algorithm for Task Scheduling in the Cloud Environment

paper_content:

In the face of a large number of task requests which are submitted by users, the cloud data centers need not only to finish these massive tasks but also to satisfy the user's service demand. How to allocate virtual machine reasonably and schedule the tasks efficiently becomes a key problem to be solved in the cloud environment. This paper proposes a ACO-LB(Load balancing optimization algorithm based on ant colony algorithm) algorithm to solve the load imbalance of virtual machine in the process of task scheduling .The ACO-LB algorithm can adapt to the dynamic cloud environment. It will not only shorten the makespan of task scheduling, but also maintain the load balance of virtual machines in the data center. In this paper, the workflow scheduling is simulated in CloudSim. The results show that the proposed ACO-LB algorithm has better performance and load balancing ability.
---
paper_title: Cloud task scheduling based on ant colony optimization

paper_content:

Cloud computing is the development of distributed computing, parallel computing and grid computing, or defined as the commercial implementation of these computer science concepts. One of the fundamental issues in this environment is related to task scheduling. Cloud task scheduling is an NP-hard optimization problem, and many meta-heuristic algorithms have been proposed to solve it. A good task scheduler should adapt its scheduling strategy to the changing environment and the types of tasks. In this paper a cloud task scheduling policy based on ant colony optimization algorithm compared with different scheduling algorithms FCFS and round-robin, has been presented. The main goal of these algorithms is minimizing the makespan of a given tasks set. Ant colony optimization is random optimization search approach that will be used for allocating the incoming jobs to the virtual machines. Algorithms have been simulated using Cloudsim toolkit package. Experimental results showed that the ant colony optimization outperformed FCFS and round-robin algorithms.
---
paper_title: Improving Task Scheduling in Large Scale Cloud Computing Environment using Artificial Bee Colony Algorithm

paper_content:

In the face of Scheduling, the tasks are scheduled by using Different scheduling Algorithms. Each Scheduling Algorithm has own particularity and complexity during Scheduling. In order to get the minimum time for the execution of the task the Scheduling algorithm must be good, once the performance of the scheduling algorithm is good then automatically the result obtained by that particular algorithm will be considered , there are huge number of task that are scheduled under cloud computing in order to get the minimum time and the maximum through put the Scheduling algorithm plays an important factor Here the algorithm which used for Scheduling the task is artificial bee colony algorithm this scheduling process is done under the cloud computing environment. In this Paper we are considering the time as the main QoS factor, minimum total task finishing time, mean task finishing time and load balancing time is obtained by using this Cloud simulation environment
---
paper_title: A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion

paper_content:

A heuristic is proposed for initializing ABC population.An ensemble local search method is proposed to improve the convergence of TABC.Three re-scheduling strategies are proposed and evaluated.TABC is tested using benchmark instances and real cases from re-manufacturing.TABC compared against several state-of-the-art algorithms. This study addresses the scheduling problem in remanufacturing engineering. The purpose of this paper is to model effectively to solve remanufacturing scheduling problem. The problem is modeled as flexible job-shop scheduling problem (FJSP) and is divided into two stages: scheduling and re-scheduling when new job arrives. The uncertainty in timing of returns in remanufacturing is modeled as new job inserting constraint in FJSP. A two-stage artificial bee colony (TABC) algorithm is proposed for scheduling and re-scheduling with new job(s) inserting. The objective is to minimize makespan (maximum complete time). A new rule is proposed to initialize bee colony population. An ensemble local search is proposed to improve algorithm performance. Three re-scheduling strategies are proposed and compared. Extensive computational experiments are carried out using fifteen well-known benchmark instances with eight instances from remanufacturing. For scheduling performance, TABC is compared to five existing algorithms. For re-scheduling performance, TABC is compared to six simple heuristics and proposed hybrid heuristics. The results and comparisons show that TABC is effective in both scheduling stage and rescheduling stage.
---
paper_title: Solving the large-scale hybrid flow shop scheduling problem with limited buffers by a hybrid artificial bee colony algorithm

paper_content:

This paper presents a novel hybrid algorithm (TABC) that combines the artificial bee colony (ABC) and tabu search (TS) to solve the hybrid flow shop (HFS) scheduling problem with limited buffers. The objective is to minimize the maximum completion time. Unlike the original ABC algorithm, in TABC, each food source is represented by a string of job numbers. A novel decoding method is embedded to tackle the limited buffer constraints in the schedules generated. Four neighborhood structures are embedded to balance the exploitation and exploration abilities of the algorithm. A TS-based self-adaptive neighborhood strategy is adopted to impart to the TABC algorithm a learning ability for producing neighboring solutions in different promising regions. Furthermore, a well-designed TS-based local search is developed to enhance the search ability of the employed bees and onlookers. Moreover, the effect of parameter setting is investigated by using the Taguchi method of design of experiment (DOE) to determine the suitable values for key parameters. The proposed TABC algorithm is tested on sets of instances with large scales that are generated based on realistic production. Through a detailed analysis of the experimental results, the highly effective and efficient performance of the proposed TABC algorithm is contrasted with the performance of several algorithms reported in the literature.
---
paper_title: Task scheduling in the Cloud Environments based on an Artificial Bee Colony Algorithm

paper_content:

Nowadays, Cloud computing has gained vast attention due to its technological advancement, cost reduction and availability. In the Cloud environments, the suitable scheduling of the received tasks over service provides has become an important and vital problem. The scheduling problem in Cloud environments is an NP- hard problem. Therefore, many heuristics have been proposed to solve this problem up to now. In this paper, we propose a new bee colony algorithm to schedule the tasks on service providers in the Cloud environments. The results demonstrated that the proposed algorithm has a better operation in terms of task execution time, waiting time and missed tasks.
---
paper_title: Chaotic bat algorithm

paper_content:

Abstract Bat algorithm (BA) is a recent metaheuristic optimization algorithm proposed by Yang. In the present study, we have introduced chaos into BA so as to increase its global search mobility for robust global optimization. Detailed studies have been carried out on benchmark problems with different chaotic maps. Here, four different variants of chaotic BA are introduced and thirteen different chaotic maps are utilized for validating each of these four variants. The results show that some variants of chaotic BAs can clearly outperform the standard BA for these benchmarks.
---
paper_title: A Bee Colony based optimization approach for simultaneous job scheduling and data replication in grid environments

paper_content:

This paper presents a novel Bee Colony based optimization algorithm, named Job Data Scheduling using Bee Colony (JDS-BC). JDS-BC consists of two collaborating mechanisms to efficiently schedule jobs onto computational nodes and replicate datafiles on storage nodes in a system so that the two independent, and in many cases conflicting, objectives (i.e., makespan and total datafile transfer time) of such heterogeneous systems are concurrently minimized. Three benchmarks - varying from small- to large-sized instances - are used to test the performance of JDS-BC. Results are compared against other algorithms to show JDS-BC's superiority under different operating scenarios. These results also provide invaluable insights into data-centric job scheduling for grid environments.
---
paper_title: A Genetic-Algorithm-Based Approach for Task Migration in Pervasive Clouds

paper_content:

Pervasive computing is converging with cloud computing which becomes pervasive cloud computing as an emerging computing paradigm. Users can run their applications or tasks in pervasive cloud environment in order to gain better execution efficiency and performance leveraging powerful computing and storage capacities of pervasive clouds through task migration. During task migration, there are possibly a number of conflicting objectives to be considered when making migration decisions, such as less energy consumption and quick response, in order to find an optimal migration path. In this paper, we propose a genetic algorithms- (GAs-) based approach which is effective in addressing multiobjective optimization problems. We have performed some preliminary evaluations of the proposed approach which shows quite promising results, using one of the classical genetic algorithms.The conclusion is that GAs can be used for decision making in task migrations in pervasive clouds.
---
paper_title: Multi-level hierarchic genetic-based scheduling of independent jobs in dynamic heterogeneous grid environment

paper_content:

Task scheduling and resource allocation are the key rationale behind the computational grid. Distributed resource clusters usually work in different autonomous domains with their own access and security policies that have a great impact on the successful task execution across the domain boundaries. Heuristics and metaheuristics are the effective technologies for scheduling in grids due to their ability to deliver high quality solutions in reasonable time. In this paper, we develop a Hierarchic Genetic Scheduler (HGS-Sched) for improving the effectiveness of the single-population genetic-based schedulers in the dynamic grid environment. The HGS-Sched enables a concurrent exploration of the solution space by many small dependent populations. We consider a bi-objective independent batch job scheduling problem with makespan and flowtime minimized in hierarchical mode (makespan is a dominant criterion). The empirical results show the high effectiveness of the proposed method in comparison with the mono-population and hybrid genetic-based schedulers.
---
paper_title: Independent Task Scheduling in Cloud Computing by Improved Genetic Algorithm

paper_content:

Scheduling is a critical problem in Cloud computing, because a cloud provider has to serve many users in Cloud computing system. So scheduling is the major issue in establishing Cloud computing systems. A good scheduling technique also helps in proper and efficient utilization of the resources. Many scheduling techniques have been developed by the researchers like GA (Genetic Algorithm), PSO (Particle Swarm Optimizati on), Min-Min, Max-Min, X-Sufferage etc. Thi s paper proposes a new scheduling algorithm which is an i mproved version of Genetic Algorithm. In the proposed scheduling algorithm the Min-Min and Max-Min scheduling methods are merged in standard Genetic Algorit hm. Min-Min, Max-Mi n and Genetic Scheduling techniques are discussed and in the last the performance of t he standard Genetic Algorithm and proposed improved Genetic Algorithm is compared and is shown by graphs.
---
paper_title: Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms

paper_content:

Grid technologies have progressed towards a service-oriented paradigm that enables a new way of service provisioning based on utility computing models, which are capable of supporting diverse computing services. It facilitates scientific applications to take advantage of computing resources distributed world wide to enhance the capability and performance. Many scientific applications in areas such as bioinformatics and astronomy require workflow processing in which tasks are executed based on their control or data dependencies. Scheduling such interdependent tasks on utility Grid environments need to consider users' QoS requirements. In this paper, we present a genetic algorithm approach to address scheduling optimization problems in workflow applications, based on two QoS constraints, deadline and budget.
---
paper_title: A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues

paper_content:

On parallel and distributed heterogeneous computing systems, a heuristic-based task scheduling algorithm typically consists of two phases: task prioritization and processor selection. In a heuristic based task scheduling algorithm, different prioritization will produce different makespan on a heterogeneous computing system. Therefore, a good scheduling algorithm should be able to efficiently assign a priority to each subtask depending on the resources needed to minimize makespan. In this paper, a task scheduling scheme on heterogeneous computing systems using a multiple priority queues genetic algorithm (MPQGA) is proposed. The basic idea of our approach is to exploit the advantages of both evolutionary-based and heuristic-based algorithms while avoiding their drawbacks. The proposedalgorithm incorporates a genetic algorithm (GA) approach to assign a priority to each subtask while using a heuristic-based earliest finish time (EFT) approach to search for a solution for the task-to-processor mapping. The MPQGA method also designs crossover, mutation, and fitness function suitable for the scenario of directed acyclic graph (DAG) scheduling. The experimental results for large-sized problems from a large set of randomly generated graphs as well as graphs of real-world problems with various characteristics show that the proposed MPQGA algorithm outperforms two non-evolutionary heuristics and a random search method in terms of schedule quality.
---
paper_title: Task Scheduling Algorithm based on Greedy Strategy in Cloud Computing

paper_content:

In view of Min-Min algorithm prefers scheduling small tasks and Max-Min algorithm prefers scheduling big tasks led to the problem of load imbalance in cloud computing, a new algorithm named Min-Max is proposed. Min-Max makes good use of time of greedy strategy, small tasks and big tasks are put together for scheduling in order to solve the problem of load imbalance. Experimental results show that the Min-Max improves the utilization rate of the entire system and saves 9% of the overall execution time compared with Min-Min. As compared to Max-Min, Min-Max improves the utilization rate of the entire system and the total completion time and average response time are saved by 7% and 9%, re- spectively.
---
paper_title: A New Resource Scheduling Strategy Based on Genetic Algorithm in Cloud Computing Environment

paper_content:

In view of the load balancing problem in VM resources scheduling, this paper presents a scheduling strategy on load balancing of VM resources based on genetic algorithm. According to historical data and current state of the system and through genetic algorithm, this strategy computes ahead the influence it will have on the system after the deployment of the needed VM resources and then chooses the least-affective solution, through which it achieves the best load balancing and reduces or avoids dynamic migration. At the same time, this paper brings in variation rate to describe the load variation of system virtual machines, and it also introduces average load distance to measure the overall load balancing effect of the algorithm. The experiment shows that this strategy has fairly good global astringency and efficiency, and the algorithm of this paper is, to a great extent, able to solve the problems of load imbalance and high migration cost after system VM being scheduled. What is more, the average load distance does not grow with the increase of VM load variation rate, and the system scheduling algorithm has quite good resource utility.
---
paper_title: An Greedy-Based Job Scheduling Algorithm in Cloud Computing

paper_content:

Nowadays/cloud computing has become a popular platform for scientific applications. Cloud computing intends to share a large number of resources such as equipments for storage and computation, and information and knowledge for scientific researches. Job scheduling algorithm is one of the most challenging theoretical issues in the cloud computing area. How to use cloud computing resources efficiently and increase user satisfaction with jobs scheduling system is one of the cloud computing service providers important goals. Some intensive researches have been done in the area of job scheduling of cloud computing. In this paper we have proposed Greedy-Based Algorithm in cloud computing. In order to prove our opinions we will process this artical as the following steps. First of all, we will classify tasks based on QoS. Then, according to the tasks categories, we will select the appropriate branch of the function and compute the justice evaluation. This will also reflects the greedy algorithm to select local optimum. Compare to other methods, it can decrease the completion time of submitted jobs and increases the user satisfaction.
---
paper_title: Credit Based Scheduling Algorithm in Cloud Computing Environment

paper_content:

Abstract Cloud computing in today's world has become synonymous with good service policies. In order to achieve good services from a cloud, the need for a number of resources arose. But cloud providers are limited by the amount of resources they have, and are thus compelled to strive to maximum utilization. Min-Min algorithm is used to reduce the make span of tasks by considering the task length. Keeping this in mind, cloud providers should achieve user satisfaction. Thus research favors scheduling algorithms that consider both user satisfaction and resources availability. In this paper an improved scheduling algorithm is introduced after analyzing the traditional algorithms which are based on user priority and task length. High prioritized tasks are not given any special importance when they arrive. The proposed approach considers all of these factors. The experimental results show a considerable improvement in the utilization of resources.
---
paper_title: Cost performance of QoS Driven task scheduling in cloud computing

paper_content:

Abstract Till now many parameters considered in QoS driven like makespan, latency and load balancing. But allocation cost parameter is not considered in QoS-driven scheduling algorithm. Minimizing the total allocation cost is an important issue in cloud computing. In this paper, the cost is calculated of QoS-driven task scheduling algorithm and compare with traditional task scheduling algorithm in cloud computing environment. The experimental results based on cloudsim3.0 toolkit with NetBeans IDE8.0 shows that QoS-driven achieves good performance in cost parameter.
---
paper_title: Resource-aware hybrid scheduling algorithm in heterogeneous distributed computing

paper_content:

Today, almost everyone is connected to the Internet and uses different Cloud solutions to store, deliver and process data. Cloud computing assembles large networks of virtualized services such as hardware and software resources. The new era in which ICT penetrated almost all domains (healthcare, aged-care, social assistance, surveillance, education, etc.) creates the need of new multimedia content-driven applications. These applications generate huge amount of data, require gathering, processing and then aggregation in a fault-tolerant, reliable and secure heterogeneous distributed system created by a mixture of Cloud systems (public/private), mobile devices networks, desktop-based clusters, etc. In this context dynamic resource provisioning for Big Data application scheduling became a challenge in modern systems. We proposed a resource-aware hybrid scheduling algorithm for different types of application: batch jobs and workflows. The proposed algorithm considers hierarchical clustering of the available resources into groups in the allocation phase. Task execution is performed in two phases: in the first, tasks are assigned to groups of resources and in the second phase, a classical scheduling algorithm is used for each group of resources. The proposed algorithm is suitable for Heterogeneous Distributed Computing, especially for modern High-Performance Computing (HPC) systems in which applications are modeled with various requirements (both IO and computational intensive), with accent on data from multimedia applications. We evaluate their performance in a realistic setting of CloudSim tool with respect to load-balancing, cost savings, dependency assurance for workflows and computational efficiency, and investigate the computing methods of these performance metrics at runtime. We proposed a hybrid approach for tasks scheduling in Heterogeneous Distributed Computing.The proposed algorithm considers hierarchical clustering of the available resources into groups.We considered different scheduling strategies for independent tasks and scheduling for DAG scheduling.We analyze the performance of our proposed algorithm through simulation by using and extending CloudSim.
---
paper_title: Cloud-aware data intensive workflow scheduling on volunteer computing systems

paper_content:

Abstract Volunteer computing systems offer high computing power to the scientific communities to run large data intensive scientific workflows. However, these computing environments provide the best effort infrastructure to execute high performance jobs. This work aims to schedule scientific and data intensive workflows on hybrid of the volunteer computing system and Cloud resources to enhance the utilization of these environments and increase the percentage of workflow that meets the deadline. The proposed workflow scheduling system partitions a workflow into sub-workflows to minimize data dependencies among the sub-workflows. Then these sub-workflows are scheduled to distribute on volunteer resources according to the proximity of resources and the load balancing policy. The execution time of each sub-workflow on the selected volunteer resources is estimated in this phase. If any of the sub-workflows misses the sub-deadline due to the large waiting time, we consider re-scheduling of this sub-workflow into the public Cloud resources. This re-scheduling improves the system performance by increasing the percentage of workflows that meet the deadline. The proposed Cloud-aware data intensive scheduling algorithm increases the percentage of workflow that meet the deadline with a factor of 75% in average with respect to the execution of workflows on the volunteer resources.
---
paper_title: Exploring decentralized dynamic scheduling for grids and clouds using the community-aware scheduling algorithm

paper_content:

Job scheduling strategies have been studied for decades in a variety of scenarios. Due to the new characteristics of the emerging computational systems, such as the grid and cloud, metascheduling turns out to be an important scheduling pattern because it is responsible for orchestrating resources managed by independent local schedulers and bridges the gap between participating nodes. Equally, to overcome issues such as bottleneck, single point failure, and impractical unique administrative management, which are normally led by conventional centralized or hierarchical schemes, the decentralized scheduling scheme is emerging as a promising approach because of its capability with regards to scalability and flexibility.In this work, we introduce a decentralized dynamic scheduling approach entitled the community-aware scheduling algorithm (CASA). The CASA is a two-phase scheduling solution comprised of a set of heuristic sub-algorithms to achieve optimized scheduling performance over the scope of overall grid or cloud, instead of individual participating nodes. The extensive experimental evaluation with a real grid workload trace dataset shows that, when compared to the centralized scheduling scheme with BestFit as the metascheduling policy, the use of CASA can lead to a 30%-61% better average job slowdown, and a 68%-86% shorter average job waiting time in a decentralized scheduling manner without requiring detailed real-time processing information from participating nodes. Highlights? We introduce a decentralized scheduling algorithm without requiring detailed node information. ? Our algorithm is able to adapt to the changes in grids through time by rescheduling. ? Comparisons with the known BestFit algorithm within a centralized scheduling scheme are made. ? Our algorithm leads to a 30%-61% better average job slowdown. ? Our algorithm leads to a 68%-86% shorter average job waiting time.
---
paper_title: Multi-objective energy-efficient workflow scheduling using list-based heuristics

paper_content:

Abstract Workflow applications are a popular paradigm used by scientists for modelling applications to be run on heterogeneous high-performance parallel and distributed computing systems. Today, the increase in the number and heterogeneity of multi-core parallel systems facilitates the access to high-performance computing to almost every scientist, yet entailing additional challenges to be addressed. One of the critical problems today is the power required for operating these systems for both environmental and financial reasons. To decrease the energy consumption in heterogeneous systems, different methods such as energy-efficient scheduling are receiving increasing attention. Current schedulers are, however, based on simplistic energy models not matching the reality, use techniques like DVFS not available on all types of systems, or do not approach the problem as a multi-objective optimisation considering both performance and energy as simultaneous objectives. In this paper, we present a new Pareto-based multi-objective workflow scheduling algorithm as an extension to an existing state-of-the-art heuristic capable of computing a set of tradeoff optimal solutions in terms of makespan and energy efficiency. Our approach is based on empirical models which capture the real behaviour of energy consumption in heterogeneous parallel systems. We compare our new approach with a classical mono-objective scheduling heuristic and state-of-the-art multi-objective optimisation algorithm and demonstrate that it computes better or similar results in different scenarios. We analyse the different tradeoff solutions computed by our algorithm under different experimental configurations and we observe that in some cases it finds solutions which reduce the energy consumption by up to 34.5% with a slight increase of 2% in the makespan.
---
paper_title: Heuristics for periodical batch job scheduling in a MapReduce computing framework

paper_content:

Task scheduling has a significant impact on the performance of the MapReduce computing framework. In this paper, a scheduling problem of periodical batch jobs with makespan minimization is considered. The problem is modeled as a general two-stage hybrid flow shop scheduling problem with schedule-dependent setup times. The new model incorporates the data locality of tasks and is formulated as an integer program. Three heuristics are developed to solve the problem and an improvement policy based on data locality is presented to enhance the methods. A lower bound of the makespan is derived. 150 instances are randomly generated from data distributions drawn from a real cluster. The parameters involved in the methods are set according to different cluster setups. The proposed heuristics are compared over different numbers of jobs and cluster setups. Computational results show that the performance of the methods is highly dependent on both the number of jobs and the cluster setups. The proposed improvement policy is effective and the impact of the input data distribution on the policy is analyzed and tested.
---
paper_title: Reliability-driven scheduling of time/cost-constrained grid workflows

paper_content:

Abstract Workflow scheduling in Grids and Clouds is a NP-Hard problem. Constrained workflow scheduling, arisen in recent years, provides the description of the user requirements through defining constraints on factors like makespan and cost. This paper proposes a scheduling algorithm to maximize the workflow execution reliability while respecting the user-defined deadline and budget. We have used ant colony system to minimize an aggregation of reliability and constraints violation. Three novel heuristics have been proposed which are adaptively selected by ants. Two of them are employed to find feasible schedules and the other is used to enhance the reliability. Two methods have been investigated for time and cost considerations in the resource selection. One of them assigns equal importance to the time and cost factors, and the other weighs them according to the tightness of satisfaction of the corresponding constraints. Simulation results demonstrate the effectiveness of the proposed algorithm in finding feasible schedules with high reliability. As it is shown, as an additional achievement, the Grid profit loss has been decreased.
---
paper_title: An incentive-based heuristic job scheduling algorithm for utility grids

paper_content:

Abstract Job scheduling in utility grids should take into account the incentives for both grid users and resource providers. However, most of existing studies on job scheduling in utility grids only address the incentive for one party, i.e., either the users or the resource providers. Very few studies on job scheduling in utility grids consider incentives for both parties, in which the cost, one of the most attractive incentives for users, is not addressed. In this paper, we study the job scheduling in utility grid by optimizing the incentives for both parties. We propose a multi-objective optimization approach, i.e., maximizing the successful execution rate of jobs and minimizing the combined cost (incentives for grid users), and minimizing the fairness deviation of profits (incentive for resource providers). The proposed multi-objective optimization approach could offer sufficient incentives for the two parties to stay and play in the utility grid. A heuristic scheduling algorithm called Cost-Greedy Price-Adjusting (CGPA) algorithm is developed to optimize the incentives for both parties. Simulation results show that the CGPA algorithm is effective and could lead to higher successful execution rate, lower combined cost and lower fairness deviation compared with some popular algorithms in most cases.
---

Title: Current Perspective in Task Scheduling Techniques in Cloud Computing: A Review

Section 1: INTRODUCTION
Description 1: This section provides an overview of cloud computing models and emphasizes the importance of efficient task scheduling, resource allocation, and resource sharing. It also introduces various scheduling approaches and outlines the paper's structure.

Section 2: TASK SCHEDULING TAXONOMY
Description 2: This section presents a novel taxonomy for classifying task scheduling approaches in cloud computing, based on Goal Oriented Task Scheduling (GOTS) and Constraint Oriented Task Scheduling (COTS).

Section 3: METAHEURISTIC BASED SCHEDULING
Description 3: This section reviews metaheuristic-based solutions for task scheduling, including Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), Artificial Bee Colony (ABC), and BAT Optimization.

Section 4: GENETIC ALGORITHM (GA) BASED SCHEDULING
Description 4: This section discusses various proposals that use Genetic Algorithms (GA) for task scheduling, including hybrid approaches that combine GA with other techniques.

Section 5: GREEDY APPROACH BASED SCHEDULING SCHEMES
Description 5: This section covers scheduling schemes that employ greedy algorithms to optimize resource utilization and task completion times in cloud environments.

Section 6: HEURISTIC BASED SCHEDULING
Description 6: This section explores heuristic-based scheduling methods and their application in optimizing different parameters like cost, time, and resource utilization in cloud computing.

Section 7: CONCLUSION
Description 7: This section summarizes the review of task scheduling schemes, highlights the proposed taxonomy, and discusses the implications of Goal Oriented Task Scheduling (GOTS) and Constraint Oriented Task Scheduling (COTS). It also suggests future research directions in the field of task scheduling in cloud computing.