Research On Multi-objective Optimization Task Scheduling Algorithm For Heterogeneous Computing Systems

With the rapid development of software and hardware technology and the proliferation of computation-intensive applications,heterogeneous computing systems play a critical role in scientific computing,engineering control,and other fields by virtue of their high performance,flexibility,and scalability.As the main factor directly affecting the performance of heterogeneous computing systems,task scheduling has become a research hotspot.Due to the heterogeneity of system resources,the uncertainty of makespan,and the requirement of a low-carbon green economy,it is essential to design a multi-objective task scheduling algorithm that simultaneously optimizes the makespan and energy consumption.However,traditional multi-objective optimization task scheduling algorithms for heterogeneous computing systems have the following three problems that need to be solved urgently.First,many scholars mainly utilize linear weighting or ε-constraint strategy to find a unique optimal solution while ignoring valuable information about the Pareto front in the mathematical model.Second,several multi-objective evolutionary algorithms(MOEAs),such as strength Pareto evolutionary algorithm(SPEA-II)and fast non-sorting genetic algorithm(NSGA-II)were proposed to address the single workflow multi-objective optimization scheduling problems,but they easily get stuck in the local optimal due to lack of powerful local exploitation ability.In addition,the conventional MOEAs are essentially stochastic state-space search algorithms,which leads to slower convergence in some cases.Third,most current research in multi-objective optimization task scheduling algorithms for heterogeneous computing systems only consider single workflow scenarios,which lacks research on joint scheduling of multiple workflows.In view of these problems,this thesis designed a multi-objective task scheduling algorithm under single workflow and multiple workflow scenarios based on multi-objective memetic algorithm(MOMA)to simultaneously minimize the makespan and energy consumption on heterogeneous computing systems that DVFS-enabled.The main research contributions of this thesis are as follows:To take full advantage of information about Pareto front,this thesis first portrayed the system and workflow model,then constructed the makespan and energy consumption models,and finally introduced the concepts related to multi-objective optimization to establish a Pareto-based multi-objective task scheduling model.Aiming at the problem that the existing MOEAs have a slower convergence and the lack of powerful local exploitation ability,a single-workflow multi-objective memetic algorithm(SW-MOMA)based on MOMA is proposed in Chapter 3.First,a novel encoding strategy that can effectively prevent information loss is designed to fully utilize the valuable information of tasks and resources.Then,the evolutionary operators are improved to guarantee the validity of each solution.After that,a seed chromosome is introduced into the initial population to improve SW-MOMA’s convergence speed.Finally,the time-aware and energy-aware local search algorithms are proposed based on the solution structure to enhance the exploration and exploitation ability of the proposed algorithm.Experimental results demonstrate that SW-MOMA is able to obtain higher quality scheduling solutions on benchmarks and random workflows compared to existing algorithms.As for the joint multi-workflow scheduling problem,a multi-workflow multiobjective memetic algorithm(MW-MOMA)based on SW-MOMA is proposed in Chapter 4.First,multiple workflows are preprocessed to reduce the encoding complexity of MW-MOMA.Second,a double-ranking hierarchical algorithm is proposed to fully utilize the intra and inter-workflow ranking information.Finally,hierarchical crossover and mutation operators are proposed to further improve the global optimization ability of MW-MOMA.Experimental results indicate that MWMOMA can be effectively applied in multiple workflows scheduling scenarios,and it is superior to the existing algorithms in terms of C-metric,HV and IGD respectively.