Application and comparison of hybrid evolutionary multiobjective optimization algorithms for solving task scheduling problem on heterogeneous systems
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 in V represents a subtask of the application task.
- •
E is the set of communication edges. The directed edge ei,j joins nodes and , where node is called the parent node and node 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:
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)
A comparison of study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems
Journal of Parallel and Distributed Computing
(2001)A genetic-algorithm-based approach for task matching and scheduling in heterogeneous computing environments
Journal of Parallel and Distributed Computing
(1997)- et al.
Using evolutionary programming to schedule tasks on a suite of heterogeneous computers
Computers & Operation Research
(1996) Genetic local search for multiobjective combinartorial optimization
European Journal of Operational Research
(2002)- et al.
Reliability versus performance for critical applications
Journal of Parallel and Distributed Computing
(2009) - et al.
A dynamic and reliability driven scheduling algorithm for parallel real-time jobs executing on heterogeneous clusters
Journal of Parallel and Distributed Computing
(2005) - et al.
Heterogeneous processing
IEEE Computer
(1993) - et al.
Computers and Intractability: A Guide to the Theory of NP-Completeness
(1979) - et al.
Performance-effective and low-complexity task scheduling for heterogeneous computing
IEEE Transaction on Parallel and Distributed Systems
(2002) - et al.
Matching and scheduling algorithms for minimizing execution time and failure probability of applications in heterogeneous computing
IEEE Transaction Parallel Distributed Systems
(2002)
Memetic algorithms for multiobjective optimization: issues, methods and prospects
A multi-objective genetic local search algorithm and its application to flowshop scheduling
IEEE Transaction on Systems, Man, and Cybernetics: Part C
Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling
IEEE Transaction on Evolutionary Computation
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 IntelligenceCitation 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 SoftwareCitation 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 ApplicationsCitation 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.
An Analytical Review and Performance Measures of State-of-Art Scheduling Algorithms in Heterogenous Computing Enviornment
2024, Archives of Computational Methods in Engineering