Algorithms For Research Scheduling Problems In Cloud Manufacturing

Cloud manufacturing is a new manufacturing model based on the network,according to the needs of users.Resources in the cloud manufacturing environment are decentralized,and resources can be integrated through the cloud manufacturing platform to realize on-line transaction of resource use rights,which is beneficial to resource sharing and synergy to achieve win-win outcomes.This thesis mainly studies the problem of parallel machine scheduling for a given budget total cost in a cloud manufacturing environment.The thesis contains five chapters.In chapterl,we first intruduce some basic concepts of the scheduling problem and cloud manufacturing,and summarize the research results of cloud manufacturing resource schedul-ing in recent years.In chapter 2,we mainly study uniform parallel machine scheduling problems with fixed machine cost,and the goal is to miniminze the makespan.We consider two cases.The first case assumes that the jobs with different sizes and the machine with fast speed has a greater unit cost speed.We give an approximation algorithm with worst-case ratio of 2(1 + 1/h-1);The second case assumes that the jobs have the same sizes and we give an approximation algorithm with worst-case ratio of 2(1 + ?)(1-1/m);In chapter 3,we mainly study uniform parallel machine scheduling problems with unit time processing cost.We consider the case where the jobs are fractional,and the goal is to miniminze the makespan.We give an optimal algorithm of the problem.In chapter 4,we mainly study identical parallel machine scheduling problem with unit time processing cost,and the goal is to maximize the minimum machine completion time within a given cost.For preemptive case,we provide an optimal algorithm of the problem.In chapter 5,we summarize the full text and put forward the related issues as the next research direction.