工件可选择的平行机在线排序

On-line parallel machine scheduling with selective jobs

研究了一类平行机在线排序问题,且工件可以选择.用三参数法表示该模型为:Pm|on-line,rj,D|∑fj.其中D指机器使用期限,fj为工件Jj的加工利润,目标函数是使得在机器使用期限内所获总利润最大.本文给出了该模型fj=1情形(即工件费用相同)的所有在线算法竞争比的上界12,进而给出了两台机器、fj=1且工件序列只含两类工件情形(小工件加工时间为1,大工件加工时间为d≥2)的在线算法A1,其竞争比为1/2。

In this paper we consider an on-line parallel machine scheduling problem in which jobs can be chosen. Our model can be represented as ： Pm｜on-line,rj,D｜∑fj, in which D is the time limit of machines, fj is the profit by process- ing jobJj . The goal is to select jobs so as to maximize the total profit of all processed jobs during the period that machines can be used. We give an upper bound 1/2 of competitive ratio for the casefj= 1, And when there are only two machines, fj = 1 and jobs have only two kinds of processing time （small-jobs＇ processing time is 1 and large-jobs＇ processing time is d 1 2 ）, on-line algorithm has a competitive ratio of at least 1/2 and it is the best possible.