大规模Flow shop调度是一个重要的制造加工系统中的核心问题,广泛应用于工业环境中。大规模流水调度是很多实际流水线生产调度问题的简化模型,也是一类典型的NP完全问题,已被证明在多项式时间内得不到最优值。该问题也是生产管理中的核心问题,好的求解方法可以促进企业提高生产率。因此,对于该问题的研究从理论到实践都有重要意义。近年来,对于流水调度问题的求解主要有启发式算法和元启发式算法,但各有其不足之处:元启发式方法的运行时间长,可获得较好的解,但其解不稳定;启发式方法可在较短的时间内得到鲁棒性较强的解,但是极少获得较优的解。为了更好地解决大规模流水调度问题,提出两个相应的启发式算法,从实时性和优解性两个方面与现有的算法进行比较,大量试验结果表明该方法能有效求解所考虑的大规模流水调度问题。首先,针对以总完工时间为优化目标的大规模流水作业调度问题,提出基于局部插入和全局插入的双插入启发式算法DIH。DIH算法与目前求解流水调度问题最好的启发算法RZ、WY、FL在1500个实例上进行比较。试验表明,DIH算法具有最好的性能,并且能够满足大规模调度对于实时性和优解性的要求。其次,提出复合启发式算法CDIH求解最优化总完工时间的大规模流水调度问题。在CDIH算法中,将DIH算法的调度结果通过全局插入和工件交换操作进行二次改进。通过4000个不同规模实例将CDIH算法与目前最好的复合启发式算法IH7、FL-IH7在ARPD、STD、OPT和计算时间等参数方面进行比较,试验结果表明:在最好调度的获取能力、所得调度的平均质量及所得调度的稳定性方面,CDIH算法均是最优的。CDIH能够更有效地解决以总完工时间最小为目标的Flow Shop调度问题。