流水车间调度是实际流水线生产过程的简化模型,涉及领域包含港口船舶、物流传输、车间生产等。合理的调度能够优化分配有限的资源、提高生产效率、降低交易风险等。文章以现有流水车间研究为基础,研究了多台流水机环境下最小化总误工损失的调度问题,设计了分支定界算法对其求解。流水车间指对于每个任务而言需按照“FIFO”原则在每台机器上加工,虽然可行算法能够满足机器及任务数量为大规模时的求解,却无法获得精确解。而本文设计的分支定界算法则可以保证在任务规模尽可能大的情况下,获得精确解。算法首先针对所研究问题,建立一棵搜索树,为避免全部枚举所带来的较高运算复杂性,算法利用上下界剪支来删减无用分支,并根据搜索树的特点设置全局上界、上界和局部下界来提升剪支效率。对于全局上界,采用遗传算法求得初始解,使用染色体编码方式,通过选择、交叉、变异产生下一代,最终通过限制迭代次数终止算法;而下界的计算上用到了DP与PMTN技术,在单机与有公共交付期情况下,分别运行多次DP与PMTN算法求解最小误工损失的最优序列,最后将两个下界的结果相结合得到最终下界MIX,从而提升了分支定界算法的剪支效果,使剪支过程更高效。同时对于上述多台机器模型中遗传算法求得的初始解与启发式规则得到的结果作比较,证实遗传算法对初始解的改进能力。最后,通过实验对比论证了本文给出的精确算法在求解所研究问题上的可行性及有效性。实验数据表明,通过B&B＿MIX删减搜索树结点的方式性能优于普通的分支定界树及B&B＿MDP、B&B＿PMTN两者中任意一个作为树的下界的方式;另外,初始解的改进上,遗传算法对LPT、TSPT的改善效果较弱,说明这两种规则作为问题的初始解较好,可进一步求解超大规模的问题实例。