| With the development of science and technology,cloud computing attracting wide attention from scholars in various industries.Cloud computing resource scheduling problems are gradually becoming multi-machine and multi-stage.For example,in the cloud computing model,data can be transmitted by multiple servers,and the data transmission path can be divided into two stages.The external memory is transferred to the cloud server,and the cloud server is transmitted to the user through the network.This model is a two-stage scheduling problem in a typical multi-machine environment.At present,the main research goal of two-stage scheduling problem in multi-machine environment is to minimize the maximum completion time,while the research with the maximum profit as the goal is very few.Therefore,this thesis will study the the Multiple Two-Stage Flowshop Packing problem.In this thesis,we propose some approximate algorithms and analyze the complexity of the two-stage maximum revenue scheduling problem in multi-machine environment.The main content of this thesis is as follows:1.Based on the knapsack problem,it is proved that the Multiple Two-Stage Flowshop Packing problem is NP-hard problem,if NP≠P,and it is proved that it does not have a complete polynomial time approximation algorithm by using the knapsack problem.2.When the number of two-stage flowshop is the input of the algorithm,an approximate algorithm is proposed by using the greedy algorithm idea.The approximate ratio is 4,and the time complexity is O(n~3log n),where n is the number of two-stage jobs.Then the correlation between the multi-knapsack problem and this topic is analyzed,and combined with the approximate algorithm of the multi-knapsack problem,a new approximate algorithm is proposed.The approximate ratio is increased from 4 to 3+ε,whereεis a constant greater than0.3.When the number of two-stage flowshop is constant,this thesis constructs a two-stage machine state set model,and designs a pseudo-polynomial time algorithm based on the dynamic programming idea,whose time complexity is related to the time limit.By studying the multi-knapsack problem and the minimum completion time problem,combined with some new techniques,a better approximation algorithm is designed by enumerating part of the two-stage jobs,and then the subsequent two-stage jobs is skillfully filled.The approximation ratio is raised to 2+εonce again,whereεis a constant greater than 0. |
