Research On New Models And Algorithms For Periodic Multi-installment Divisible-load Scheduling

Divisible-load scheduling has become one of key issues for the information technologies in recent years.The current research mainly focuses on how to find a reasonable scheduling strategy to make large-scale computing in parallel and distributed systems with the most efficient way.Many studies have been done in the field of distributing data in single installment,but there have been only a few works on divisible-load scheduling with multi-installments in a non-blocking mode of communication system.This paper investigates divisible-load scheduling models and algorithms in a non-blocking heterogeneous distributed system.The main results are as follows:1.We investigate the multi-installment divisible-load scheduling problem while the distribution sequence of processors is given in advance.At first,a new multi-installments divisible-load scheduling model in a non-blocking heterogeneous distributed system is proposed,which can not only reach the goal of minimizing the processing time of the entire workload,but can obtain following three objectives as well:(1)the optimal number of processors can be obtained;(2)the optimal number of installments can be gotton;(3)the optimal load fraction is assigned to each processor in each installment.At second,we proved a series of good properties of the model and derived an explicit expression of the processing time with respect to the number of installments and the number of the processors.Furthermore,a new heuristic algorithm to solve the model is proposed.Finally,the experiments have been conducted and experimental results show the effectiveness of the proposed model and the efficiency of the proposed algorithm.2.We investigate the multi-installment divisible-load scheduling problem while the distribution sequence of processors is to be determined.Note that most of real world scheduling problems are in heterogeneous environments(the computing speed of each processor is different),and the communication speed of each communication link is different as well.Therefore,the processing time of the entire workload is affected by the distribution sequence of processors.Thus,this kind of problem is more complicated.To solve the problem,at first,we propose a new multi-installment divisible-load scheduling model,which can not only minimize the processing time of the entire workload,but also can obtain following four objectives:(1)the optimal distribution sequence of the processors can be obtained;(2)the optimal number of processors can be gotten;(3)the optimal number of installments can be obtained;(4)the optimal load fraction is assigned to each processor in each installment.At second,a new global optimization genetic algorithm is proposed for this model.Finally,we conduct several experiments to study the performance of the new model and new algorithm,and the results demonstrate that the proposed model and algorithm are effective and the proposed algorithm has a better performance than the compared scheduling method.