分支限界法求解批处理任务调度问题

Question

有n个任务（编号为1～n）要在由两台机器M1和M2组成的流水线上完成加工。每个任务加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工任务i所需的时间分别为ai和bi（1≤i≤n），要求确定这n个任务的最优加工顺序，使得从第一个任务在机器M1上开始加工，到最后一个任务在机器M2上加工完成所需的时间最少。

Answer 1

这是一个经典的工厂调度问题，被称为"流水线调度问题"。可以使用贪心算法解决。

一种可行的做法是：将所有的任务在M1和M2上各处理一遍，得到在M1和M2上的处理时间分别为Ti和Ui，记录当前的加工顺序为S（即第i个任务是S[i]），则从M1到M2的总处理时间即为T1+T2，其中：

T1 = max(ai1, ai2+bi1, ai3+bi1+bi2, ..., ai(n-1)+bi1+bi2+...+bi(n-2), ain+bn-1+bn)

T2 = max(bn, bn-1+an, ..., b2+a3+...+an, b1+a2+...+an)

上述计算过程中，T1计算了从M1到M2完整处理整个任务序列（从左到右）所需的最短时间，T2计算了从M2到最后（从右到左）完成所有任务所需的最短时间。

现在的问题是确定任务的最优加工顺序。由于我们的目标是使总处理时间最小，那么可以考虑使用贪心策略，优先加工处理时间短的任务。

具体做法是：首先计算每个任务在M1和M2上分别所需的时间，即Ti = ai + ui（i=1, 2, ..., n），其中ui表示在它前面的任务在M1和M2上加工所需的时间。由于T1和T2都是最大值，因此可以考虑从Ti的最大值开始（即从处理时间最长的任务开始），将任务依次加入到加工序列S中。