研究了流水机环境下最小化总误工损失的调度问题。流水机调度指的是n个工件需要m台机器加工,每个工件需要m道工序,每道工序需要不同的机器;n个工件在m台机器上的加工顺序相同。工件的误工损失是与交付期有关的一种惩罚量,其数值正比于工件滞后于其交付期加工的部分。针对该问题不同模型,分别设计了分枝定界算法求解其小规模运算实例,以及遗传算法求解大规模实例。对于两台流水机模型,重新分析了2006年发表的分枝定界算法,利用反例法指出其下界设计中的错误;然后给出了新的计算下界方法,给出一个新的分枝定界算法。该算法利用遗传算法获得初始解,并利用上下界剪枝规则、节点间的支配规则去掉无效节点,缩小搜索规模。对于多台流水机模型,扩展了上述的遗传算法。根据问题特性,定义了染色体的编码方式、交叉和变异规则,以及算法终止条件。对于多台流水机模型,问题规模稍微增大,精确算法很难在满意的时间内找到最优解,甚至不可能找到最优解;因此,本文用遗传算法求所研究问题的近似解,并与其它的启发式算法的实验结果做比较,证明了遗传算法相比于其它启发式算法能更好的改善问题的初始解。实验数据表明,上述两个算法在处理小规模实例和中大规模实例过程中性能表现良好。带下界规则的分枝定界算法能有效地去除搜索树中的无效分枝,支配规则可以有效的去除无效节点,显著地提高了分支定界算法的搜索效率。遗传算法能够快速求解大规模算例,且性能远优于那些简单的启发式规则,能够为求解大规模问题算例时提供较好初始解。