Scoring and Dynamic Hierarchy-Based NSGA-II for Multiobjective Workflow Scheduling in the Cloud

Abstract : Cloud computing becomes a promising technology to reduce computation cost by providing users with elastic resources and application-deploying environments as a pay-per-use model. More scientific workflow applications have been moved or are being migrated to the cloud. Scheduling workflows turns to the main bottleneck for increasing resource utilization and quality of service (QoS) for users. This work formulates workflow scheduling as multiobjective optimization problems and proposes a Scoring and Dynamic Hierarchy-based NSGA-II (Nondominated Sorting Genetic Algorithm II), called SDHN for short, to minimize both makespan and cost of workflow execution. First, a scoring criterion is developed to calculate the total score for each individual during population updating, which is used as a quantitative index to evaluate the dominance degree of individuals among the whole population. Hence, SDHN can distinguish individuals within the same dominance level and target its search toward the directions of elite solutions as their different dominance degrees and accordingly improve search efficiency. Second, a population-based dynamic hierarchical structure (HS) and its evolutionary rules are presented to update HS by comparing each child with all parental individuals from bottom to up until finding a proper dominant level. Since traversing all HS levels is not needed in most cases, the number of individual comparisons is reduced and SDHN's updating efficiency is greatly improved, especially for large-scale and complex applications. Third, to guarantee its converging to the near-optimal solutions, adaptive adjustment strategies (AASs) are designed to prevent the search from falling into local optima or diverging by checking the number of individuals at the highest HS level and then modifying the relevant genetic operations to guide the evolutionary process to approach the global Pareto Front. Extensive experiments are conducted to verify SDHN, and the results show that it outp...

 EXISTING SYSTEM :

 ? Cloud computing has become a standardized way of providing IT services delivered through Internet technologies in a pay-per-use and in a self-service way. ? Workflow scheduling tries to map the workflow tasks to the Virtual Machines (VMs) based on different functional and non-functional requirements. ? The flexibility of Cloud Services support any individual or organization to go for Cloud Computing. ? Researchers prefer the evolutionary algorithms to optimize the performance of the workflows rather than applying the heuristic scheduling algorithms and also Cloud Computing task scheduling differ from the other distributed environments viz.

 DISADVANTAGE :

 ? A Multi-objective Optimization Problem (MOP) is characterized by multiple conflicting objectives that require simultaneous optimization. ? Scheduling of scientific workflows in a distributed environment is a well-known NP-complete problem and therefore intractable with exact solutions. ? It is an NP-complete problem, so building an optimum workflow scheduler with reasonable performance and computation speed is very challenging in the heterogeneous distributed environment of clouds. ? Many existing studies deal with cloud workflow scheduling as a single or bi-objective optimization problem without considering some important requirements of the users or the providers.

 PROPOSED SYSTEM :

 • Linear clustering scheme and Dominant Sequence Clustering (DSC) had been proposed for this. Both works used computation and communication time of tasks in a workflow to determine a cluster of tasks. • It has been proposed for reducing data movement and increasing VM utilization. • This proprietary representation required specific implementation for genetic operators where population initialization, order crossover, taskto-instance crossover, and order mutation of EMO-NSGAII also were proposed for generating and manipulating a chromosome. • After a scheduling plan for a workflow execution is proposed, the number of VMs is also determined.

 ADVANTAGE :

 ? The PEFT heuristic provides guidance to the algorithm that improves the performance of the proposed method and allows for faster convergence to suboptimal solutions. ? Therefore, a smaller value of generational distance (GD) reveals a better performance of the achieved solution set. ? Compared with NSGA-II, the performance gain is over 50% in most of the cases whereas the improvement rate of HBMMO over MOHEFT is slightly better for small- and medium-size workflows. ? Predict Earliest Finish Time (PEFT) is an efficient heuristic in terms of makespan proposed for task scheduling in heterogeneous systems. ? The two conflicting objectives of the proposed scheme Hybrid Bio-inspired Metaheuristic for Multi-objective Optimization (HBMMO) are to minimize makespan and to reduce cost along with the efficient utilization of the VMs.