如何证明按短作业优先算法调度时其平均周转时间最短
假设有n个作业，按照运行时间排序t1 < t2 t1 + t2 + ... + t(i-1) + ti = a(i+1)依次类推之后bx > ax 其中i < x < j+1.之后b与a又相等。所以任意交换后，等待时间变大。所以最小作业优先的等待时间最小。所以平均周转时间最短。
假设有n个作业，按照运行时间排序t1 < t2 <... < tn平均周转时间 = （总的运行时间 + 总的等待时间）/n其中总的运行时间是定值，n为定值，因此要平均周转时间最短既要求总的等待时间最短。按照最短作业优先，设第i个作业的等待时间为ai.则a1 = 0a2 = t1a3 = t1 + t2....an = t1 + t2 + ... + t(i-1)总的等待时间为a1 + a2 + a3 + ... + an现在只需要证明这个是最小就可以了。任意取2个作业i 和 j。 且ti < tj。交换ti和tj的顺序。则新等待时间变成b0 b1 b2 .... b(i-1)  bi b(i+1) ..... b(j-1) bj b(j+1) ... bn 其中b0 + b1 + ... + b(i-1) + bi与原来的a相等。 b(i+1) = t1 + t2 + ... + t(i-1) + tj > t1 + t2 + ... + t(i-1) + ti = a(i+1)依次类推之后bx > ax  其中i < x < j+1.之后b与a又相等。所以任意交换后，等待时间变大。所以最小作业优先的等待时间最小。所以平均周转时间最短。