Elsevier

Applied Soft Computing

Volume 11, Issue 2, March 2011, Pages 2725-2734
Applied Soft Computing

Application and comparison of hybrid evolutionary multiobjective optimization algorithms for solving task scheduling problem on heterogeneous systems

https://doi.org/10.1016/j.asoc.2010.11.003Get rights and content

Abstract

Task scheduling problem in heterogeneous systems (TSPHS) is a multiobjective optimization problem (MOP). Multiobjective evolutionary algorithms (MOEA) are well suited for solving multiobjective task scheduling problem. In this paper, the two conflicting objectives namely, makespan and reliability are considered. The performance of MOEAs can be improved by hybridization with local search. Hybridization of MOEAs improves the convergence speed to Pareto front. Simple neighborhood search (SNS) algorithm is used as the local search algorithm. The weighted-sum based approach for solving the MOP with its hybrid version is compared. Then the two MOEAs: SPEA2 and NSGA-II are compared with each other in the pure and hybrid version for random task graphs and also for a real-time numerical application graph. The simulations confirm that Hybrid NSGA-II is best suited for solving the task scheduling problem.

Introduction

Heterogeneous systems consist of heterogeneous suite of machines, high speed interconnections interfaces, communication protocols and programming environments which provide a variety of architectural capabilities that has diverse execution requirements [1]. One of the key challenges of heterogeneous systems is the scheduling problem. Given an application modeled by a dependence graph, the scheduling problem deal with mapping each task of the application onto the available heterogeneous systems in order to minimize makespan. The task scheduling problem has been solved several years ago and is known to be NP-complete [2]. Several heuristic algorithms are proposed in the literature to solve this problem [3]. These heuristics are classified into different categories such as list scheduling algorithms, clustering algorithms, duplication based algorithms, guided random search algorithms. Genetic Algorithms [4], [5] are the most widely studied guided random search techniques, for task scheduling problems. Evolutionary programming (EP) is a mutation-based evolutionary algorithm applied to discrete search spaces and used in task scheduling [6].

As the heterogeneous systems become larger and larger, there is a possibility of processor and network link failures and this can have adverse impact on applications running on the system. In order to decrease the impact of failures on an application, task scheduling algorithms must be devised that optimize both makespan and reliability. In the literature several techniques have been developed to reduce the adverse effect of failures on applications executing on a heterogeneous system [7]. One approach is to employ a reliable scheduling algorithm in which tasks of an application are assigned to machines in such a way that the failure probability of the application is minimized. Unfortunately, increasing the reliability implies an increase of the makespan. This justifies the search for algorithms that both minimize makespan and minimize the failure probability.

Multi-objective evolutionary algorithm (MOEA) combines two major disciplines: evolutionary computation and theoretical frameworks of multi-criteria decision making. The goals in the development of MOEAs are twofold. The first goal is to improve the convergence of solutions to the Pareto front. The other goal is to increase the diversity of solutions. One promising strategy to improve the search ability of MOEAs is the hybridization with local search. Hybrid MOEAs (HMOEA) with local search are often referred to as memetic MOEA. The memetic algorithms for multiobjective optimizations are dealt in [8]. The first memetic MOEA was proposed in [9], where the weighted-sum of multiple objectives with random weights was used for local search. A similar algorithm with the weighted-sum based local search scheme was proposed in [10], [11], [12]. In [13], a different memetic MOEA called M-PAES, based on Pareto dominance rather than the weighted sum of multiple objectives is given.

Section snippets

Related work

Defining the multiple objectives for the task scheduling problem for generating efficient schedules at reduced computational times are of research interest in recent days. The objectives such as makespan, robustness and reliability are considered for solving the task scheduling problem. Multiobjective GA has been used for task scheduling in [14], [15]. In [14], the dependent relationships of tasks and multi-dimensional QoS metrics of completion time and execution cost of tasks, are considered

Task scheduling problem

The scheduling system model consists of an application, heterogeneous computing system and two of the objectives namely, makespan and reliability. The application is represented by a directed acyclic graph G (V, E, C, W), where:

  • V, the set of v nodes. Each node vi in V represents a subtask of the application task.

  • E is the set of communication edges. The directed edge ei,j joins nodes vi and vj, where node vi is called the parent node and node vj is called the child node. This implies the

Optimization problem

The task scheduling problem is formulated by considering the objectives of minimizing the makespan and maximizing the reliability of the schedules.

Principles of multi-objective optimization and HMOEA

Many real world problems involve simultaneous optimization of multiple objectives that often are competing. In a multi-objective optimization problem (MOP), one solution that is the best with respect to all objectives may not be achievable [26]. Usually the aim is to determine the trade-off surface, which is a set of non-dominated solution points, known as Pareto optimal solutions. Every individual in this set is an acceptable solution. Mathematically a MOP can be formulated as follows:Minimize

Implementation of MOEA to task scheduling problems

MOEA approaches start with a population of randomly generated candidate solutions and evolves toward better set of solutions (Pareto optimal front solutions) over number of generations or iterations. Its implementation for task scheduling problems is as given below.

Simple neighborhood search

The neighborhood structure with which the neighboring solutions are determined to move to is one of the important elements of any random search heuristics. Exchange and Insert are two neighborhood structures employed for this HMOEA.

  • Exchange is a function used to move around. Here any two randomly selected genes are simply swapped. For example, if we have a matching string m1 = [211200] and the two random numbers derived are 2 and 4. After applying the Exchange, the new matching string will be

Simulation results and discussion

To test the effectiveness of the HMOEA for the task scheduling, the solutions were obtained for random task graphs. A Random task graph was generated using the method as proposed in [5]. There are few parameters involved in the random task graph generation and they are: Number of nodes, shape parameter, outdegree, average computation cost, computation to cost ratio, average communication cost and heterogeneity factor.

In this paper, the input parameters of the directed acyclic graph generation

Conclusion

In this paper, we have studied the problem of scheduling tasks graph on heterogeneous systems. We have used evolutionary algorithms for solving this scheduling problem with two objectives: makespan and reliability. The evolutionary algorithms namely, GA and EP are used to solve the TSPHS. The best solution obtained using weighted sum based GA and EP for the Gauss elimination task graph is compared. GA proves to be better than EP for solving the TSPHS. A hybrid version of this weighted sum based

References (27)

  • J.D. Knowles et al.

    Memetic algorithms for multiobjective optimization: issues, methods and prospects

  • H. Ishibuchi et al.

    A multi-objective genetic local search algorithm and its application to flowshop scheduling

    IEEE Transaction on Systems, Man, and Cybernetics: Part C

    (1998)
  • H. Ishibuchi et al.

    Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling

    IEEE Transaction on Evolutionary Computation

    (2003)
  • Cited by (46)

    • Energy efficient multi-objective scheduling of tasks with interval type-2 fuzzy timing constraints in an Industry 4.0 ecosystem

      2020, Engineering Applications of Artificial Intelligence
      Citation Excerpt :

      Apart from these, there are single objective approaches such as for random scheduling (Boyer and Hura, 2005). Multi-criteria task scheduling problem has been reliability (Chitra et al., 2011), makespan and load balancing (Boyer and Hura, 2005), total cost and makespan (Tsai et al., 2013) etc. None of these considered the objectives of processor energy minimization and earliness of task completion under IT2 fuzzy uncertainty, which we have studied and solved in this paper.

    • Quantum genetic algorithm based scheduler for batch of precedence constrained jobs on heterogeneous computing systems

      2018, Journal of Systems and Software
      Citation Excerpt :

      Some examples of MOEA are Non-dominated Sorting Genetic Algorithm (NSGA I and II) designed by Deb et al. (2002), Pareto-Archived Evolution Strategy (PAES) by Knowles and Corne (1999) and Strength-Pareto Evolutionary Algorithm (SPEA) by Zitzler (1999). Multi-objective Evolutionary Algorithm (MOEA) based scheduling models for distributed systems can be seen in Chitra et al. (2011), Raza and Vidyarthi (2010), Grosan et al. (2007), Canon and Jeannot (2010), Khaled Ahsan Talukder et al. (2009), Jiang (2015), Ye et al. (2006), Ishibuchi and Murata (1998), Durillo and Prodan (2014), Yu et al. (2007) and Zhu et al. (2016). Scheduling is the allocation of modules of the job on processing nodes statically or dynamically with the intention of optimizing the desired Quality of Service (QoS) parameters.

    • Integrated production and delivery with single machine and multiple vehicles

      2016, Expert Systems with Applications
      Citation Excerpt :

      An NSGA-II optimization algorithm combined with a tabu search was proposed to provide Pareto optimal solutions. Chitra, Rajaram, and Venkatesh (2011) considered a task scheduling problem in heterogeneous systems. To solve the problem, they constructed two multi-objective evolutionary algorithms: SPEA2 (the Strength Pareto Evolutionary Algorithm 2) and NSGA-II.

    View all citing articles on Scopus
    View full text