简述分支限界法求解流水作业调度问题的思路，举例说明给出计算步骤

分支限界法是一种解决优化问题的算法，其中流水作业调度问题是一种典型的优化问题。其思路是通过不断分支扩展搜索树来找到最优解，同时使用限界函数来剪枝减少搜索的范围。

具体地，对于流水作业调度问题，我们要求解的是 n 个作业在 m 台机器上的调度问题，使得每个作业都被顺序地加工完成，并且最终的完成时间最短。这个问题可以表示成一个 n*m 的矩阵，其中每个元素表示对应的作业在对应的机器上的加工时间。

分支限界法的思路是将所有可能的调度方案组成的集合看成一棵搜索树，其中每个节点表示一个部分解（即已经安排好了一部分作业的调度方案），其子节点表示在当前部分解基础上，加工下一个作业的所有可能的调度方案。

对于每个节点，我们可以计算出一个上界值（也称为限界函数），表示在当前部分解的基础上，剩余作业的最短完成时间。通过比较当前节点的上界值和当前找到的最优解，可以决定是否需要继续搜索该节点的子节点，或者将该节点从搜索树中剪枝。

下面举一个例子来说明分支限界法求解流水作业调度问题的计算步骤：

假设有 3 个作业，分别需要在 2 台机器上加工，加工时间矩阵为：

| 2 | 1 |
|---|---|
| 3 | 2 |
| 1 | 4 |

首先，我们初始化搜索树，将根节点设为一个空的调度方案。

然后，我们计算根节点的上界值，即将所有作业按照加工时间从小到大排序后，依次加入到当前调度方案中，得到的最短完成时间。在这个例子中，排序后的作业顺序为 3-1-2，对应的最短完成时间为 8。

接下来，我们按照上述算法，依次生成根节点的子节点。首先，我们将作业 1 加入到第一台机器上，得到一个新的部分解。然后，我们计算该部分解的上界值，即将剩余的作业按照加工时间从小到大排序后，依次加入到当前调度方案中，得到的最短完成时间。在这个例子中，排序后的作业顺序为 2-3，对应的最短完成时间为 9。

接着，我们将作业 2 加入到第一台机器上，得到另一个新的部分解。同样地，我们计算该部分解的上界值，即将剩余的作业按照加工时间从小到大排序后，依次加入到当前调度方案中，得到的最短完成时间。在这个例子中，排序后的作业顺序为 3，对应的最短完成时间为 10。

最后，我们将作业 3 加入到第一台机器上，得到最后一个新的部分解。同样地，我们计算该部分解的上界值，即将剩余的作业按照加工时间从小到大排序后，依次加入到当前调度方案中，得到的最短完成时间。在这个例子中，排序后的作业顺序为 2，对应的最短完成时间为 11。

通过比较上述所有部分解的上界值和当前找到的最优解，可以确定下一步搜索的方向。在这个例子中，最短完成时间为 8，是由根节点得到的，因此我们只需要搜索根节点的子节点，即将作业 1 加入到第一台机器上的部分解和将作业 2 加入到第一台机器上的部分解。

通过不断重复上述过程，直到搜索完所有可能的调度方案，就可以得到最优解。