Research On Two-stage Job Scheduling Algorithm With Deadline In Multi-machine Environment

The demand for resources required to record and process data in the era of Big Data is beginning to grow.The emergence of cloud computing is well suited to meet this demand.In cloud computing,resource scheduling has recently attracted the attention of researchers.In cloud computing systems with high real-time requirements,client resource requests are considered as two-stage jobs with deadlines and servers in the cloud are considered as two-stage machines.According to the service model of cloud computing,the completion of resource requests can be rewarded accordingly.In this model,for a cloud service center with multiple servers and a large number of resource requests at the same time,given a set of resource requests,they are scheduled on the servers in the data center such that the maximum profits is obtained by completing the resource requests.This is exactly the Multiple Flowshop Scheduling with Maximized Profits(MFP)scheduling model studied in this thesis,which has some practical significance.At present,domestic and foreign research on two-stage job scheduling mainly aims at minimizing the maximum completion time.And the problem of scheduling two-stage jobs with deadlines on multiple two-stage machines with the goal of maximizing profits has not been considered.Therefore,in this thesis,we systematically study this resource scheduling problem in conjunction with the classical Flowshop scheduling model.The main points of this thesis are as follows.(1)MFP(r,t)model for all jobs with the same R-time and T-time,where r is the R-time of all jobs and t is the T-time of all jobs.In this thesis,an exact algorithm for polynomial time is proposed based on the idea of dynamic programming.The proof of correctness of the algorithm is completed by mathematical induction.The time complexity and space complexity of the algorithm are analyzed as O(n~2),and the efficiency of the algorithm is proved.(2)For the MFP(p)model in which all jobs have the same profit p,the MFP(p)model is proved to be NP-hard according to the partition problem,and from the simplified single-stage scheduling problem of the MFP(p)model,it is proved that the solution obtained by the exact algorithm of the single-stage scheduling problem is an upper bound for the optimal solution of the MFP(p)model,and finally an efficient heuristic algorithm is proposed according to the rules of Moore's algorithm.And the efficiency of the algorithm is proved by benchmark tests.(3)For the MFP model without any restrictions,in which the job has different deadlines,R-times,T-times and profits.The MFP model is proved to be NP-hard based on the knapsack problem,and a fully polynomial time approximation scheme(FPTAS)for the simplified single-stage scheduling problem is designed from the simplified single-stage scheduling problem of the MFP model,and it is shown that the solution obtained by the FPTAS for the single-stage scheduling problem is an upper bound for the optimal solution of the MFP model.Based on this,an efficient heuristic algorithm is proposed,and the efficiency of the algorithm is demonstrated by benchmark tests.