我们不知道MS的最优解是什么，但是我们总是可以给出最优解的某些性 质，依据这些性质，可以讨论具体这个算法的解和最优解之间的差距 GMS算法的误差分析中的几个概念： OptMs(I)≥p1≥p2≥··≥pn. Clearly, OptMS(I)≥ p 4.2 m P%≤ 4.3 k
GMS算法的误差分析中的几个概念： 4.2 我们不知道MS的最优解是什么，但是我们总是可以给出最优解的某些性 质，依据这些性质，可以讨论具体这个算法的解和最优解之间的差距 4.3
证明概要（只讨论任务数大于机器数）： 何意？ Let n>m. Let T be such that cost(Ti)=EreT Pr cost(GMS(I)】 and let k be the largest index in T.If k m,then T=1 and so Optms(I)=p1 pk and GMS(I)is an optimal solution. 为什么？ Now,assume m k.Following Figure 4.2 we see that 什么是T和k? 这里有完整证明中的第二层分情形证明，是什么？
证明概要(只讨论任务数大于机器数)： 什么是Tl和k？ 这里有完整证明中的第二层分情形证明，是什么？ 何意？ 为什么？
从图中，我们能看出什么？ 什么是cost(GMSI)? cost(GMS(I)) P1 P2 Pk cost(GMS(I))-Pk 什么是cost(GMSI-Pk? ∑ip:≥m·[cost(GMS(O)-p OptMs(I)≥ ∑2四 OptMs(I)>cost(GMS(I))-pk m
从图中，我们能看出什么？ 什么是cost(GMS(I))? 什么是cost(GMS(I))-Pk? Tl