带机器准备时间的同类机在线与半在线排序问题

ON-LINE AND SEMI ON-LINE SCHEDULING ON UNIFORM MACHINES WITH NON-SIMULTANEOUS MACHINE AVAILABLE TIMES

研究带机器准备时间的m台同类机 (uniformmachines)在线和半在线排序问题 ,目标函数为极小化最大机器 (工件 )完工时间 .对于在线情形 ,证明了LS算法的最坏情况为 ρ =( 1+ 5 ) 2 ,m =2 ,1+ 2m - 2 2 ,m≥ 3 ,并且当m =2时 ,LS算法是最好的近似算法 ;当m =2 ,3 ,… ,6时界是紧的 ,特别地 ,当s1 =s2 =… =sm - 1 ,sm ≥ 1时 ,证明了LS算法的最坏情况界为 ρ =( 1+ 5 ) 2 ,m =2 ,3 - 4 (m + 1) ,m≥ 3 ,而且界是紧的 ;对于已知加工时间递减的半在线排序问题 ,证明了LS算法的最坏情况界为 2 - 2 (m + 1) .

This paper investigates on-line and semi on-line scheduling problems on uniform machines with non-simultaneous machine available times. In on-line vertion, it is proved that the worst case performance ratio of LS algorithm is ρ=(1+5)/2, m=2, 1+2m-2/2, m≥3, furthermore, LS algorithm is the best possible approximation algorithm when m=2 and the bound is tight when m=2,3,...,6. For the case that s 1=s-2=...=s m-1, s-m≥1, it is proved that the worst case performance ratio of LS algorithm is ρ=(1+5)/2, m=2, 3-4/(m+1), m≥3, and the bound is tight. For the semi on-line scheduling where the jobs are ordered in decreasing times, it is proved that the worst case performance ratio of LS algorithm is 2-2/(m+1).