1、 证明当最优调度在任何机器上至多包含 2 个作业时，LPT 也是最优的。 证明： 设 n=2m ， 若 n<2m, 则 令 J , J  2 , , n J 2 m n 1  均 为 0 ， 将 其 加 入 实 例 I 中 ， 不 妨 设 PP 1 2     P n   1   P 2 m 设最优调度使得每台机器恰有 2 个作业： i JJ , ，则必有 j  , mjmi  。否则若某最优调度 O 有 ,i j m ，则必定有某台机器上有 sJ 和 tJ ，使得 s,t>m. 因为： P P i j ,  P P s t , 那么：交换 ,j tP P 有： t i      P P i j P P s  和 j P P P P i j 显然，交换后的调度O 的最迟完成时间只可能减少，所以O 也是最优调度。 若某最优调度 O 有 ,i j m ，则必定有某台机器上有 sJ 和 tJ ，使得 ,s t m 因为： P P i j ,  P P s t , 那么：交换 ,j tP P 有： i s       和 j P P P P t P P P P s t 显然，交换后的调度O 的最迟完成时间只可能减少，所以O 也是最优调度。 J 1  分别分配到 1, , JJ M 所以，必有最优调度使 M 上，当将 mJ m 1  J , 2 , t s , m ,  2 , , J 2 m 分 m 配到 M 台机器上时，LPT 是将长时间的作业分配到轻负载上，必与该最优调度结果相同。 即： ( ) A I ( ) OPT I    1 4 3 1 3 m ( m  2)