带有限缓冲区的混合流水车间多目标调度

工程科学学报 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 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） 工程科学学报，第 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（ 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 期

袁庆欣等：带有限缓冲区的混合流水车间多目标调度 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 期