Research On New Models And Algorithms For Divisible-load Scheduling

The production of massive data has brought more problems and tests for the progress of society.With the development of science and technology,in the calculation of data information,people have gradually transformed from traditional single node,serial,and mainframe processing modes to multi-node,parallel,and multi-machine distributed processing modes.How to reasonably divide the tasks of each computing node and get the optimal task scheduling strategy has become a research hotspot.The theory of divisible load is a good approximation to many problems in the real world,such as data mining,network storage,data intensive computing and so on.The theory is characterized by simple and easy to understand,and good compromise on the simplicity and accuracy of the model.The research content of this paper is that in the heterogeneous star network,combining the actual situation,two new scheduling models are established,and corresponding efficient algorithms are designed.Mainly for the following two aspects: 1.For the single-installment scheduling problem with time window constraints for the processor in the star network,the most reasonable task partitioning strategy and the most efficient processor scheduling order can be solved by the designed algorithm,which can make the total task calculation time optimal.On the basis of existing research,the concept of time-window is introduced first,it makes the model more practical.Then we propose a novel time-window aware divisible-load scheduling non-blocking model.Meanwhile,we design a genetic algorithm for the proposed model.In order to solve the model quickly and efficiently,we encode the load partition and the distribution sequence of processors at the same time.Then we design different crossover operators to optimize the load partition and the distribution sequence of processors,and a modifiy operator is designed to modify the load partition scheme which does not satisfy the processors' time-window.Morever,we design an efficient local search operator to speed up the convergence rate of the algorithm.Finally,the simulation experiment is carried out,the results show that under the constraint of the processor time-window,our algorithm improve the performance of the existing algorithm by at least 20%,it proves the correctness and effectiveness of the proposed algorithm.2.For the multi-squeezing scheduling problem with time window constraints for the processor in the star network,the most appropriate scheduling parameters,the number of processors involved in the calculation,and the most reasonable task partitioning strategy can be solved by the designed algorithm,which can make the total task calculation time optimal.Firstly,a new non-blocking optimization model for multi-installment scheduling is established.This model is mainly used to model the time-window constraints of the processor in the system.At the same time,a new efficient algorithm is designed to solve this problem.In the proposed algorithm,the number of internal scheduling parameters is first obtained through mathematical derivation,and then based on the existing research,a genetic algorithm with local search is designed to calculate the last scheduled task volume.Finally,the simulation results show that the proposed algorithm is superior to the existing algorithms in the multi-installment scheduling with time window,and the efficiency of the proposed algorithm is proved.