王 婷，毋 涛

(西安工程大学 计算机科学学院，陕西 西安 710048)

0 引 言

随着中国经济社会的发展，产品定制服务的出现，消费者个性化需求也日益凸显，有一部分制造型企业开始采用订单生产模式[1](make-to-order，MTO)，比如西装定制、船舶制造。

在MTO生产模式中,订单内不同的工件的交货期不同，而制造型企业通常都是配备固定的车间、机器和人员，订单调度决策往往受车间生产能力的制约。在这种情况下，这种决策往往会与实际生产有所偏差，造成计划外的生产成本(如加班、外包)和拖期罚金，导致企业信誉受损，客户满意度降低。

为提高订单交付的准时率,企业需要在有限产能下对订单生产作业进行合理的计划安排和调度，依据订单产品的要求交期及时交付产品，履行合约。研究基于流水线车间的订单调度问题可以有效提高企业的生产效率和竞争力，对于处于MTO生产模式的企业制定出合理有效的订单调度决策，及时交付作业具有重要的研究意义。

长期以来，混合流水车间调度问题[2](hybrid flow shop scheduling problem，HFSP)被证明是一个经典的NP难题。目前，求解HFSP的算法主要包括遍历式算法、构造型算法和智能化优化算法，其中遍历式算法可以求解出该类问题的精确解，但计算速度较慢；构造型算法在求解该类问题时运算速度较快，但算法结构复杂且通常无法求解出全局最优解[3]；优化算法有严格的理论基础，能在短时间内解决问题的最优或理想解。智能优化算法[4]主要有混合萤火虫算……