Research On Multi-installment Scheduling Models And Algorithms Based On Servers’ Available Times

With the advent of the era of big data,scientific applications concentrate more on data intensive computations.In order to meet the requirements of effective storage and efficient processing of big data,a variety of distributed platforms have emerged,such as cluster computing,cloud computing,edge computing and so on.It is worth noting that no matter what kind of computing platform it depends on,efficient task scheduling strategy is indispensable.However,most of the existing distributed task scheduling models assume that all servers are idle before tasks arrives,and that they can remain available online during task execution.In fact,all distributed platforms can barely ensure it.Different servers may have different available times.When assigning tasks on distributed servers,the available time of each server must be considered,otherwise tasks may not start or complete on time.In this thesis,we propose two new task scheduling models based on the constraints of server available time,and design efficient algorithms to solve them.Simulation results show the effectiveness of the proposed models and efficiency of our algorithms.The specific work of this thesis includes two aspects as follows.First,we established a uniform multi-installment scheduling model by considering available times of servers.It takes the shortest makespan of tasks as the objective.Then,an efficient heuristic algorithm is designed to solve this model,by which an optimal task allocation strategy is obtained.Through comparative experiments,it is proved that the proposed algorithm can solve the task scheduling problem with heterogeneous server available time.Compared with the existing scheduling models,the proposed one can achieve shortest makespan of tasks.Second,we considered the effect of server scheduling sequence on the makespan of tasks,and established a multi-installment scheduling model considering both server scheduling sequence and available time.The proposed model aims at the shortest makespan of tasks.At the same time,we designed an efficient evolutionary algorithm to solve the proposed model,including reasonable coding strategy,efficient crossover and mutation operators,and effective correction operators in order to make all individuals in the population meet the constraints of server available time.Simulation results show that the proposed algorithm can not only meet the constraints of server available time,but also obtain an optimal server scheduling sequence,thus minimizing the total makespan of tasks.