工件满足一致性的同类机在线分批排序问题

Online batch scheduling problem on uniform machines with agreeable processing times

研究了工件满足一致性,批容量无界的两台同类机在线分批排序问题,目标为极小化工件的最大完工时间和极小化工件的最大流程时间,三元素法分别表示为Q_2|r_i<r_j?p_i≤p_j,B=∞, on-line|C_(max),Q_2|r_i<r_j?p_i≥p_j,B=∞, on-line|F_(max).不失一般性,假设第一台机器速度为1,第二台机器速度为s,s≥1.对于上述两类问题设计了一个在线算法,并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α,这里α为α~2+sα-1=0的正根,特别地,当s=1时,该算法的竞争比不超过1.618.对第二类排序问题,该在线算法的竞争比不超过1+1/α.

We study the online batch scheduling problem on two uniform machines,where the batch capacity is unbounded.When the arrival times and the processing times of jobs are agreeable,two scheduling models whose objectives are to minimize the makespan and flow-time are developed and they are expressed as Q2|ri<rj?pi≤pj,B=∞,on-line|Cmax and Q2|ri<rj?pi≥pj,B=∞,on-line|Fmax.Without loss of generality,the speeds of the two machines are assumed to be 1 and s,s≥1.We propose an on-line algorithm and prove the competitive ratios of the algorithm are not more than s+αand 1+1/α,respectively,whereαis the positive root ofα2+sα-1=0.Moreover,for the former scheduling model,we prove that the competitive ratio of the algorithm is not more than 1.618,when s=1.