·1492 工程科学学报，第43卷，第11期 KEY WORDS hybrid flow shop;multi-objective;buffer equalization:multi-constraint;NSGA-III 考虑工件以批量形式运输、车间中各个工序 有限机器独立配置缓冲区混合流水车间调度问题 前后生产节拍不同等因素，在混合流水车间中建 的文献较少，本文将对带有限缓冲区的混合流水 立缓冲区是非常必要的.流水车间中(Flow shop, 车间调度问题进行研究，以最小化完工时间、最小 FS)的缓冲区一般有两种形式，加工工序间共享缓 化运载设备运输时间、最小化并行机前置缓冲区 冲区山和机器独立配置缓冲区冈，第一种类型常见 空间占用率均衡指数为目标，考虑运载设备运输 于物料搬运较为容易、加工形式单一的串型生产 能力限制、机器不确定性加工时间、缓冲区容积 线当中可而对于运输能力有限、车间布局不易更 有限等资源限制条件，建立模型，并采用NSGA- 改的混合流水车间，机器独立配置缓冲区更具备 Ⅱ与NSGA-II算法进行求解，对比不同算法在求 研究意义 解过程的差异.最后，将针对实际车间进行实例验 求解混合流水车间的调度问题已经被 证，并对产生的优化结果加以分析 Gupta证明是非确定性多项式(Non-deterministic 1 带有限缓冲区的混合流水车间建模 polynomial,,NP)难度问题，目前解决这类问题有适 用于低复杂度、小规模问题的精确计算心刀、启发 1.1问题描述 式方法⑧9以及当下被广泛使用的智能搜索算 混合流水车间生产加工阶段s=1~S,加工设 法o-1切，Smutnicki!较早的针对含有容量限制的 备k=1~N,每一台加工设备都配置了独立的前置 中间缓冲区的两机排列的混合流水车间，以最小 缓冲区和后置缓冲区，受到有限的车间空间和设 化完工时间为目标，采用了一种基于禁忌搜索的 备生产线布局的影响，除第一道加工工序的前置 近似算法：Nowickils采用禁忌算法，将其扩展为 缓冲区和最后一道加工工序的后置缓冲区视为容 每个加工工序中可以含有任意数量的机器； 量无限大，其他剩下所有的缓冲区均为容量有限 Qian等6针对有限缓冲区位于连续机器之间的流 的缓冲区，车间中运载设备i=1~Y用于工序间工 水车间调度问题，设计一种混合差分进化算法 件运输，每一个加工阶段中都包含着生产精度不 (HDE),并通过仿真实验验证算法的有效性；Wang 同、加工效率不等、工件适用情况存在差异的一 与Tangl7采用一种回溯启发式算法，针对加工阶 定数量的并行机，工件集O按照批次进行划分为A 段间有限等待时间的混合流水车间调度问题，以 个批次，0=1,2，…，a,…,A-1,A,工件总数量为J 最小化完工时间为目标进行求解同时验证了算法 假设：(1)所有工件的加工顺序一致，均要从第一加 的有效性 工工序开始，完成一个工序的加工任务后，进入下 遗传算法(Genetic algorithm,GA)已经广泛的 一个加工工序，直到完成最后一个加工工序的加 应用在车间调度问题上8-20，本文也拟采用遗 工任务：(2)其中缓冲区的容积可以进行调节，但 传算法进行求解.NSGA-I(Non-dominated sorting 会受到车间空间和天车运输距离的限制，且加工 genetic algorithm2,NSGA-Ⅱ)是由Deb等提出， 作业一旦开始，缓冲区容积就不能再更改：(3)所 且已经广泛应用在处理多目标混合流水车间调 有加工批次均为合理划分，既能满足天车运输能 度问题当中2-2的智能算法.NSGA-IⅢI(Non- 力的要求，同时也符合缓冲区容积要求：(4)不考 虑工件的换装时间，且同批次内工件之间无确定 dominated sorting genetic algorithm 3,NSGA-III) 先后加工顺序要求 在NSGA-I基础上提出的，与NSGA-I有着相 1.2模型建立 同的框架，但是在精英选择策略关于同一级非支 相关参数设计如表1. 配个体间的选择机制上，NSGA-IⅡ算法采用根据拥 车间资源约束条件如下： 挤度大小的方式进行个体选择，NSGA-II则是基 于参考点的方式，改进了NSGA-Ⅱ算法在处理三 Xs一s+Ii+ (X山+XkF/+XikB)=1,j 个及其以上目标时解在非支配层上分布不均匀、 k=1 (1) 易陷入局部最优的缺点 综上，现有的文献中多数都是假定车间中为 Xi.s-s+Ia≤1，Ys,i (2) 无限制缓冲区，或者为工序间共享缓冲区，研究带 a=lKEY WORDS    hybrid flow shop；multi-objective；buffer equalization；multi-constraint；NSGA-III 考虑工件以批量形式运输、车间中各个工序 前后生产节拍不同等因素，在混合流水车间中建 立缓冲区是非常必要的. 流水车间中（Flow shop, FS）的缓冲区一般有两种形式，加工工序间共享缓 冲区[1] 和机器独立配置缓冲区[2] ，第一种类型常见 于物料搬运较为容易、加工形式单一的串型生产 线当中[3] ，而对于运输能力有限、车间布局不易更 改的混合流水车间，机器独立配置缓冲区更具备 研究意义. 求 解 混 合 流 水 车 间 的 调 度 问 题 已 经 被 Gupta[4] 证明是非确定性多项式（Non-deterministic polynomial, NP）难度问题，目前解决这类问题有适 用于低复杂度、小规模问题的精确计算[5−7]、启发 式方法[8−9] 以及当下被广泛使用的智能搜索算 法[10−13] ，Smutnicki[14] 较早的针对含有容量限制的 中间缓冲区的两机排列的混合流水车间，以最小 化完工时间为目标，采用了一种基于禁忌搜索的 近似算法；Nowicki[15] 采用禁忌算法，将其扩展为 每 个 加 工 工 序 中 可 以 含 有 任 意 数 量 的 机 器 ； Qian 等[16] 针对有限缓冲区位于连续机器之间的流 水车间调度问题 ，设计一种混合差分进化算法 (HDE)，并通过仿真实验验证算法的有效性；Wang 与 Tang[17] 采用一种回溯启发式算法，针对加工阶 段间有限等待时间的混合流水车间调度问题，以 最小化完工时间为目标进行求解同时验证了算法 的有效性. 遗传算法（Genetic algorithm，GA）已经广泛的 应用在车间调度问题上[18−20] ，本文也拟采用遗 传算法进行求解. NSGA-II（Non-dominated sorting genetic algorithm 2，NSGA-II）是由 Deb 等[21] 提出， 且已经广泛应用在处理多目标混合流水车间调 度 问 题 当 中 [22−24] 的 智 能 算 法 . NSGA-III（ Non￾dominated sorting genetic algorithm 3， NSGA-III） 是 在 NSGA-II 基础上提出的[25] ，与 NSGA-II 有着相 同的框架，但是在精英选择策略关于同一级非支 配个体间的选择机制上，NSGA-II 算法采用根据拥 挤度大小的方式进行个体选择，NSGA-III 则是基 于参考点的方式，改进了 NSGA-II 算法在处理三 个及其以上目标时解在非支配层上分布不均匀、 易陷入局部最优的缺点. 综上，现有的文献中多数都是假定车间中为 无限制缓冲区，或者为工序间共享缓冲区，研究带 有限机器独立配置缓冲区混合流水车间调度问题 的文献较少，本文将对带有限缓冲区的混合流水 车间调度问题进行研究，以最小化完工时间、最小 化运载设备运输时间、最小化并行机前置缓冲区 空间占用率均衡指数为目标，考虑运载设备运输 能力限制、机器不确定性加工时间、缓冲区容积 有限等资源限制条件，建立模型，并采用 NSGA￾II 与 NSGA-III 算法进行求解，对比不同算法在求 解过程的差异. 最后，将针对实际车间进行实例验 证，并对产生的优化结果加以分析. 1    带有限缓冲区的混合流水车间建模 1.1    问题描述 k = 1 ∼ N i = 1 ∼ Y O = {1,2,··· ,a,··· ,A−1,A} 混合流水车间生产加工阶段 s=1～S，加工设 备 ，每一台加工设备都配置了独立的前置 缓冲区和后置缓冲区，受到有限的车间空间和设 备生产线布局的影响，除第一道加工工序的前置 缓冲区和最后一道加工工序的后置缓冲区视为容 量无限大，其他剩下所有的缓冲区均为容量有限 的缓冲区，车间中运载设备 用于工序间工 件运输，每一个加工阶段中都包含着生产精度不 同、加工效率不等、工件适用情况存在差异的一 定数量的并行机，工件集 O 按照批次进行划分为 A 个批次， ，工件总数量为 J. 假设：（1）所有工件的加工顺序一致，均要从第一加 工工序开始，完成一个工序的加工任务后，进入下 一个加工工序，直到完成最后一个加工工序的加 工任务；（2）其中缓冲区的容积可以进行调节，但 会受到车间空间和天车运输距离的限制，且加工 作业一旦开始，缓冲区容积就不能再更改：（3）所 有加工批次均为合理划分，既能满足天车运输能 力的要求，同时也符合缓冲区容积要求；（4）不考 虑工件的换装时间，且同批次内工件之间无确定 先后加工顺序要求. 1.2    模型建立 相关参数设计如表 1. 车间资源约束条件如下： ∑ Y i=1 Xi,s→(s+1), j,t + ∑ N k=1 (Xk, j,t + Xj,s,k,F,t + Xj,k,B,t) = 1,∀ j （1） ∑ A a=1 Xi,s→(s+1),a,t ⩽ 1,∀s,i （2） · 1492 · 工程科学学报，第 43 卷，第 11 期