2.流水作业调度 n个作业f1，2，..，nì要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。 分析： 流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

这是一个经典的流水作业调度问题，可以使用动态规划算法来解决。

设f(i,j)表示前i个作业在机器M1上加工完成，前j个作业在机器M2上加工完成的最短时间。则有以下的状态转移方程：

f(i,j) = min{f(i-1,j), f(i,j-1)} + ai + bi

其中，f(i-1,j)表示前i-1个作业在机器M1上加工完成，前j个作业在机器M2上加工完成后，再将第i个作业加工在机器M1上；f(i,j-1)表示前i个作业在机器M1上加工完成，前j-1个作业在机器M2上加工完成后，再将第j个作业加工在机器M2上；ai和bi分别表示第i个作业在机器M1和M2上加工所需的时间。

最终的最优解为f(n,n)，即前n个作业在机器M1和M2上加工完成的最短时间。

需要注意的是，由于每个作业的加工顺序都是先在M1上加工，再在M2上加工，因此不能将作业i加工在机器M2上，也不能将作业j加工在机器M1上。