第四章作业部分参考答案1.设有n个顾客同时等待一项服务。顾客i需要的服务时间为t,1ini应该如何安排n个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。试给出你的做法的理由(证明)。策略：对t1in进行排序，ttt,然后按照递增顺序依次服务i,i，,iii1i2in12n即可。解析：设得到服务的顾客的顺序为j,j,.,j，则总等待时间为12nT二(n-1)t+(n-2)t+2t+1,则在总等待时间T中t的权重最大，tj1j2j”-2jn-1j1j的权重最小。故让所需时间少的顾客先得到服务可以减少总等待时间。证明：设ttt,，下证明当按照不减顺序依次服务时，为最优策略。i1i2in记按照iii次序服务时，等待时间为T，下证明任意互换两者的次序，T12n都不减。即假设互换i,j(ij)两位顾客的次序，互换后等待总时间为T，则有由于+t,in2in1i2T二(n1)t+(n2)tHb2ti1T=(n1)t+(n2)t
