如何证明按短作业优先算法调度时其平均周转时间最短

Question

如何证明按短作业优先算法调度时其平均周转时间最短

Answer 1

假设有n个作业，按照运行时间排序t1 < t2 t1 + t2 + ... + t(i-1) + ti = a(i+1)
依次类推之后bx > ax 其中i < x < j+1.之后b与a又相等。
所以任意交换后，等待时间变大。所以最小作业优先的等待时间最小。所以平均周转时间最短。