Research For Algorithms On The Scheduling Problem Of Three Parallel Machines With Two GoS Levels

The scheduling problem is a kind of important combinatorial optimization problem in operational research,which mainly refers to the problem of reasonably arranging and allocating tasks and resources under the condition of limited resources,so that resources can be optimally used and tasks can be completed efficiently.It has extensive applications in various fields such as manufacturing,logistics,and public utilities,and with the continuous development of computer theory and technology,the depth and breadth of problem research have also been continuously expanded.Given n jobs and m machines,each job and machine are labeled with the grade of service(GoS)levels.And each job can be processed by a particular machine only when the GoS level of the job is not less than that of the machine.The scheduling problem requires finding an allocation scheme that minimizes the maximum completion time.This problem is NPhard(even if the number of machine is limited to 2),because it is easy to see that when there is only one GoS level,the problem is aleady a well-known NP-hard problem:the classical parallel machine scheduling problem.This dissertation studies the online and offline situations with two GoS levels,and limits the number of machines to 3.The following results are obtained:(1)In the online situation,one of the three machines has a GoS level of 1 and two machines have a GoS level of 2,and the three machines will be idle at the same time after the job arrives over time and all the jobs are processed.It is proved that the competitive ratio of any online algorithm cannot be better than 3/2,and a online algorithm with a competitive ratio of 5/3 is designed.(2)In the offline situation,one of the three machines has a GoS level of 1 and two machines have a GoS level of 2.Using the idea of "bundling’ and calling subroutines,an algorithm is designed to maintain the approximation ratio.Specifically,the approximation ratio α,where α is the approximation ratio achieved by the specific algorithm we call to solve the classical parallel machine scheduling problem;at the same time,our algorithm that maintains the approximation ratio can be extended to the case of any number of machines,as long as the GoS level of one of the machines is 1 and the GoS level of the remaining machines is 2.(3)In the offline situation,two of the three machines have a GoS level of 1 and one machine has a GoS level of 2.A polynomial time algorithm with an approximation ratio strictly less than 3/2 was designed,which is batter than the previous results from the perspective of approximation ratio.(4)In the offline situation,three machines are assigned any GoS level,but the processing time satisfies the power of 2.For the corresponding level allocation,corresponding polynomial time optimal algorithms are designed to solve it...