张 源 陶翼飞 王加冕

昆明理工大学机电工程学院,昆明,650500

0 引言

混合流水车间调度问题[1](hybrid flow-shop scheduling problem，HFSP)是指在一定的时间内对加工工件的排序和设备的指派进行合理分配，使某些性能指标达到最优，已广泛应用于烟草加工、中草药生产、冶金等行业。HFSP结合了流水车间和并行机调度的特点，使其复杂程度更高、求解难度更大，且已被证明是一类经典的NP难题[2]。有效解决该类调度问题可以提高企业的生产效率和竞争力，因此研究HFSP具有重要的应用价值和意义。

目前，求解HFSP的算法主要包括遍历式算法[3]、构造型算法[4]和智能优化算法[5]，其中遍历式算法可以求解出该类问题的精确解，但计算速度较慢；构造型算法在求解该类问题时运算速度较快，但算法结构复杂且通常无法求解出全局最优解；智能优化算法具有严密的理论依据，能够在较短时间内求解出问题的最优解或理想解，已普遍应用于求解各种生产调度问题。差分进化(differential evolutionary，DE)算法[6]是在遗传算法进化思想的基础上所提出的一种智能优化算法，通过父代向量间的差分运算进行种群的迭代更新，主要用于求解多维空间整体最优解。目前已有许多研究采用DE算法求解生产调度问题。GODFREY等[7]针对流水车间调度问题，分别以最大完工时间、流水时间和最小化拖期为目标，采用DE算法进行求解并与采用遗传算法的结果进行比较，验证了DE算法具有较好的求解质量。PAN等[8]提出了一种求解作业车间最大完工时间的混合离散DE算法，该算法基于工件的排列顺序对个体进行编码，并应用基于工件排列的变异和交叉操作来生成新的候选解，通过已知基准实例的计算仿真和比较，证明了所提算法的优越性。……