An Effective Cloud Workflow Scheduling Approach Combining PSO and Idle Time Slot-Aware Rules

Workflow scheduling is a key issue and remains a challenging problem in cloud computing.Faced with the large number of virtual machine(VM)types offered by cloud providers,cloud users need to choose the most appropriate VM type for each task.Multiple task scheduling sequences exist in a workflow application.Different task scheduling sequences have a significant impact on the scheduling performance.It is not easy to determine the most appropriate set of VM types for tasks and the best task scheduling sequence.Besides,the idle time slots on VM instances should be used fully to increase resources'utilization and save the execution cost of a workflow.This paper considers these three aspects simultaneously and proposes a cloud workflow scheduling approach which combines particle swarm optimization(PSO)and idle time slot-aware rules,to minimize the execution cost of a workflow application under a deadline constraint.A new particle encoding is devised to represent the VM type required by each task and the scheduling sequence of tasks.An idle time slot-aware decoding procedure is proposed to decode a particle into a scheduling solution.To handle tasks'invalid priorities caused by the randomness of PSO,a repair method is used to repair those priorities to produce valid task scheduling sequences.The proposed approach is compared with state-of-the-art cloud workflow scheduling algorithms.Experiments show that the proposed approach outperforms the comparative algorithms in terms of both of the execution cost and the success rate in meeting the deadline.

Time optimization for workflow scheduling based on the combination of task attributes

In order to reduce the scheduling makespan of a workflow,three list scheduling algorithms,namely,level and out-degree earliest-finish-time(LOEFT),level heterogeneous selection value(LHSV),and heterogeneous priority earliest-finish-time(HPEFT)are proposed.The main idea hidden behind these algorithms is to adopt task depth,combined with task out-degree for the accurate analysis of task prioritization and precise processor allocation to achieve time optimization.Each algorithm is divided into three stages:task levelization,task prioritization,and processor allocation.In task levelization,the workflow is divided into several independent task sets on the basis of task depth.In task prioritization,the heterogeneous priority ranking value(HPRV)of the task is calculated using task out-degree,and a non-increasing ranking queue is generated on the basis of HPRV.In processor allocation,the sorted tasks are assigned one by one to the processor to minimize makespan and complete the task-processor mapping.Simulation experiments through practical applications and stochastic workflows confirm that the three algorithms can effectively shorten the workflow makespan,and the LOEFT algorithm performs the best,and it can be concluded that task depth combined with out-degree is an effective means of reducing completion time.

Trust Based Meta-Heuristics Workflow Scheduling in Cloud Service Environment

Cloud computing has emerged as a new style of computing in distributed environment. An efficient and dependable Workflow Scheduling is crucial for achieving high performance and incorporating with enterprise systems. As an effective security services aggregation methodology, Trust Work-flow Technology (TWT) has been used to construct composite services. However, in cloud environment, the existing closed network services are maintained and functioned by third-party organizations or enterprises. Therefore service-oriented trust strategies must be considered in workflow scheduling. TWFS related algorithms consist of trust policies and strategies to overcome the threats of the application with heuristic workflow scheduling. As a significance of this work, trust based Meta heuristic workflow scheduling (TMWS) is proposed. The TMWS algorithm will improve the efficiency and reliability of the operation in the cloud system and the results show that the TMWS approach is effective and feasible.

Monte Carlo Simulation-Based Robust Workflow Scheduling for Spot Instances in Cloud Environments

When deploying workflows in cloud environments,the use of Spot Instances(SIs)is intriguing as they are much cheaper than on-demand ones.However,Sls are volatile and may be revoked at any time,which results in a more challenging scheduling problem involving execution interruption and hence hinders the successful handling of conventional cloud workflow scheduling techniques.Although some scheduling methods for Sls have been proposed,most of them are no more applicable to the latest Sls,as they have evolved by eliminating bidding and simplifying the pricing model.This study focuses on how to minimize the execution cost with a deadline constraint when deploying a workflow on volatile Sls in cloud environments.Based on Monte Carlo simulation and list scheduling,a stochastic scheduling method called MCLS is devised to optimize a utility function introduced for this problem.With the Monte Carlo simulation framework,MCLS employs sampled task execution time to build solutions via deadline distribution and list scheduling,and then returns the most robust solution from all the candidates with a specific evaluation mechanism and selection criteria.Experimental results show that the performance of MCLS is more competitive comparedwithtraditionalalgorithms.

The Application of Hybrid Krill Herd Artificial Hummingbird Algorithm for Scientific Workflow Scheduling in Fog Computing

Fog Computing(FC)provides processing and storage resources at the edge of the Internet of Things(IoT).By doing so,FC can help reduce latency and improve reliability of IoT networks.The energy consumption of servers and computing resources is one of the factors that directly affect conservation costs in fog environments.Energy consumption can be reduced by efficacious scheduling methods so that tasks are offloaded on the best possible resources.To deal with this problem,a binary model based on the combination of the Krill Herd Algorithm(KHA)and the Artificial Hummingbird Algorithm(AHA)is introduced as Binary KHA-AHA(BAHA-KHA).KHA is used to improve AHA.Also,the BAHA-KHA local optimal problem for task scheduling in FC environments is solved using the dynamic voltage and frequency scaling(DVFS)method.The Heterogeneous Earliest Finish Time(HEFT)method is used to discover the order of task flow execution.The goal of the BAHA-KHA model is to minimize the number of resources,the communication between dependent tasks,and reduce energy consumption.In this paper,the FC environment is considered to address the workflow scheduling issue to reduce energy consumption and minimize makespan on fog resources.The results were tested on five different workflows(Montage,CyberShake,LIGO,SIPHT,and Epigenomics).The evaluations show that the BAHA-KHA model has the best performance in comparison with the AHA,KHA,PSO and GA algorithms.The BAHA-KHA model has reduced the makespan rate by about 18%and the energy consumption by about 24%in comparison with GA.This is a preview of subscription content,log in via an institution to check access.

A multi-objective reinforcement learning algorithm for deadline constrained scientific workflow scheduling in clouds

Recently,a growing number of scientific applications have been migrated into the cloud.To deal with the problems brought by clouds,more and more researchers start to consider multiple optimization goals in workflow scheduling.However,the previous works ignore some details,which are challenging but essential.Most existing multi-objective work-flow scheduling algorithms overlook weight selection,which may result in the quality degradation of solutions.Besides,we find that the famous partial critical path(PCP)strategy,which has been widely used to meet the deadline constraint,can not accurately reflect the situation of each time step.Work-flow scheduling is an NP-hard problem,so self-optimizing algorithms are more suitable to solve it.In this paper,the aim is to solve a workflow scheduling problem with a deadline constraint.We design a deadline constrained scientific workflow scheduling algorithm based on multi-objective reinforcement learning(RL)called DCMORL.DCMORL uses the Chebyshev scalarization function to scalarize its Q-values.This method is good at choosing weights for objectives.We propose an improved version of the PCP strategy called MPCP.The sub-deadlines in MPCP regularly update during the scheduling phase,so they can accurately reflect the situation of each time step.The optimization objectives in this paper include minimizing the execution cost and energy consumption within a given deadline.Finally,we use four scientific workflows to compare DCMORL and several representa-tive scheduling algorithms.The results indicate that DCMORL outperforms the above algorithms.As far as we know,it is the first time to apply RL to a deadline constrained workflow scheduling problem.

Weighted-adaptive Inertia Strategy for Multi-objective Scheduling in Multi-clouds

One of the fundamental problems associated with scheduling workflows on virtual machines in a multi-cloud environment is how to find a near-optimum permutation.The workflow scheduling involves assigning independent computational jobs with conflicting objectives to a set of virtual machines.Most optimization methods for solving non-deterministic polynomial-time hardness(NP-hard)problems deploy multi-objective algorithms.As such,Pareto dominance is one of the most efficient criteria for determining the best solutions within the Pareto front.However,the main drawback of this method is that it requires a reasonably long time to provide an optimum solution.In this paper,a new multi-objective minimum weight algorithm is used to derive the Pareto front.The conflicting objectives considered are reliability,cost,resource utilization,risk probability and makespan.Because multi-objective algorithms select a number of permutations with an optimal trade-off between conflicting objectives,we propose a new decisionmaking approach named the minimum weight optimization(MWO).MWO produces alternative weight to determine the inertia weight by using an adaptive strategy to provide an appropriate alternative for all optimal solutions.This way,consumers’needs and service providers’interests are taken into account.Using standard scientific workflows with conflicting objectives,we compare our proposed multi-objective scheduling algorithm using minimum weigh optimization(MOS-MWO)with multi-objective scheduling algorithm(MOS).Results show that MOS-MWO outperforms MOS in term of QoS satisfaction rate.

Comparison of selected algorithms for scheduling workflow applications with dynamically changing service availability

This paper compares the quality and execution times of several algorithms for scheduling service based workflow applications with changeable service availability and parameters. A workflow is defined as an acyclic directed graph with nodes corresponding to tasks and edges to dependencies between tasks. For each task, one out of several available services needs to be chosen and scheduled to minimize the workflow execution time and keep the cost of service within the budget. During the execution of a workflow, some services may become unavailable, new ones may appear, and costs and execution times may change with a certain probability. Rescheduling is needed to obtain a better schedule. A solution is proposed on how integer linear programming can be used to solve this problem to obtain optimal solutions for smaller problems or suboptimal solutions for larger ones. It is compared side-by-side with GAIN, divide-and-conquer, and genetic algorithms for various probabilities of service unavailability or change in service parameters. The algorithms are implemented and subsequently tested in a real BeesyCluster environment.