Parallel Machine Scheduling With Machine Release Times And Eligibility Restrictions

In this paper,we discuss the parallel machine scheduling with machine prepa-ration time and machining qualification constraints,and study the minimization of the target function as the maximum completion time and the maximum delay time respectively.First,we analyze the NP-hardness of the problem,then discuss the optimal algorithm of the problem in many special cases,and finally,on this basis,propose a heuristic algorithm with better time complexity for the original problem.In the first part,we consider the minimization of the make-span.Firstly,for the problem Pm,Ri|pj=p,Mj| Cmax,we give the optimal algorithm with times complexity of O(m3/2n5/3logmn and O(n log n).Then,for the problem Pm,Ri |Mj|Cmax we propose a heuristic algorithms with three time complexity of O(n log n).In the second part,we consider the minimization of the maximum lateness.Firstly,for the problems Pm,Ri | pj=1,Mj| Lmax,Pm | intree,pj=1,Mj|Lmax and P2 |prec,pj=1,Mj |Lmax,we prove that there are optimal algorithms with time complexity of O(n log n),O(n log n)and O(n2).Then,for the prob-lem Pm,Ri |Mj| Lmax,we propose a heuristic algorithm with time complexity of O(n log n).In the third part,we consider the parallel machine scheduling problem with machine release time and eligibility restrictions,job release time.For the problems Pm,Ri | rj,Mj |Cmax and Pm,Ri | rj,Mj| Lmax,we present a heuristic algorithm with time complexity of O(n log n).In summary,The algorithm we designed on reasonable assumptions is correct.It has clear ideas and little time complexity.Not only can solve practical problems well,but also has strong practical value and promotion significance.