A New Hybrid Algorithm Based on Improved MODE and PF Neighborhood Search for Scheduling Task Graphs in Heterogeneous Distributed Systems

Abstract

Multi-objective task graph scheduling is a well-known NP-hard problem that plays a significant role in heterogeneous distributed systems. The solution to the problem is expected to optimize all scheduling objectives. Pretty large state-of-the-art algorithms exist in the literature that mostly apply different metaheuristics for solving the problem. This study proposes a new hybrid algorithm comprising an improved multi-objective differential evolution algorithm (DE) and Pareto-front neighborhood search to solve the problem. The novelty of the proposed hybrid method is achieved by improving DE and hybridizing it with the neighborhood search method. The proposed method improves the performance of differential evolution by applying appropriate solution representation as well as effective selection, crossover, and mutation operators. Likewise, the neighborhood search algorithm is applied to improve the extracted Pareto-front and speed up the evolution process. The effectiveness and performance of the developed method are assessed over well-known test problems collected from the related literature. Meanwhile, the values of spacing and hyper-volume metrics are calculated. Moreover, the Wilcoxon signed method is applied to carry out pairwise statistical tests over the obtained results. The obtained results for the makespan, reliability, and flow-time of 50, 18, and 41, respectively, by the proposed hybrid algorithm in the study confirmed that the developed algorithm outperforms all proposed methods considering the performance and quality of objective values.

Keywords

• evolutionary computation
• optimization
• processor scheduling
• pareto optimization
• heuristic algorithms