工程科学学报 Chinese Journal of Engineering 带有限缓冲区的混合流水车间多目标调度 袁庆欣董绍华 Optimizing multi-objective scheduling problem of hybrid flow shop with limited buffer YUAN Qing-xin,DONG Shao-hua 引用本文： 袁庆欣，董绍华.带有限缓冲区的混合流水车间多目标调度.工程科学学报，2021,43(11)：1491-1498.doi: 10.13374j.issn2095-9389.2020.02.26.002 YUAN Qing-xin,DONG Shao-hua.Optimizing multi-objective scheduling problem of hybrid flow shop with limited buffer[J]. Chinese Journal of Engineering,.2021,43(11:1491-1498.doi:10.13374j.issn2095-9389.2020.02.26.002 在线阅读View online::htps:/doi.org/10.13374.issn2095-9389.2020.02.26.002 您可能感兴趣的其他文章 Articles you may be interested in 多目标多约束混合流水车间插单重调度问题研究 Research on rush order insertion rescheduling problem under hybrid flow shop with multi-objective and multi-constraint 工程科学学报.2019.41(11：1450 https:/doi.org10.13374.issn2095-9389.2018.11.27.002 基于多目标支持向量机的ADHD分类 ADHD classification based on a multi-objective support vector machine 工程科学学报.2020,42(4：441 https:/doi.org10.13374.issn2095-9389.2019.09.12.007 协同式多目标自适应巡航控制 Multi-objective adaptive cruise control (ACC)algorithm for cooperative ACC platooning 工程科学学报.2020,42(4：423 https::/1doi.org/10.13374.issn2095-9389.2019.05.21.002 固溶时效工艺对6016铝合金力学性能的影响及多目标优化 Effect of solution and aging processes on the mechanical properties of 6016 aluminum alloy and multi-objective optimization 工程科学学报.2017,391：75 https:ldoi.org/10.13374j.issn2095-9389.2017.01.010 基于粒子群算法的转炉用氧节能优化调度 Optimal scheduling of converter oxygen based on particle swarm optimization 工程科学学报.2021,43(2：279 https:/1doi.org/10.13374.issn2095-9389.2020.04.02.002 无数学模型的非线性约束单目标系统优化方法改进 Optimization method improvement for nonlinear constrained single objective system without mathematical models 工程科学学报.2018.40(11：1402htps:/doi.org/10.13374.issn2095-9389.2018.11.014
带有限缓冲区的混合流水车间多目标调度 袁庆欣 董绍华 Optimizing multi-objective scheduling problem of hybrid flow shop with limited buffer YUAN Qing-xin, DONG Shao-hua 引用本文: 袁庆欣, 董绍华. 带有限缓冲区的混合流水车间多目标调度[J]. 工程科学学报, 2021, 43(11): 1491-1498. doi: 10.13374/j.issn2095-9389.2020.02.26.002 YUAN Qing-xin, DONG Shao-hua. Optimizing multi-objective scheduling problem of hybrid flow shop with limited buffer[J]. Chinese Journal of Engineering, 2021, 43(11): 1491-1498. doi: 10.13374/j.issn2095-9389.2020.02.26.002 在线阅读 View online: https://doi.org/10.13374/j.issn2095-9389.2020.02.26.002 您可能感兴趣的其他文章 Articles you may be interested in 多目标多约束混合流水车间插单重调度问题研究 Research on rush order insertion rescheduling problem under hybrid flow shop with multi-objective and multi-constraint 工程科学学报. 2019, 41(11): 1450 https://doi.org/10.13374/j.issn2095-9389.2018.11.27.002 基于多目标支持向量机的ADHD分类 ADHD classification based on a multi-objective support vector machine 工程科学学报. 2020, 42(4): 441 https://doi.org/10.13374/j.issn2095-9389.2019.09.12.007 协同式多目标自适应巡航控制 Multi-objective adaptive cruise control (ACC) algorithm for cooperative ACC platooning 工程科学学报. 2020, 42(4): 423 https://doi.org/10.13374/j.issn2095-9389.2019.05.21.002 固溶时效工艺对6016铝合金力学性能的影响及多目标优化 Effect of solution and aging processes on the mechanical properties of 6016 aluminum alloy and multi-objective optimization 工程科学学报. 2017, 39(1): 75 https://doi.org/10.13374/j.issn2095-9389.2017.01.010 基于粒子群算法的转炉用氧节能优化调度 Optimal scheduling of converter oxygen based on particle swarm optimization 工程科学学报. 2021, 43(2): 279 https://doi.org/10.13374/j.issn2095-9389.2020.04.02.002 无数学模型的非线性约束单目标系统优化方法改进 Optimization method improvement for nonlinear constrained single objective system without mathematical models 工程科学学报. 2018, 40(11): 1402 https://doi.org/10.13374/j.issn2095-9389.2018.11.014
工程科学学报.第43卷，第11期：1491-1498.2021年11月 Chinese Journal of Engineering,Vol.43,No.11:1491-1498,November 2021 https://doi.org/10.13374/j.issn2095-9389.2020.02.26.002;http://cje.ustb.edu.cn 带有限缓冲区的混合流水车间多目标调度 袁庆欣四，董绍华 北京科技大学机械工程学院.北京100083 ☒通信作者，E-mail:15522625919@163.com 摘要研究对象是带有限缓冲区混合流水车间中的多目标调度问题.以各机器前置后置缓冲区容积有限、工件以批量形 式运输、运载设备的运载能力有限等作为资源限制因素，以最小化完工时间、最小化物料运输时间、最小化并行机前置缓冲 区空间占用率均衡指数为目标，建立调度模型.分别采用NSGA-Ⅱ、NSGA-Ⅲ算法求解该模型.并对比两者之间的差别：设置 不同的缓冲区容积.探究不同缓冲区容积对生产目标的影响.寻找最优缓冲区容积：建立不同模型.探究以最小化并行机前置 缓冲区空间占用率均衡指数为目标的意义，最后以某船用管类生产企业的实际生产案例作为对象，通过对比优化结果与实际 生产数据，验证了算法有效性. 关键词混合流水车间：多目标：缓冲区均衡：多约束：NSGA-Ⅲ 分类号U673.2 Optimizing multi-objective scheduling problem of hybrid flow shop with limited buffer YUAN Qing-xin,DONG Shao-hua School of Mechanical Engineering,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:15522625919@163.com ABSTRACT Buffer zones in a production company are set before and after each processing equipment based on various factors such as workshop space in the hybrid-flow workshop,transportation capacity of the carrying equipment,ease of handling of the machine, machine productivity at various stages,and production cycle time.The objective of this paper was to optimizing the multi-objective scheduling problem in hybrid flow shop with limited buffer.As there was limited space(capacity)at front and rear buffers of each machine,transportation of workpieces in batches,limited carrying capacity of carrier equipment,differences in workability between parallel machines,and process determination,etc.,were considered as resource limiting factors,and based upon these factors two- objective scheduling model was established with the goal of minimizing completion time and minimizing material transportation time. The two-objective scheduling model was added with minimization parallel machine front buffer space occupancy rate equilibrium index as a new goal,and established a three-objective scheduling model.In this article,NSGA-II and NSGA-III algorithms were used to solve the three-objective scheduling model,and the crossover and mutation parts of the algorithm were redesigned according to the model established.The actual production data of a marine pipe production enterprise was taken as an example and optimization results were compared with the actual production data.Thus the effectiveness of the algorithm was verified,and the difference between the two algorithms when processing the three-target scheduling model was compared,and it is concluded that NSGA-III has better convergence effect when processing the three-objective model.To explore the impact of different buffer volumes on production,target values under different buffer volumes were compared,and finally optimal buffer volume for each target was found out;then the two-objective model and the three-objective model were compared under different buffer volumes.The optimization results of these indicators prove the practical importance of adding the minimization of the parallel machine front buffer space occupancy rate balance index. 收稿日期：2020-02-26 基金项目：国家自然科学基金资助项目(71301008)
带有限缓冲区的混合流水车间多目标调度 袁庆欣苣，董绍华 北京科技大学机械工程学院，北京 100083 苣通信作者， E-mail：15522625919@163.com 摘 要 研究对象是带有限缓冲区混合流水车间中的多目标调度问题. 以各机器前置后置缓冲区容积有限、工件以批量形 式运输、运载设备的运载能力有限等作为资源限制因素，以最小化完工时间、最小化物料运输时间、最小化并行机前置缓冲 区空间占用率均衡指数为目标，建立调度模型. 分别采用 NSGA-II、NSGA-III 算法求解该模型，并对比两者之间的差别；设置 不同的缓冲区容积，探究不同缓冲区容积对生产目标的影响，寻找最优缓冲区容积；建立不同模型，探究以最小化并行机前置 缓冲区空间占用率均衡指数为目标的意义，最后以某船用管类生产企业的实际生产案例作为对象，通过对比优化结果与实际 生产数据，验证了算法有效性. 关键词 混合流水车间；多目标；缓冲区均衡；多约束；NSGA-III 分类号 U673.2 Optimizing multi-objective scheduling problem of hybrid flow shop with limited buffer YUAN Qing-xin苣 ，DONG Shao-hua School of Mechanical Engineering, University of Science and Technology Beijing, Beijing 100083, China 苣 Corresponding author, E-mail: 15522625919@163.com ABSTRACT Buffer zones in a production company are set before and after each processing equipment based on various factors such as workshop space in the hybrid-flow workshop, transportation capacity of the carrying equipment, ease of handling of the machine, machine productivity at various stages, and production cycle time. The objective of this paper was to optimizing the multi-objective scheduling problem in hybrid flow shop with limited buffer. As there was limited space (capacity) at front and rear buffers of each machine, transportation of workpieces in batches, limited carrying capacity of carrier equipment, differences in workability between parallel machines, and process determination, etc., were considered as resource limiting factors, and based upon these factors twoobjective scheduling model was established with the goal of minimizing completion time and minimizing material transportation time. The two-objective scheduling model was added with minimization parallel machine front buffer space occupancy rate equilibrium index as a new goal, and established a three-objective scheduling model. In this article, NSGA-II and NSGA-III algorithms were used to solve the three-objective scheduling model, and the crossover and mutation parts of the algorithm were redesigned according to the model established. The actual production data of a marine pipe production enterprise was taken as an example and optimization results were compared with the actual production data. Thus the effectiveness of the algorithm was verified, and the difference between the two algorithms when processing the three-target scheduling model was compared, and it is concluded that NSGA-III has better convergence effect when processing the three-objective model. To explore the impact of different buffer volumes on production, target values under different buffer volumes were compared, and finally optimal buffer volume for each target was found out; then the two-objective model and the three-objective model were compared under different buffer volumes. The optimization results of these indicators prove the practical importance of adding the minimization of the parallel machine front buffer space occupancy rate balance index. 收稿日期: 2020−02−26 基金项目: 国家自然科学基金资助项目（71301008） 工程科学学报，第 43 卷，第 11 期：1491−1498，2021 年 11 月 Chinese Journal of Engineering, Vol. 43, No. 11: 1491−1498, November 2021 https://doi.org/10.13374/j.issn2095-9389.2020.02.26.002; http://cje.ustb.edu.cn
·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=l
KEY 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（ Nondominated sorting genetic algorithm 3， NSGA-III） 是 在 NSGA-II 基础上提出的[25] ，与 NSGA-II 有着相 同的框架，但是在精英选择策略关于同一级非支 配个体间的选择机制上，NSGA-II 算法采用根据拥 挤度大小的方式进行个体选择，NSGA-III 则是基 于参考点的方式，改进了 NSGA-II 算法在处理三 个及其以上目标时解在非支配层上分布不均匀、 易陷入局部最优的缺点. 综上，现有的文献中多数都是假定车间中为 无限制缓冲区，或者为工序间共享缓冲区，研究带 有限机器独立配置缓冲区混合流水车间调度问题 的文献较少，本文将对带有限缓冲区的混合流水 车间调度问题进行研究，以最小化完工时间、最小 化运载设备运输时间、最小化并行机前置缓冲区 空间占用率均衡指数为目标，考虑运载设备运输 能力限制、机器不确定性加工时间、缓冲区容积 有限等资源限制条件，建立模型，并采用 NSGAII 与 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 期
袁庆欣等：带有限缓冲区的混合流水车间多目标调度 1493· 表1参数及变量设计 Table 1 Design of the parameters and decision variables Parameters Description c Capacity of the kth machine's front buffer in the stage s C Capacity of the kth machine's back buffer N Number of machines at the s processing stage 台 Total number of artifacts in batch a TCkJ Completion time of job j on the kth machine belong to sth stage Tis-(s+l)j Transportation completion time of ith transporter for transports jobj Tikj Starting time of job j that processed on the kth machine belong to sth stage 山 The processing time of jobjon the kth machine belong to sth stage 左-s+时 The transportation time of ith transporter for transports jobj Tis-(stij The leaving time of job j that leaves ith transporter Thk The idle time of the Ath machine belong to sth stage T The leaving time of job jthat leaves the kth machine belong to sth stages Tk8j The leaving time of job jthat leaves back buffer of the kth machine belong to sth stage Taak The leaving time of ath batch that leav ves the kth machine belong to sth stage Tis-(s+lk The arriving time of ith transporter that arrives the kth machine belong to sth stage 咀 The remaining volume of the back buffer of the kth machine belong to sth stage 生 The remaining volume of the front buffer of the Ath machine belong to sth stage T The last time the back buffer of the kth machine has enough room for job j Torlka The last time the front buffer of the th machine has enough room for batcha Tisk The moment that the back buffer of the kth machine has enough room for jobj Taak The moment that the front buffer of the kth machine has enough room for batch a t Production moment Xis-(s+D).j If job j is transported by transporter ith transporter at t,it is equal to 1,otherwise 0 XE加 If job j is processed on the kth machine at t,it is equal to 1,otherwise 0 XjskF If job j is in the front buffer of the kth machine belong to sth stage at t,it is equal to 1,otherwise 0 XiB」 If job j is in the back buffer of the kth machine at t,it is equal to 1,otherwise 0 Xi.s-(s+l)al If ath transported by ith transporter,it is equal to1,otherwise (3) TkB/=maxT-+lmt,Tdk小，，k,ijea,ac0 (10) x.crvnk Tis-(s+Dj=TskB.j+his-(D)j,Vi.jEO (11) (4) Ts-s+l=max(Ti.-s+lT+Dkd小.，i.kjea,ac0 (12) 2 (5) Ta=maxtT when V Ja.T=1 Vs.k (13) TSj=Tkj+Vs.k.jeO (6) TikpTsk.Bj≥0，sk,je0 (14) Tik=maxT-e+DTVs,.k,ije0,s≥1（7） 上述模型中，式(1)~(3)为机器能力、运载设 备运输能力约束，具体为一台机器一次只能加工 Tk=max(TC.T小.Ys,k,je0 (8) 一个工件，一台运载设备一次也只能运输一个批 TR max(TRl,when V >1.TRk=t.Vs.k.jeo 次的工件：式(4)~(5)为缓冲区容积限制；式(6)、 (9) 式(11)分别为加工时间约束和运输时间约束；式
∑ J j=1 Xk, j,t ⩽ 1,∀k （3） ∑ J j=1 Xj,s,k,F,t ⩽ C F s,k ,∀s, k （4） ∑ O j=1 Xj,k,B,t ⩽ C B k ,∀k （5） T C s,k, j = T s s,k, j +t p s,k, j ,∀s, k. j ∈ O （6） T s s,k, j = max{T l i,s→(s+1), j ,T i s,k };∀s, k,i, j ∈ O,s ⩾ 1 （7） T l s,k, j = max{T C s,k, j ,T B j,s,k },∀s, k, j ∈ O （8） T B j,s,k = max{T B j,s,k },when V B s,k ⩾ 1,T B j,s,k = t,∀s, k, j ∈ O （9） T l s,k,B, j = max{T a i,s→(s+1),msk ,T l a,s,k },∀s, k,i, j ∈ a,a ⊆ O （10） Ti,s→(s+1), j = T l s,k,B, j +ti,s→(s+1), j ,∀i, j ∈ O （11） T l i,s→(s+1), j =max{Ti,s→(s+1), j ,T F (s+1),k,a },∀s,i, k, j∈a,a⊆O （12） T F s,k,a = max{T B a,s,k },when V F s,k ⩾ Ja,T B a,s,k = t,∀s, k （13） T s s,k, j ,T l s,k,B, j ⩾ 0,∀s, k, j ∈ O （14） 上述模型中，式（1）～（3）为机器能力、运载设 备运输能力约束，具体为一台机器一次只能加工 一个工件，一台运载设备一次也只能运输一个批 次的工件；式（4）～（5）为缓冲区容积限制；式（6）、 式（11）分别为加工时间约束和运输时间约束；式 表 1 参数及变量设计 Table 1 Design of the parameters and decision variables Parameters Description C F s,k Capacity of the kth machine’s front buffer in the stage s C B k Capacity of the kth machine’s back buffer Ns Number of machines at the s processing stage Ja Total number of artifacts in batch a T C s,k, j Completion time of job j on the kth machine belong to sth stage Ti,s→(s+1), j Transportation completion time of ith transporter for transports job j T s s,k, j Starting time of job j that processed on the kth machine belong to sth stage t p s,k, j The processing time of job j on the kth machine belong to sth stage ti,s→(s+1), j The transportation time of ith transporter for transports job j T l i,s→(s+1), j The leaving time of job j that leaves ith transporter T i s,k The idle time of the kth machine belong to sth stage T l s,k, j The leaving time of job j that leaves the kth machine belong to sth stage s T l s,k,B, j The leaving time of job j that leaves back buffer of the kth machine belong to sth stage T l a,s,k The leaving time of ath batch that leaves the kth machine belong to sth stage T a i,s→(s+1),k The arriving time of ith transporter that arrives the kth machine belong to sth stage V B s,k The remaining volume of the back buffer of the kth machine belong to sth stage V F s,k The remaining volume of the front buffer of the kth machine belong to sth stage T B j,s,k The last time the back buffer of the kth machine has enough room for job j T F (s+1),k,a The last time the front buffer of the kth machine has enough room for batch a T B j,s,k The moment that the back buffer of the kth machine has enough room for job j T F a,s,k The moment that the front buffer of the kth machine has enough room for batch a t Production moment Xi,s→(s+1), j,t If job j is transported by transporter ith transporter at t, it is equal to 1, otherwise 0 Xk, j,t If job j is processed on the kth machine at t, it is equal to 1, otherwise 0 Xj,s,k,F,t If job j is in the front buffer of the kth machine belong to sth stage at t, it is equal to 1, otherwise 0 Xj,k,B,t If job j is in the back buffer of the kth machine at t, it is equal to 1,otherwise 0 Xi,s→(s+1),a,t If ath transported by ith transporter t, it is equal to 1, otherwise 0 袁庆欣等： 带有限缓冲区的混合流水车间多目标调度 · 1493 ·
1494 工程科学学报.第43卷第11期 (7)~(10)和式(12)~（13)为车间工艺约束；式 Ns (14)为加工时间、起运时间均大于零. (Ps k-P 目标函数如下： f=min (19) 考虑车间工作效率和车间内相关运营成本， 将最小化完工时间和最小化运载设备运输时间作 为本文研究的两个目标，建立两目标带有限缓冲 2带有限缓冲区的混合流水车间调度问题 区的混合流水车间调度模型，记为模型1，如式 (15)和式(16)所示 针对所建立的调度模型，分别采用NSGA-Ⅱ， NSGA-I算法对模型进行求解，算法框架与两算 i=min(max级l (15) 法不同的个体选择方式详见文献[25).本文中由于 =m22i.w-ra） 各机器配置了容积有限的缓冲区，增加了工序与工 (16) 序之间的关联性，初始种群的生成方式为随机生 i=l a=1 由于缓冲区容积有限，在一些未考虑工件占 成，终止准则为达到预定的终止时间，适应度为个体 用缓冲区空间均衡的排产方案中，会导致部分缓 的目标值，基因编码、交叉变异的具体设计如下， 2.1基因编码 冲区出现“拥堵”的现象，即缓冲区空间被工件占 满，导致上一工序加工完的工件无法进入到下一 本文中建立的模型涉及工件排序和并行机选 工序，而停留在上一工序的缓冲区和机器中，增加 择两部分，在编码方式上采用了双层编码的方式， 了等待时间.本文中以缓冲区占用率来衡量加工 第1层为工件码，按照工艺顺序划分为多个加工 阶段，每个基因位中的数字代表工件的批次编号； 过程中各缓冲区占用情况，以并行机前置缓冲区 占用率均衡作为第3个目标，建立3目标带有限缓 第2层为机器码，对应第一层中的工件所选择的 机器，每个基因位中的数字代表该批次工件在该 冲区的混合流水车间调度模型，记为模型2，并行 阶段可选机器集中所选择的机器索引号，若2个 机前置缓冲区占用率均衡指数如式(19)所示， 不同批次的工件在某阶段选择同一台机器，则以 Pk为机器缓冲区占用率，P,为第s工序并行机中 工件码中出现的先后顺序确定排产顺序，同时基 的各个机器的平均占用率 因的编码顺序满足工序间关联性的要求.例：如 图1所示[2,1,3,5,4,6,3,2,4,5,1,6,4,6,3,5,2,1,1,2,2,1,2， 3,2,1,2,3,2,1,2,3,3,1,1,2]为一个3加工阶段6批次 .Vs.k (17) 工件模型的其中1条染色体，[2,1,3,5,4,6,3,2,4,5,1,6,4， 6,3,5,2,1]是工件码部分，[1,2,2,1,2,3,2,1,2,3,2,1,2,3,3,1， 1,2]是机器码部分，工件码与机器码为一一对应关系. P:= 既包含全部加工阶段与全部工件编号的工件码同时 18) 也有对应机器码的染色体为一个完整的调度方案 (a) (b) Workcode Machine code Workcode 2 13 5 4 63 2 4 5 16 653024064523D30233010210 214351611325164221331221①1T1① Machine After POX crossover code 022023202320 c 420356132564002331T02 Genes adjust to meet production process requirements 图1编码示意图(a)与交叉示意图(b) Fig.1 Coding diagram (a)and cross diagram(b) 2.2交叉与变异 父代中工件分配到机器的机器码部分，可以保证 采用基于工序编码的交叉算子(Precedence 满足新产生的子代符合生产工艺的约束，同时满 operation crossover,,POX)所生成的新基因，保留了 足本文中对工序间关联性的要求.具体操作如图1
（7）～（10）和式（12）～（13）为车间工艺约束；式 （14）为加工时间、起运时间均大于零. 目标函数如下： 考虑车间工作效率和车间内相关运营成本， 将最小化完工时间和最小化运载设备运输时间作 为本文研究的两个目标，建立两目标带有限缓冲 区的混合流水车间调度模型，记为模型 1，如式 （15）和式（16）所示. f1 = min{maxt C s,k, j } （15） f2 = min∑ Y i=1 ∑ A a=1 (T l i,s→(s+1), j −T l s,k,B, j ) （16） Ps,k Ps 由于缓冲区容积有限，在一些未考虑工件占 用缓冲区空间均衡的排产方案中，会导致部分缓 冲区出现“拥堵”的现象，即缓冲区空间被工件占 满，导致上一工序加工完的工件无法进入到下一 工序，而停留在上一工序的缓冲区和机器中，增加 了等待时间. 本文中以缓冲区占用率来衡量加工 过程中各缓冲区占用情况，以并行机前置缓冲区 占用率均衡作为第 3 个目标，建立 3 目标带有限缓 冲区的混合流水车间调度模型，记为模型 2，并行 机前置缓冲区占用率均衡指数如式（ 19）所示 ， 为机器缓冲区占用率， 为第 s 工序并行机中 的各个机器的平均占用率. Ps,k = w ∑ J j=1 Xj,s,k,F,t C F s,k ,∀s, k （17） Ps = ∑ Ns k=1 Ps,k Ns ,∀s （18） f3 = min ∑ S s=1 ∑ Ns k=1 (Ps,k − Ps) 2 Ns −1 （19） 2 带有限缓冲区的混合流水车间调度问题 针对所建立的调度模型，分别采用 NSGA-II， NSGA-III 算法对模型进行求解，算法框架与两算 法不同的个体选择方式详见文献 [25]. 本文中由于 各机器配置了容积有限的缓冲区，增加了工序与工 序之间的关联性，初始种群的生成方式为随机生 成，终止准则为达到预定的终止时间，适应度为个体 的目标值，基因编码、交叉变异的具体设计如下. 2.1 基因编码 本文中建立的模型涉及工件排序和并行机选 择两部分，在编码方式上采用了双层编码的方式， 第 1 层为工件码，按照工艺顺序划分为多个加工 阶段，每个基因位中的数字代表工件的批次编号； 第 2 层为机器码，对应第一层中的工件所选择的 机器，每个基因位中的数字代表该批次工件在该 阶段可选机器集中所选择的机器索引号，若 2 个 不同批次的工件在某阶段选择同一台机器，则以 工件码中出现的先后顺序确定排产顺序，同时基 因的编码顺序满足工序间关联性的要求. 例：如 图 1 所 示 [2,1,3,5,4,6,3,2,4,5,1,6,4,6,3,5,2,1,1,2,2,1,2, 3,2,1,2,3,2,1,2,3,3,1,1,2] 为一个 3 加工阶段 6 批次 工件模型的其中 1 条染色体，[2,1,3,5,4,6,3,2,4,5,1,6,4, 6,3,5,2,1] 是工件码部分，[1,2,2,1,2,3,2,1,2,3,2,1,2,3,3,1, 1,2] 是机器码部分，工件码与机器码为一一对应关系， 既包含全部加工阶段与全部工件编号的工件码同时 也有对应机器码的染色体为一个完整的调度方案. Workcode 2 1 3 5 4 6 3 2 4 5 1 6 6 5 3 1 2 4 1 6 4 5 2 3 1 3 1 2 3 3 1 1 1 2 1 1 2 1 4 3 5 6 1 3 2 5 6 4 2 2 1 3 3 2 2 1 1 1 1 1 4 p1 p2 c 2 1 3 5 6 1 3 2 5 6 4 1 3 1 2 3 3 1 1 1 2 1 1 1 2 2 1 2 3 2 1 2 3 2 1 Machine code Workcode (a) (b) Machine code After POX crossover Genes adjust to meet production process requirements 图 1 编码示意图（a）与交叉示意图（b） Fig.1 Coding diagram (a) and cross diagram (b) 2.2 交叉与变异 采用基于工序编码的交叉算子 (Precedence operation crossover，POX) 所生成的新基因，保留了 父代中工件分配到机器的机器码部分，可以保证 满足新产生的子代符合生产工艺的约束，同时满 足本文中对工序间关联性的要求. 具体操作如图 1 · 1494 · 工程科学学报，第 43 卷，第 11 期
袁庆欣等：带有限缓冲区的混合流水车间多目标调度 ·1495. 中示例所示，p1、p2是随机选择的两个父代个体， 3实例验证 在工件码部分随机生成交叉点，并首先在该部分 本文以某船用管类生产企业为研究对象，对 进行交叉，保留两个父代个体中保持关联性的相 其生产加工车间进行考虑缓冲区容积有限的混合 关基因，随后机器码部分对应工件码相关部分的 流水车间多目标优化调度的相关研究.其车间生 交叉方式进行交叉，对其中不符合工艺要求的基 产布局图如图2所示，车间被分为2跨4区，其中 因调整方式为，在满足工艺要求的基因组合中随 共有6个加工工序，工件在各个加工工序间通过 机选择，保证种群的多样性，最终生成子代c. 天车进行运输，每道工序都包含数量不等，加工精 多点变异是遗传算法中常见的变异方式，本 度、工作效率、工件适用情况不同的并行机，每台 文中基因变异主要针对机器码部分，根据变异率 机器都配置了独立的前置后置缓冲区，该车间可 随机选取个体进行变异，为保证个体的多样性，变 以认为是一个带有限缓冲区的混合流水车间.车 异过程为全随机变异方式 间生产工件信息如表2所示. Cutting1(2) Bending6(10)21 Fully- ◆Bending710) 26 Spot- Polishing20 welding16(15) welding18(30) 17 225) Cutting2(2) Bending14(0)0 Areal Area3 Area2 Area4 20 Bending8(6) Cutting3(1.5) 17 Bending9(6) 13 Pumping Bending10(6) Spot- Fully- Cutting4(1.5) 4Polishing21 welding17(15) welding19(30) (2.25 Bending11(2) 15 0 Bending13(2) Cutting5(1.5) X:Transportation time Crane 图2生产车间布局图 Fig.2 Production workshop layout 表2工件编号以及对应各阶段机器适用状况统计表 3目标优化问题时的区别；(2)通过改变缓冲区的 Table 2 Workpiece number and statistics of applicable conditions of the 容积，比较不同缓冲区容积时，模型2中3个目标 machine at each stage 值的变化；(3)采用NSGA-IⅢ处理模型1，统计 Job Cutting Spot-Fully- Bending Polishing Pumping number welding welding 3个指标值并与模型2的3个目标值进行对比分 1 [1,2] [6,7刀[16,17刀[1819] [20,21] [22] 析.所处理订单为企业实际订单，订单中将工件划 [3,45] [8) [16,17刀[18,19][20,21] [22 分为6个批次，批次1到批次6在各个阶段的机器 3 [3,4,5] [9] [1617118,19120,21] [22] 适用情况分别对应表2中工件编号，每个批次的 4 3,4,5][10] [16,17[18,1920,21][22] 批量都是8 5 [3,4,5][11,12][16,17][18,19][20,21][22] 实验一：分别采用NSGA-Ⅱ与NSGA-II解决 6[3,4,5[13][16,17[18,19[20,21][22 3目标带有限缓冲区的混合流水车间调度模型， 共2组实验，每组实验进行10次，2个算法均设置 现拟设计3个实验，(1)以该车间为研究基础， 为初始种群数量为500，交叉率为0.8，变异率为 分别采用NSGA-Ⅱ与NSGA-II处理多目标车间调 0.2,算法迭代10次即完成10次交叉变异之后达 度问题，验证算法的有效性，探究2个算法处理 到终止条件
中示例所示， p1、p2 是随机选择的两个父代个体， 在工件码部分随机生成交叉点，并首先在该部分 进行交叉，保留两个父代个体中保持关联性的相 关基因，随后机器码部分对应工件码相关部分的 交叉方式进行交叉，对其中不符合工艺要求的基 因调整方式为，在满足工艺要求的基因组合中随 机选择，保证种群的多样性，最终生成子代 c. 多点变异是遗传算法中常见的变异方式，本 文中基因变异主要针对机器码部分，根据变异率 随机选取个体进行变异，为保证个体的多样性，变 异过程为全随机变异方式. 3 实例验证 本文以某船用管类生产企业为研究对象，对 其生产加工车间进行考虑缓冲区容积有限的混合 流水车间多目标优化调度的相关研究. 其车间生 产布局图如图 2 所示，车间被分为 2 跨 4 区，其中 共有 6 个加工工序，工件在各个加工工序间通过 天车进行运输，每道工序都包含数量不等，加工精 度、工作效率、工件适用情况不同的并行机，每台 机器都配置了独立的前置后置缓冲区，该车间可 以认为是一个带有限缓冲区的混合流水车间. 车 间生产工件信息如表 2 所示. Cutting1(2) Bending6(10) Spotwelding16(15) Fullywelding18(30) Polishing20 Bending7(10) (2.25) Bending14(0) Bending8(6) Bending9(6) Bending10(6) Bending11(2) Bending12(2) Bending13(2) Bending14(0) 9 4 14 8 21 0 0 17 26 21 28 23 20 24 22 26 28 X X: Transportation time Crane 20 0 0 18 14 16 26 13 14 15 11 8 8 10 19 19 19 6 3 3 5 4 9 7 13 16 17 20 4 2 Cutting2(2) Cutting3(1.5) Cutting4(1.5) Cutting5(1.5) Area1 Area2 Area3 Pumping 7 4 9 Spotwelding17(15) Fullywelding19(30) Polishing21 (2.25) 7 4 9 Area4 图 2 生产车间布局图 Fig.2 Production workshop layout 表 2 工件编号以及对应各阶段机器适用状况统计表 Table 2 Workpiece number and statistics of applicable conditions of the machine at each stage Job number Cutting Bending Spotwelding Fullywelding Polishing Pumping 1 [1,2] [6,7] [16,17] [18,19] [20,21] [22] 2 [3,4,5] [8] [16,17] [18,19] [20,21] [22] 3 [3,4,5] [9] [16,17] [18,19] [20,21] [22] 4 [3,4,5] [10] [16,17] [18,19] [20,21] [22] 5 [3,4,5] [11,12] [16,17] [18,19] [20,21] [22] 6 [3,4,5] [13] [16,17] [18,19] [20,21] [22] 现拟设计 3 个实验，（1）以该车间为研究基础， 分别采用 NSGA-II 与 NSGA-III 处理多目标车间调 度问题，验证算法的有效性，探究 2 个算法处理 3 目标优化问题时的区别；（2）通过改变缓冲区的 容积，比较不同缓冲区容积时，模型 2 中 3 个目标 值的变化 ； （ 3） 采 用 NSGA-III 处理模 型 1， 统 计 3 个指标值并与模型 2 的 3 个目标值进行对比分 析. 所处理订单为企业实际订单，订单中将工件划 分为 6 个批次，批次 1 到批次 6 在各个阶段的机器 适用情况分别对应表 2 中工件编号，每个批次的 批量都是 8. 实验一：分别采用 NSGA-II 与 NSGA-III 解决 3 目标带有限缓冲区的混合流水车间调度模型， 共 2 组实验，每组实验进行 10 次，2 个算法均设置 为初始种群数量为 500，交叉率为 0.8，变异率为 0.2，算法迭代 10 次即完成 10 次交叉变异之后达 到终止条件. 袁庆欣等： 带有限缓冲区的混合流水车间多目标调度 · 1495 ·
.1496 工程科学学报，第43卷，第11期 图3为优化的结果，通过结果可知，在处理3目标 处理该模型时一级个体（最优解）的个数，通过对比可知 问题时，NSGA-II的收敛性要明显好于NSGA-Ⅱ， 在处理3目标带有限缓冲区的混合流水车间调度模型 图4中为分别统计10次NSGA-IⅡ与NSGA-II算法 时，NSGA-Ⅱ的一级个体更多，也说明收敛效果更好 3.0 2.5 (a) (b) 20 20 1.5 0 1.0 0.5 05 708 808 600 700 700 Transportation time/min 500 650 600 400 550 Makespan/min Transportation 600 650 400 600 550 300500 ime/min 200500 Makespan/min Population Pareto optimaltiy 图3NSGA-I(a)与NSGA-I(b)优化结果图 Fig.3 NSGA-II (a)and NSGA-III (b)optimization results 40 NSGA-II ■NSGA-I 通过该实验结果可知，缓冲区的容积逐渐变 Pareto 5302520 大，工序间独立性增强，运输时间与缓冲区占用率 均衡指数明显下降，其中缓冲区容积增大至14 5 后，运输时间变化开始趋于稳定，不再有明显的下 0 降，缓冲区占用率均衡指数在缓冲区容积增大至 10后，下降速度放缓，增大至20后再次放缓，但整 4 56 9 10 Experiments 体上仍继续下降，完工时间则基本保持不变 图4NSGA-I与NSGA-IⅢ一级个体数量对比图 实验结果分析如下.缓冲区容积较小则加工 Fig.4 Comparison of the number of NSGA-II and NSGA-III individuals 过程中发生“拥堵”的概率会增大，从而会延长工 件在天车上的滞留时间，致使运输时间增多：在同 实验二：为更贴近车间实际情况，除第一阶段 一缓冲区中，缓冲区中相同工件数量时，缓冲区容 机器的前置缓冲区和最后一阶段的后置缓冲区， 积大的缓冲区空间占用率低，使得缓冲区均衡指 其余各个机器的前置后置缓冲区容积均相等且统 数下降，同时随着缓冲区容积增大，工序间独立性 一变化，以缓冲区可容纳工件数量作为描述缓冲 增强，可选择加工方案增多，其中可使缓冲区占用 区容积的指标，缓冲区可调整的最小容量为订单 率更均衡的方案数量也会增加，以上两点都是导 中单个批次最大工件数，当前订单中为8，逐步增 致缓冲区占用率均衡指数下降的原因；完工时间 加缓冲区容量至50，对比不同缓冲区容积下，3个 不受缓冲区容积影响 目标值的变化，如图5所示 实验三：使用NSGA-II处理模型1，统计3个 550 指标值情况，与实验二中统计模型2的3个目标值 500 Completion time 情况对比，探究模型1与模型2在不同缓冲区容积 450 Transportation time 8000 400 下3个指标值的区别，如图6所示 里350 Buffer equilibrium index 300 4000 通过实验结果可知，模型1与模型2完工时间 250 2000 基本相同.且随着缓冲区容积改变，完工时间基本 200 5 10 15 2025303540 4550 无变化，在缓冲区容积较小时，模型1的运输时间 Buffer volume 要小于模型2的运输时间，但缓冲区均衡指数较 图5优化3目标有限缓冲区的混合流水车间调度模型三指标统计 高，说明在生产过程中出现了缓冲区空间占用率 结果 Fig.5 Three statistical results of hybrid flow shop scheduling model 不均衡和机器负载不均衡的情况，缓冲区容积增 with optimized three-object limited buffer zone 大后，两模型的运输时间指标与缓冲区占用率均
图 3 为优化的结果，通过结果可知，在处理 3 目标 问题时 ，NSGA-III 的收敛性要明显好于 NSGA-II， 图 4 中为分别统计 10 次 NSGA-II 与 NSGA-III 算法 处理该模型时一级个体（最优解）的个数，通过对比可知 在处理 3 目标带有限缓冲区的混合流水车间调度模型 时，NSGA-III 的一级个体更多，也说明收敛效果更好. 3.0 2.5 2.0 1.5 1.0 0.5 0 700 Buffer equalization/10 Transportation time/min Makespan/min 600 500 400 300 500 600 700 550 650 (a) 2.5 2.0 1.5 1.0 0.5 0 800 Buffer equalization/10 Transportation time/min Makespan/min 600 400 200 500 600 700 550 650 (b) Population Pareto optimaltiy 图 3 NSGA-II（a）与 NSGA-III（b）优化结果图 Fig.3 NSGA-II (a) and NSGA-III (b) optimization results 40 35 30 25 20 15 10 5 0 1 2 3 4 5 6 7 8 9 10 Number of Pareto frontier individuals Experiments NSGA-Ⅲ NSGA-Ⅲ algorithm Pareto front number changes NSGA-Ⅱ algorithm Pareto front number changes Average number of NSGA-Ⅲ NSGA-Ⅱ NSGA-Ⅱ 图 4 NSGA-II 与 NSGA-III 一级个体数量对比图 Fig.4 Comparison of the number of NSGA-II and NSGA-III individuals 实验二：为更贴近车间实际情况，除第一阶段 机器的前置缓冲区和最后一阶段的后置缓冲区， 其余各个机器的前置后置缓冲区容积均相等且统 一变化，以缓冲区可容纳工件数量作为描述缓冲 区容积的指标，缓冲区可调整的最小容量为订单 中单个批次最大工件数，当前订单中为 8，逐步增 加缓冲区容量至 50，对比不同缓冲区容积下，3 个 目标值的变化，如图 5 所示. 550 500 450 400 350 300 250 200 5 10 15 20 Buffer volume Completion time Transportation time Buffer equilibrium index Buffer equilibrium index Time/min 25 30 35 50 40 45 12000 10000 8000 6000 4000 2000 0 图 5 优化 3 目标有限缓冲区的混合流水车间调度模型三指标统计 结果 Fig.5 Three statistical results of hybrid flow shop scheduling model with optimized three-object limited buffer zone 通过该实验结果可知，缓冲区的容积逐渐变 大，工序间独立性增强，运输时间与缓冲区占用率 均衡指数明显下降，其中缓冲区容积增大至 14 后，运输时间变化开始趋于稳定，不再有明显的下 降，缓冲区占用率均衡指数在缓冲区容积增大至 10 后，下降速度放缓，增大至 20 后再次放缓，但整 体上仍继续下降，完工时间则基本保持不变. 实验结果分析如下. 缓冲区容积较小则加工 过程中发生“拥堵”的概率会增大，从而会延长工 件在天车上的滞留时间，致使运输时间增多；在同 一缓冲区中，缓冲区中相同工件数量时，缓冲区容 积大的缓冲区空间占用率低，使得缓冲区均衡指 数下降，同时随着缓冲区容积增大，工序间独立性 增强，可选择加工方案增多，其中可使缓冲区占用 率更均衡的方案数量也会增加，以上两点都是导 致缓冲区占用率均衡指数下降的原因；完工时间 不受缓冲区容积影响. 实验三：使用 NSGA-III 处理模型 1，统计 3 个 指标值情况，与实验二中统计模型 2 的 3 个目标值 情况对比，探究模型 1 与模型 2 在不同缓冲区容积 下 3 个指标值的区别，如图 6 所示. 通过实验结果可知，模型 1 与模型 2 完工时间 基本相同，且随着缓冲区容积改变，完工时间基本 无变化，在缓冲区容积较小时，模型 1 的运输时间 要小于模型 2 的运输时间，但缓冲区均衡指数较 高，说明在生产过程中出现了缓冲区空间占用率 不均衡和机器负载不均衡的情况，缓冲区容积增 大后，两模型的运输时间指标与缓冲区占用率均 · 1496 · 工程科学学报，第 43 卷，第 11 期
袁庆欣等：带有限缓冲区的混合流水车间多目标调度 1497 600 500 580 (a) 450 四 560 400 540 350 e 300 480 250 460 200 440 420 50 400 510 1520253035404550 100101520n253035404550 Buffer volume Buffer volume 3.0 (c) S25 -Model 2 -Model 1 1.5 1.0 V 0 101520.253035404550 Buffer volume 图6模型1与模型2对比.(a)完工时间：(b)运输时间：(c)缓神区均衡指数 Fig.6 Comparison of model I and model 2:(a)completion time;(b)transportation time;(c)buffer equilibrium index 衡指数分别趋于相等 [2]Huang J Z,Li A P,Liu X M,et al.Optimal design of production line layout considering buffer allocation.J Tongji Univ Nat Sci, 4结论 2015,43(7):1075 (I)同时采用NSGA-II与NSGA-I两个算法 (黄君政，李爱平，刘雪梅，等.考虑缓冲区配置的生产线布局优 化设计.同济大学学报（自然科学版），2015,43(7)：1075) 对3目标调度模型进行优化，得出在处理3个目标 [3] Papadopoulos H T,Vidalis M I.A heuristic algorithm for the 的问题时，NSGA-I在收敛性和生成一级个体数 buffer allocation in unreliable unbalanced production lines 量上要好于NSGA-Ⅱ的结论 Comput Ind Eng,2001,41(3):261 (2)求解3目标带有限缓冲区的混合流水车间 [4] Gupta J N D.Two-stage,hybrid flowshop scheduling problem.J 调度模型，不断增加缓冲区容积，得出缓冲区容积 0 per Res Soc,.1988,39(4:359 越大，完工时间基本不变，运输时间越短和缓冲区 5 Djellab H,Djellab K.Preemptive hybrid flowshop scheduling 占用率更均衡的结论 problem of interval orders.EurJOper Res,002,137(1):37 (3)若不考虑缓冲区占用率均衡，在缓冲区容 [6] Bolat A,Al-Harkan I,Al-Harbi B.Flow-shop scheduling for three 积较小时模型1可以得到与模型2相比更小的运 serial stations with the last two duplicate.Comput Oper Res,2005, 32(3):647 输时间，但会导致缓冲区占用率均衡性较差，缓冲 [7] Guirchoun S,Martineau P,Billaut J C.Total completion time 区容积增大后，模型1的缓冲区占用率均衡性逐 minimization in a computer system with a server and two parallel 渐得到改善，则得出在缓冲区容积较小时，考虑缓 processors.Comput Oper Res,2005,32(3):599 冲区占用率均衡更具备研究意义 [8] Brah S A.A comparative analysis of due date based job sequencing rules in a flow shop with multiple processors.Prod 参考文献 P1 an Control,1996,7(4):362 [1]Khosla I.The scheduling problem where multiple machines [9]Brah S A,Wheeler G E.Comparison of scheduling rules in a flow compete for a common local buffer.Eur J Oper Res,1995,84(2): shop with multiple processors:A simulation.Simulation,1998, 330 71(5):302
衡指数分别趋于相等. 4 结论 （1）同时采用 NSGA-II 与 NSGA-III 两个算法 对 3 目标调度模型进行优化，得出在处理 3 个目标 的问题时，NSGA-III 在收敛性和生成一级个体数 量上要好于 NSGA-II 的结论. （2）求解 3 目标带有限缓冲区的混合流水车间 调度模型，不断增加缓冲区容积，得出缓冲区容积 越大，完工时间基本不变，运输时间越短和缓冲区 占用率更均衡的结论. （3）若不考虑缓冲区占用率均衡，在缓冲区容 积较小时模型 1 可以得到与模型 2 相比更小的运 输时间，但会导致缓冲区占用率均衡性较差，缓冲 区容积增大后，模型 1 的缓冲区占用率均衡性逐 渐得到改善，则得出在缓冲区容积较小时，考虑缓 冲区占用率均衡更具备研究意义. 参 考 文 献 Khosla I. The scheduling problem where multiple machines compete for a common local buffer. Eur J Oper Res, 1995, 84（2）: 330 [1] Huang J Z, Li A P, Liu X M, et al. Optimal design of production line layout considering buffer allocation. J Tongji Univ Nat Sci, 2015, 43（7）: 1075 （黄君政, 李爱平, 刘雪梅, 等. 考虑缓冲区配置的生产线布局优 化设计. 同济大学学报 (自然科学版), 2015, 43（7）：1075） [2] Papadopoulos H T, Vidalis M I. A heuristic algorithm for the buffer allocation in unreliable unbalanced production lines. Comput Ind Eng, 2001, 41（3）: 261 [3] Gupta J N D. Two-stage, hybrid flowshop scheduling problem. J Oper Res Soc, 1988, 39（4）: 359 [4] Djellab H, Djellab K. Preemptive hybrid flowshop scheduling problem of interval orders. Eur J Oper Res, 2002, 137（1）: 37 [5] Bolat A, Al-Harkan I, Al-Harbi B. Flow-shop scheduling for three serial stations with the last two duplicate. Comput Oper Res, 2005, 32（3）: 647 [6] Guirchoun S, Martineau P, Billaut J C. Total completion time minimization in a computer system with a server and two parallel processors. Comput Oper Res, 2005, 32（3）: 599 [7] Brah S A. A comparative analysis of due date based job sequencing rules in a flow shop with multiple processors. Prod Plan Control, 1996, 7（4）: 362 [8] Brah S A, Wheeler G E. Comparison of scheduling rules in a flow shop with multiple processors: A simulation. Simulation, 1998, 71（5）: 302 [9] 600 580 560 540 520 500 480 460 440 420 400 5 10 15 20 25 30 35 Buffer volume (a) Time/min 40 45 50 500 450 400 350 300 250 200 150 100 5 10 15 20 25 30 35 Buffer volume (b) Time/min 40 45 50 3.0 Model 2 Model 1 2.5 2.0 1.5 1.0 0.5 0 5 10 15 20 25 30 35 Buffer volume (c) Buffer equilibrium index/10 4 40 45 50 图 6 模型 1 与模型 2 对比. （a）完工时间；（b）运输时间；（c）缓冲区均衡指数 Fig.6 Comparison of model 1 and model 2: (a) completion time; (b) transportation time; (c) buffer equilibrium index 袁庆欣等： 带有限缓冲区的混合流水车间多目标调度 · 1497 ·
·1498 工程科学学报.第43卷第11期 [10]Priya A,Sahana S K.Multiprocessor scheduling based on scheduling problems /2011 IEEE International Conference on evolutionary technique for solving permutation flow shop problem. Industrial Engineering and Engineering Management.Singapore, EEE Access,2020,8:53151 2011:176 [11]Ruiz R,Vazquez-Rodriguez J A.The hybrid flow shop scheduling [20]Duan J H,Zhang M,Qiao G Y,et al.A genetic algorithm for problem.Eur JOper Res,2010,205(1):1 permutation flowshop scheduling with total flowtime criterion / [12]Khan B,Hanoun S,Johnstone M,et al.Multi-objective job shop 2011 Chinese Control and Decision Conference (CCDC). scheduling using i-NSGA-III /2018 Annual IEEE International Mianyang,2011:1514 Systems Conference.Vancouver,2018:1 [21]Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective [13]Li P,Yang Y X,Du X Y,et al.Iterated local search for distributed genetic algorithm:NSGA-II.IEEE Trans Evol Comput,2002, multiple assembly no-wait flowshop scheduling /2017 IEEE 6(2):182 Congress on Evolutionary Computation.San Sebastian,2017 [22]Wang DJ.Liu F,Jin Y C.A proactive scheduling approach to [14]Smutnicki C.A two-machine permutation flow shop scheduling steel rolling process with stochastic machine breakdown.Nar problem with buffers.Oper-Res-Spektrum,1998,20(4):229 Comput,,2019,18(4):679 [15]Nowicki E.The permutation flow shop with buffers:A tabu search [23]Boufellouh R,Belkaid F.Multi-objective approach to optimize approach.Eur J Oper Res,1999,116(1):205 production and maintenance scheduling in flow shop environment [16]Qian B,Wang L,Huang D X,et al.An effective hybrid DE-based under non-renewable resources constraints /2019 International algorithm for multi-objective flow shop scheduling with limited Conference on Advanced Electrical Engineering (ICAEE).Algiers, buffers.Comput Oper Res,2009,36(1):209 2019 [17]Wang X P,Tang L X.A tabu search heuristic for the hybrid [24]Wang D J,Liu F,Wang JJ,et al.Integrated rescheduling and flowshop scheduling with finite intermediate buffers.Compur preventive maintenance for arrival of new jobs through Oper Res,.2009,36(3):907 evolutionary multi-objective optimization.Soft Comput,2016, [18]Sioud A,Gravel M,Gagne C.A genetic algorithm for solving a 20(4):1635 hybrid flexible flowshop with sequence dependent setup times / [25]Deb K,Jain H.An evolutionary many-objective optimization 2013 IEEE Congress on Evolutionary Computation.Cancun,2013: algorithm using reference-point-based nondominated sorting 2512 approach,Part I:solving problems with box constraints.IEEE [19]Omar M K.Spreadsheet approach for solving complex flowshop Trans Evol Comput,2014,18(4):577
Priya A, Sahana S K. Multiprocessor scheduling based on evolutionary technique for solving permutation flow shop problem. IEEE Access, 2020, 8: 53151 [10] Ruiz R, Vazquez-Rodriguez J A. The hybrid flow shop scheduling problem. Eur J Oper Res, 2010, 205（1）: 1 [11] Khan B, Hanoun S, Johnstone M, et al. Multi-objective job shop scheduling using i-NSGA-III // 2018 Annual IEEE International Systems Conference. Vancouver, 2018: 1 [12] Li P, Yang Y X, Du X Y, et al. Iterated local search for distributed multiple assembly no-wait flowshop scheduling // 2017 IEEE Congress on Evolutionary Computation. San Sebastian, 2017 [13] Smutnicki C. A two-machine permutation flow shop scheduling problem with buffers. Oper-Res-Spektrum, 1998, 20（4）: 229 [14] Nowicki E. The permutation flow shop with buffers: A tabu search approach. Eur J Oper Res, 1999, 116（1）: 205 [15] Qian B, Wang L, Huang D X, et al. An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers. Comput Oper Res, 2009, 36（1）: 209 [16] Wang X P, Tang L X. A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers. Comput Oper Res, 2009, 36（3）: 907 [17] Sioud A, Gravel M, Gagne C. A genetic algorithm for solving a hybrid flexible flowshop with sequence dependent setup times // 2013 IEEE Congress on Evolutionary Computation. Cancun, 2013: 2512 [18] [19] Omar M K. Spreadsheet approach for solving complex flowshop scheduling problems // 2011 IEEE International Conference on Industrial Engineering and Engineering Management. Singapore, 2011: 176 Duan J H, Zhang M, Qiao G Y, et al. A genetic algorithm for permutation flowshop scheduling with total flowtime criterion // 2011 Chinese Control and Decision Conference (CCDC). Mianyang, 2011: 1514 [20] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput, 2002, 6（2）: 182 [21] Wang D J, Liu F, Jin Y C. A proactive scheduling approach to steel rolling process with stochastic machine breakdown. Nat Comput, 2019, 18（4）: 679 [22] Boufellouh R, Belkaid F. Multi-objective approach to optimize production and maintenance scheduling in flow shop environment under non-renewable resources constraints // 2019 International Conference on Advanced Electrical Engineering (ICAEE). Algiers, 2019 [23] Wang D J, Liu F, Wang J J, et al. Integrated rescheduling and preventive maintenance for arrival of new jobs through evolutionary multi-objective optimization. Soft Comput, 2016, 20（4）: 1635 [24] Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I: solving problems with box constraints. IEEE Trans Evol Comput, 2014, 18（4）: 577 [25] · 1498 · 工程科学学报，第 43 卷，第 11 期