一类Q_m/r_j/C_(max)on-line问题的LS算法分析

AN ON_LINE LS ALGORITHM FOR SOME Q m/r j/C max SCHEDULING

考虑一类 Ｑｍ／ｒｊ／ Ｃｍａｘ ｏｎ＿ｌｉｎｅ 排序问题的 Ｌ Ｓ算法（ ｍ 台机器，其中一台机器的速度为ｂ（ ｂ ＞ １） ，其余机器的速度都为１） ，证明这个算法的性能指标的上界是１ ＋ ｍ － １ｂ ．

An on_line LS algorithm for some Q m/r j/C max scheduling is provided, where the speed of one of m machines is b(b >1),others are 1. We prove that its performance guarantee is less than 1+ m-1b .