第6题 加油站加油排队
某个加油站每次只能对一种车辆加油。各种车辆的加油时间如下：
车型： 大型卡车 中型卡车 小汽车
时间(分)： 7 5 4
如果这三种车辆同时到达加油站加油，问加油站应该怎样安排加油顺序，才能使总共需要的时间(加油及等候时间最省？
分析：由于加油站一次只能对一种车辆加油，所以三种车辆同时到达，必定产生有两种车辆要等候。要节省时间，必须尽量减少等候时间，而让加油时间短的车辆先加油，就能节省总的加油及等候时间。我们不妨计算一下按大型卡车、中型卡车、小汽车加油顺序所需总的等候时间：
7＋7＋7＋5＋5＋4= 35(分)
如果按大型卡车、小汽车、中型卡车的加油顺序计算总的等候时间为：
7＋7＋7＋4＋4＋5= 34(分)
显然，第二种方案比第一种方案好一些。如果我们把所有的加油方案一一列举出来，通过计算，就能找到最优方案。对于这样的问题是否有规律性，利用它还能解决更一般的情形吗？
解：由于加油时间分别为7分、5分和4分钟，所以合理的方案是安排加油时间短的车辆先加油，这样其他两种车辆的等候时间就较短，因此按小汽车、中型卡车、大型卡车的加油顺序计算总的等候时间为最少。
4＋4＋4＋5＋5＋7= 29(分)
回顾：如果有几种不同类型的车辆同时到达加油站，加油的时间分别为T1、T2 …Tn ，则等候的总时间T为：
T＝nT1+ (n- 1)T2+ (n- 2)T3＋…+Tn
要使T最少，只有当T1≤T2≤…≤Tn 时，T取到最小，因此必须安排加油时间短的车辆先加油，加油时间长的车辆放在后面。
下面我们考虑将上述问题从加油站的加油能力方面加以推广：
如果加油站能够同时对两种车辆加油，对各种车辆的加油所需时间为：
车型： 重型车 大卡车 中型卡车 小汽车 微型车
时间(分)： 10 7 5 4 3
车型：摩托车
时间(分)： 2
如果有上述六种不同类型的车辆同时到达，又应该如何安排加油顺序呢？
首先必须考虑分成二组，分组和编排加油顺序仍然以尽量减少等候时间为原则。第一种方案是每组各三辆车设第一组，加油时间分别为T1、T2、T3，则总共需要时间为：
T1+ (T1＋T2)+ (T1+ T2+ T3)＝ 3T1＋ 2T2＋T3
同理，另一组为3t1+ 2t2＋t3，六种车辆所需的总时间T为：
T= 3(T1 ＋t1 )＋2(T2+t2)＋(T3 ＋t3 )
从式子中可以看出，T1＋t1尽可能小。因此，摩托车、微型车安排在最前，小汽车、中型卡车其次，而大卡车及重型车安排在最后。即分成的两组为：
第一组：摩托车、小汽车、大卡车
第二组：微型车、中型卡车、重型车
所需总时间T为：
T= 3(2＋3)+ 2(4＋5)＋(7＋10)= 50(分)
如果按另一种方案编成四辆和二辆的两组又如何呢？显然时间为：
(4T1＋3T2 +2T3 ＋T4 )＋(2t1+t2)= T1 ＋3(T1+ T2)
＋2(T3＋t1)+ (T4＋t2)
与第一种方案作同样的分析，多了一个T1，不是最节省。同样以五辆与一辆为两组的所需时间更不节省了。
注：下面我们不加证明地介绍一个不等式的结论，上述问题也可看作它的一个应用。
假设有两组数： a1 ， a2，…， an； b1 ， b2 ，…， bn，满足：
a1≤a2 ≤…≤an； b1≤b2 ≤…≤bn，我们称：
a1b1＋a2b2 +a3 b3 ＋…＋anbn 为顺序和；
a1bn＋a2 bn－1 + …+ anb1 为逆序和；
ai1bj1＋ai2bj2＋…＋ainbjn(1≤i1，i2，…， in≤n， 1≤j1，…，
jn≤n)为乱序和。
在不等式中有：顺序和≥乱序和≥逆序和。(证明从略)
在上述问题中的总时间T= nT1 ＋(n- 1)T2 ＋…＋Tn的情况下，要使T最小，取其逆序和即可，即有T1≤T2≤…≤Tn。
练习6
1．某加工厂加工某一批零配件，需要加工后才能送到下一道工序继续加工，否则只能等待。已知各种类型的零件加工时间如下：
零件类型：1 2 3 4 5
加工时间：55 40 30 80 60 (单位：分)
问如何安排加工顺序才能使总的等待时间最短？
2．如果这5种零件需要先后两种工序加工，加工时间如下表，又应该如何安排加工顺序呢？
零件类型： 1 2 3 4 5 3
加工工序1：50 40 30 20 40
加工工序2：30 20 60 80 60 (单位：分)
完成先后两道工序总用了多少时间呢？
