Some Research On Parallel Machine Online Scheduling Problem

In this thesis,we analyze the algorithm design and the optimality of the scheduling problem of the workpiece with similar processing time on the identical machines in the Ordinal semi-online model.The lower bound of the best approximation algorithm of the online scheduling problem on three uniform machines Q3|on-line|Cmax is improved.In the Ordinal semi-online model,we assume that there are n independent workpieces J1,J2,…,Jn to be processed on m identical parallel machines M1,M2,…,Mm.Each workpiece can only be processed one time on a machine,and the processing time of workpiece Ji is expressed by Pi,the scheduling time of the workpiece satisfies p1? p2?…? pn.Each arriving workpiece is arranged to a specific machine in turn according to the sequence number.Only one workpiece can be processed per machine at a time.In this thesis,the constraint condition of 1?pj?r(j=1,2,…,n)is added on the basis of the Ordinal semi-online model given by Liu([1]),we studied and improved the existing Pm algorithm and PmD algorithm when m=2.The results show that the worst performance ratio of PmD algorithm is better than Pm algorithm when the number of machines is m=2.In this thesis,we analyze the optimality of PmD algorithm when m=2,and prove that PmD algorithm is the best approximation algorithm when r?3/2.When 4/3?r?3/2,a new scheduling algorithm denoted as NPD algorithm is presented in this thesis.It is proved that the worst performance ratio of NPD algorithm in this interval is better than that of PmD algorithm,and NPD algorithm is the best approximate algorithm in this interval.For the online scheduling problem of three uniform machines Q3|on-line|Cmax,given the processing speeds si of three machines Mi(i=1,2,3),this thesis studies the special case that the speeds of three machines are s1=s2=s?1,s3=1.Suppose there are n independent workpieces J1,J2,…,Jn to be processed on these three machines,each workpiece can only be processed one time on a machine.pi represents the length of the workpiece Ji,and the processing time of the workpiece Ji is expressed by pi/si.The existing results show that the competition ratio of classical LS algorithm is min{4s+1/2s+1,3s+1/2s}.and proved that LS algorithm is the best possible online algorithm when s ? 3.When the interval of s is[1,3),the competition ratio difference between LS algorithm for this scheduling problem and the best possible online algorithm is less than 0.4299 according to existing literature.In this thesis,the parameter lower bound of the performance ratio of the best online algorithm for this scheduling problem is analyzed and calculated in more detail,and the larger lower bound of the parameter is obtained.The competitive ratio difference between LS algorithm and the best possible online algorithm is reduced from 0.4299 to 0.28054.