第16卷第2期 智能系统学报 Vol.16 No.2 2021年3月 CAAI Transactions on Intelligent Systems Mar.2021 D0:10.11992/tis.201906035 网络出版地址：https:/ns.cnki.net/kcms/detail/23.1538.TP.20200727.1906.002.html 改进区块遗传算法解决分布式车间调度问题 裴小兵，孙志卫 （天津理工大学管理学院，天津300384) 摘要：针对分布式车间调度问题，提出了改进区块遗传算法(modified block-genetic algorithm,MBGA)。用 NEH和随机性两种方式得到高质量的初始解，然后进行统计分析，选出精英染色体，建立工件-车间分配矩阵 和工件一机器排序矩阵，挖掘联系紧密的基因链组成区块。构建基于区块的人工染色体，并进行基因重组，提 高解的质量和多样性。通过算例与其他知名算法进行比较，结果表明该算法优于其他算法，并具有较好的稳定 性和准确性。 关键词：区块：协同效应：人工染色体：分布式车间调度问题：遗传算法：基因重组：概率矩阵：组合优化 中图分类号：TP18文献标志码：A文章编号：1673-4785(2021)02-0303-10 中文引用格式：裴小兵，孙志卫.改进区块遗传算法解决分布式车间调度问题.智能系统学报，2021,16(2)：303-312. 英文引用格式：PEI Xiaobing,SUN Zhiwei..Solving distributed-shop scheduling problems based on modified genetic algorithm [JI.CAAI transactions on intelligent systems,2021,16(2):303-312. Solving distributed-shop scheduling problems based on modified genetic algorithm PEI Xiaobing,SUN Zhiwei (School of Management,Tianjin University of Technology,Tianjin 300384,China) Abstract:To solve distributed-job-shop scheduling problems,in this paper,we propose a modified block-genetic al- gorithm(MBGA).First,we initialize the solutions by combining NEH and random assignments.Then,by statistical ana- lysis,we select an elite chromosome to establish a job-factory distribution matrix and job-machine sorting matrix to mine the block's closely linked gene chain.Block-based artificial chromosomes are constructed and recombined to im- prove the quality and diversity of the solutions.The experimental results show that the performance of the proposed MBGA algorithm is superior to that of other well-known algorithms with respect to its stability and accuracy. Keywords:block;synergistic effect;artificial chromosomes;distributed job shop scheduling problem;genetic al- gorithm;gene recombination;probability matrix;combinatorial optimization 随着生产全球化和制造规模化，大型制造企注，如对关键路径的二车间综合调度问题四、分布 业为降低成本、提高生产柔性与生产效率以快速 式流程车间问题)、多工序同时结束的多车间逆 满足全球市场需求，生产方式正由集中性单车间 序综合调度和分布式工作车间问题等。 生产向分布式车间生产转变。但是相关文献研究 经典的单车间调度问题Gob-shop scheduling 还主要集中在单个车间生产调度。近年来，分 problem,JSP)中所有的工件都在同一车间内加工 布式车间调度问题(distributed job-shop scheduling 完成的，DJSP是将工件分配到更多的车间共同加 problem,DJSP)在车间调度研究领域逐渐受到关 工完成。DJSP是对SP的扩展，结合了工件在分 布式车间的分配和单个车间内调度两种问题，并 收稿日期：2019-06-19.网络出版日期：2020-07-28. 基金项目：国家创新方法工作专项(2017M010800). 且允许任何一个车间拥有加工完成任何一个工件 通信作者：孙志卫.E-mail:2838569310@qq.com 的能力
DOI: 10.11992/tis.201906035 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20200727.1906.002.html 改进区块遗传算法解决分布式车间调度问题 裴小兵，孙志卫 （天津理工大学 管理学院，天津 300384） 摘 要：针对分布式车间调度问题，提出了改进区块遗传算法 (modified block-genetic algorithm，MBGA)。用 NEH 和随机性两种方式得到高质量的初始解，然后进行统计分析，选出精英染色体，建立工件−车间分配矩阵 和工件−机器排序矩阵，挖掘联系紧密的基因链组成区块。构建基于区块的人工染色体，并进行基因重组，提 高解的质量和多样性。通过算例与其他知名算法进行比较，结果表明该算法优于其他算法，并具有较好的稳定 性和准确性。 关键词：区块；协同效应；人工染色体；分布式车间调度问题；遗传算法；基因重组；概率矩阵；组合优化 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2021)02−0303−10 中文引用格式：裴小兵, 孙志卫. 改进区块遗传算法解决分布式车间调度问题 [J]. 智能系统学报, 2021, 16(2): 303–312. 英文引用格式：PEI Xiaobing, SUN Zhiwei. Solving distributed-shop scheduling problems based on modified genetic algorithm [J]. CAAI transactions on intelligent systems, 2021, 16(2): 303–312. Solving distributed-shop scheduling problems based on modified genetic algorithm PEI Xiaobing，SUN Zhiwei (School of Management, Tianjin University of Technology, Tianjin 300384, China) Abstract: To solve distributed-job-shop scheduling problems, in this paper, we propose a modified block-genetic algorithm (MBGA). First, we initialize the solutions by combining NEH and random assignments. Then, by statistical analysis, we select an elite chromosome to establish a job-factory distribution matrix and job-machine sorting matrix to mine the block’s closely linked gene chain. Block-based artificial chromosomes are constructed and recombined to improve the quality and diversity of the solutions. The experimental results show that the performance of the proposed MBGA algorithm is superior to that of other well-known algorithms with respect to its stability and accuracy. Keywords: block; synergistic effect; artificial chromosomes; distributed job shop scheduling problem; genetic algorithm; gene recombination; probability matrix; combinatorial optimization 随着生产全球化和制造规模化，大型制造企 业为降低成本、提高生产柔性与生产效率以快速 满足全球市场需求，生产方式正由集中性单车间 生产向分布式车间生产转变。但是相关文献研究 还主要集中在单个车间生产调度[1]。近年来，分 布式车间调度问题 (distributed job-shop scheduling problem，DJSP) 在车间调度研究领域逐渐受到关 注，如对关键路径的二车间综合调度问题[2] 、分布 式流程车间问题[3] 、多工序同时结束的多车间逆 序综合调度[4] 和分布式工作车间问题[5-6] 等。 经典的单车间调度问题[7] (job-shop scheduling problem, JSP) 中所有的工件都在同一车间内加工 完成的，DJSP 是将工件分配到更多的车间共同加 工完成。DJSP 是对 JSP 的扩展，结合了工件在分 布式车间的分配和单个车间内调度两种问题，并 且允许任何一个车间拥有加工完成任何一个工件 的能力。 收稿日期：2019−06−19. 网络出版日期：2020−07−28. 基金项目：国家创新方法工作专项 (2017M010800). 通信作者：孙志卫. E-mail: 2838569310@qq.com. 第 16 卷第 2 期 智 能 系 统 学 报 Vol.16 No.2 2021 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2021
·304· 智能系统学报 第16卷 由于分布式车间调度需要考虑分配和排序两 与蚁群算法相结合的改进区块遗传算法，通过蚁 个阶段，因而DSP更加复杂图：第一阶段将待加工 群算法中的信息素浓度和区块两种方式分别统计 的零件分配到∫家车间中：第二阶段对已经分配 搜索路径和搜索关联度，提炼精英染色体中的有 到同一车间的工件进行排序（即单个车间调度问 效信息，比人造解与遗传算法结合的混合算法等 题)。第一阶段的工件分配很大程度上决定了多 更具有竞争性。区块能较大程度地平衡分布式车 车间之间的工作量协同程度，对算法的结果具有 间之间和机器之间的工作量，使分配到同一车间 至关重要的影响。为了更好地解决DJSP,Wagner网 的工件在每个机器上的加工时间相近，发挥加工 提出了DJSP模型，经过不断的改进能够准确地 车间之间的系统效应。在构建人工染色体的过程 描述出分布式工作车间调度问题的特征，该模型 中，通过以工件为单位或以区块为单位插入到人 的建立对求解DJSP具有重要意义。在该数学模 工染色体的空白位置，提高了染色体的质量，加 型被提出之前，研究者一般使用标准遗传算法来 快了解的收敛速度。 解决分布式车间调度问题，之后的研究也是在 目前关于分布式车间调度问题的文献相对较 标准遗传算法的基础上进行的局部改进，以解决 少，现有研究将分配和排序两阶段分别考虑，在 中小规模的分布式车间调度问题。该数学模型 分配阶段仅考虑每个车间每台机器的工作量均 的提出促进了DJSP的研究进度，扩大了问题的 衡，未涉及下一阶段的工件排序，其结果可能会 可研究规模。Naderi等四运用工件-车间分配原 增加分布式车间的最大完工时间。同时大部分针 则将所有工件分配到每个车间后，再用贪婪式启 对分布式车间调度问题的优化算法没有清晰地说 发算法对每个车间内的工件进行排序，有效地解 明如何通过变异、重组等操作使当前解集不断进 决了分布式车间调度问题：Chaouch等)在分配 化，部分文献仅对分配到不同车间的n个工件中 工件时结合运用了机器加工工件的工作量均衡原 的两个或少数几个工件进行连续调换来优化当前 则和甘特图，再用改进的蚁群优化算法对每个车 解，本文尝试同时调整解序列中车间的分配和工 间的工件进行排序；Naderi等在分配和排序的 件的排序来增加解的多样性。本文基于区块构建 基础上又进行了优化，对当前解中不同车间中相 高质量人工染色体改进传统遗传算法，应用区块 同位置的工件进行随机桃选和互换形成新的解。 保留并传递精英染色体中的高频率基因链，协调 杨敬松等1将遗传和模拟退火算法结合，相互补 分布式车间调度问题中的分配和排序两阶段；改 充弥补各自搜索能力的弱点形成混合遗传算法， 进区块遗传算法中的基因重组和人工染色体的构 用于寻找分布式车间调度问题的最短工艺路径。 建，使之适应于分布式车间调度问题。本研究以 遗传算法(genetic algorithm,GA)通过各种遗 改进后适应于分布式车间调度问题的遗传算法为 传算子（选择，交叉和突变）搜索解空间中的最优 构架，引入基于区块的人工染色体跳出遗传算法 解，得出较优的解决方案16。GA已用于解决生 的局部最优。 产调度、设施布局、资源分配等生产制造中的问 题，而GA没有机械学习能力，当迭代到一定代数 1数学模型的阐述 后评价数值陷入局部最优，产生大量的无用计算 为更好地解决调度问题，Wagner提出了整 降低了求解的精度和效率。为了跳出GA的局部 数规划模型，将调度问题模型化，明确地描述了 最优，Chang等m提出了区块，并将区块与进化算 调度问题的特征。在Naderi等2l首次尝试构建 法结合应用于解决组合优化问题，取得了不错的 分布式车间凋度问题数学模型之前，没有直接研 效果。近年来，通过挖掘区块保留优势解序列信 究分布式车间调度问题的论文，用混合整数线性 息中的高频率基因链与启发式算法结合，优化原 规划模型构建分布式车间调度问题为该问题的解 算法的搜索路径，减少无效迭代。区块与猫群 决提供了基础。 算法结合，统计猫群算法中的跟踪模式更新猫的 分布式工作车间调度问题是将n件工件分配 速度和位置，从而更新优秀解序列产生子群体， 到∫间车间中，每个车间以一定的顺序共同加工 增强了猫群算法的鲁棒性和全局搜索能力。张 完成这批零件，确定这批工件分配和排序的方 敏等2运用区块的关联规则组合成大量的人造 案。每个车间拥有m台机器，且具有独立加工完 解注入到GA中，提高了解的多样性，并通过单点 成每个工件的能力，与车间调度问题中的条件相 突变机制和两种不同的母体重组方式，保证算法 同。假设分布在不同区域的∫个车间的生产能力 的竞争优势。裴小兵等2)提出一种将遗传算法 是相同的，具有相同的机器和车间布局：所需加
由于分布式车间调度需要考虑分配和排序两 个阶段，因而 DJSP 更加复杂[8] ：第一阶段将待加工 的零件分配到 f 家车间中；第二阶段对已经分配 到同一车间的工件进行排序 (即单个车间调度问 题)。第一阶段的工件分配很大程度上决定了多 车间之间的工作量协同程度，对算法的结果具有 至关重要的影响。为了更好地解决 DJSP，Wagner[9] 提出了 DJSP 模型，经过不断的改进能够准确地 描述出分布式工作车间调度问题的特征，该模型 的建立对求解 DJSP 具有重要意义。在该数学模 型被提出之前，研究者一般使用标准遗传算法来 解决分布式车间调度问题[10] ，之后的研究也是在 标准遗传算法的基础上进行的局部改进，以解决 中小规模的分布式车间调度问题[11]。该数学模型 的提出促进了 DJSP 的研究进度，扩大了问题的 可研究规模。Naderi 等 [12] 运用工件−车间分配原 则将所有工件分配到每个车间后，再用贪婪式启 发算法对每个车间内的工件进行排序，有效地解 决了分布式车间调度问题；Chaouch 等 [13] 在分配 工件时结合运用了机器加工工件的工作量均衡原 则和甘特图，再用改进的蚁群优化算法对每个车 间的工件进行排序；Naderi 等 [14]在分配和排序的 基础上又进行了优化，对当前解中不同车间中相 同位置的工件进行随机挑选和互换形成新的解。 杨敬松等[15] 将遗传和模拟退火算法结合，相互补 充弥补各自搜索能力的弱点形成混合遗传算法， 用于寻找分布式车间调度问题的最短工艺路径。 遗传算法 (genetic algorithm，GA) 通过各种遗 传算子 (选择，交叉和突变) 搜索解空间中的最优 解，得出较优的解决方案[16]。GA 已用于解决生 产调度、设施布局、资源分配等生产制造中的问 题，而 GA 没有机械学习能力，当迭代到一定代数 后评价数值陷入局部最优，产生大量的无用计算 降低了求解的精度和效率。为了跳出 GA 的局部 最优，Chang 等 [17] 提出了区块，并将区块与进化算 法结合应用于解决组合优化问题，取得了不错的 效果。近年来，通过挖掘区块保留优势解序列信 息中的高频率基因链与启发式算法结合，优化原 算法的搜索路径，减少无效迭代[18]。区块与猫群 算法结合，统计猫群算法中的跟踪模式更新猫的 速度和位置，从而更新优秀解序列产生子群体， 增强了猫群算法的鲁棒性和全局搜索能力[19]。张 敏等[20] 运用区块的关联规则组合成大量的人造 解注入到 GA 中，提高了解的多样性，并通过单点 突变机制和两种不同的母体重组方式，保证算法 的竞争优势。裴小兵等[21] 提出一种将遗传算法 与蚁群算法相结合的改进区块遗传算法，通过蚁 群算法中的信息素浓度和区块两种方式分别统计 搜索路径和搜索关联度，提炼精英染色体中的有 效信息，比人造解与遗传算法结合的混合算法等 更具有竞争性。区块能较大程度地平衡分布式车 间之间和机器之间的工作量，使分配到同一车间 的工件在每个机器上的加工时间相近，发挥加工 车间之间的系统效应。在构建人工染色体的过程 中，通过以工件为单位或以区块为单位插入到人 工染色体的空白位置，提高了染色体的质量，加 快了解的收敛速度[16]。 目前关于分布式车间调度问题的文献相对较 少，现有研究将分配和排序两阶段分别考虑，在 分配阶段仅考虑每个车间每台机器的工作量均 衡，未涉及下一阶段的工件排序，其结果可能会 增加分布式车间的最大完工时间。同时大部分针 对分布式车间调度问题的优化算法没有清晰地说 明如何通过变异、重组等操作使当前解集不断进 化，部分文献仅对分配到不同车间的 n 个工件中 的两个或少数几个工件进行连续调换来优化当前 解，本文尝试同时调整解序列中车间的分配和工 件的排序来增加解的多样性。本文基于区块构建 高质量人工染色体改进传统遗传算法，应用区块 保留并传递精英染色体中的高频率基因链，协调 分布式车间调度问题中的分配和排序两阶段；改 进区块遗传算法中的基因重组和人工染色体的构 建，使之适应于分布式车间调度问题。本研究以 改进后适应于分布式车间调度问题的遗传算法为 构架，引入基于区块的人工染色体跳出遗传算法 的局部最优。 1 数学模型的阐述 为更好地解决调度问题，Wagner[9] 提出了整 数规划模型，将调度问题模型化，明确地描述了 调度问题的特征。在 Naderi 等 [12] 首次尝试构建 分布式车间调度问题数学模型之前，没有直接研 究分布式车间调度问题的论文，用混合整数线性 规划模型构建分布式车间调度问题为该问题的解 决提供了基础。 分布式工作车间调度问题是将 n 件工件分配 到 f 间车间中，每个车间以一定的顺序共同加工 完成这批零件，确定这批工件分配和排序的方 案。每个车间拥有 m 台机器，且具有独立加工完 成每个工件的能力，与车间调度问题中的条件相 同。假设分布在不同区域的 f 个车间的生产能力 是相同的，具有相同的机器和车间布局；所需加 ·304· 智 能 系 统 学 报 第 16 卷
第2期 裴小兵，等：改进区块遗传算法解决分布式车间调度问题 ·305· 工的工件可以在任意车间内加工完成，且加工所 Cmx≥C,YH (7) 需的时间是相同的；不考虑工资水平、运输距离 式(8(10)为决策变量。 等因素。在工件加工过程中，已经分配到加工车 Ci≥0N# (8) 间的工件禁止转移到其他车间加工，因为工件在 车间之间的交叉加工将增加成本和技术难度。 Ya∈{0,1，Va (9) DJSP的约束条件为：1)每个工件只能分配到一个 Xa∈{0,1，Vjk-j (10) 车间内，且每个工件都由特定的车间加工；2)每 在实际的分布式车间调度问题中，安排到每 台机器只能同时加工一个零件，每个零件只能同 个车间的工件数n应该远远大于机器台数m,这 时由一台机器加工；3)分配到同一车间内的工件 样才能使得机器的生产能力得到有效的应用，缩 都在该车间内顺序加工；4)n件工件的最大完工 短平均加工时间。 时间就是个车间中完工时间最长的车间的最大 完工时间。则DSP整数线性规划模型为： 2改进区块遗传算法 模型中用到的参数为：n表示工件数，j,k={1, 为适应分布式车间调度问题的特征，对传统 2,…,n}:m表示车间内机器数，i,={1,2,…,m:f表 遗传算法进行了改进，将基因交叉过程中重叠的 示车间数，={1,2，…，乃；P:表示工件j在机器i上 工件放入重组工件基因池中，再重新插入到解序 的加工时间；au:如果工作j在机器u上加工完 列中进行重组。在遗传算法中注人基于区块的高 之后立即在机器i上进行加工，则a=1,否则 质量的人工染色体增加解的多样性；从挑选的精 am=O;M为一个较大的正数。 决策变量为：X取0,1值，如果机器u在加 英染色体中统计出工件-车间分配矩阵和工件 工完工件k之后加工工件j,则X=1,否则 -机器位置矩阵，然后根据概率矩阵挖掘区块，运 用两种组合机制构建人工染色体，协调工作车间 Xm=0。Y取0,1值，如果工件j在车间r加工， 和车间内机器的工作量，优化搜索路径。算法步 则Y=l,否则Y=0。C:工件j在机器i上累计加 骤如下： 工时间的连续变量。 1)生成初始解。为保证初始解的质量和多样 整体线性规划模型为： 性，本文运用NEH和随机性两种方式，按照最早 式(1)是目标函数，寻找最小化的最大完工 完工的原则初始化种群。 时间： Minimize Cmax (1) 2)计算适应度并挑选精英染色体。计算每 个染色体的适应值，并使适应度按从小到大的顺 Subject to: 式(2)表示将每个工件都安排到唯一的车间 序进行排序，挑选出前30%的染色体作为精英染 内进行加工： 色体。 3)更新概率矩阵。分别建立工件-车间分配 y=1￥ (2) 矩阵和工件-机器排序矩阵，并随着迭代过程不 断地更新概率矩阵中的信息。 式(3)表示工件的完成时间大于该工件的加 4)组合区块。根据概率矩阵中的信息，组合 工时间： 区块。 Cn≥P,Hj (3) 5)构建人工染色体。根据区块库和概率矩阵 式(4)表示在同一时间内，一个工件最多能在 中的信息，运用轮盘赌的方式构建人工染色体。 一台机器上加工。 6)对分布式车间调度问题的解序列进行重 Ca≥C1+P,Hew=l (4) 组。将父代的染色体以某一车间中工件加工的解 式（⑤）和(6)表示在同一工厂内，一台机器最 序列片段为单位进行重组。 多能同时加工一个工件；当且仅当X=1时，式 7筛选优精英染色体。将从重组后的染色体 (5)和(6)才能够同时成立，换而言之，同 与原父代的染色体进行融合，筛选出新的精英染 一工厂的机器i加工完成工件k之后才能加工工 色体作为下一次迭代的父代。 件j。 MBGA算法流程图（见图1）中，△R为概率 Ch Cki+pji-M(3-Xkji-Yir-Yk).Vriken.jpk (5) 模型迭代计数器，R为概率模型迭代的门槛值， Cki Cji+pui-M(2+Xkji-Yir-Ykr),Vriken.jpk (6 △A和Ae分别为构成人工染色体的计数器和门 式(7表示最大完工时间： 槛值
工的工件可以在任意车间内加工完成，且加工所 需的时间是相同的；不考虑工资水平、运输距离 等因素。在工件加工过程中，已经分配到加工车 间的工件禁止转移到其他车间加工，因为工件在 车间之间的交叉加工将增加成本和技术难度。 DJSP 的约束条件为：1）每个工件只能分配到一个 车间内，且每个工件都由特定的车间加工；2）每 台机器只能同时加工一个零件，每个零件只能同 时由一台机器加工；3）分配到同一车间内的工件 都在该车间内顺序加工；4）n 件工件的最大完工 时间就是 f 个车间中完工时间最长的车间的最大 完工时间。则 DJSP 整数线性规划模型为： pj,i aj,i,u aj,i,u aj,i,u 模型中用到的参数为：n 表示工件数, j, k={1, 2,…,n}；m 表示车间内机器数, i，u={1,2,…,m}；f 表 示车间数, r={1,2,…, f}； 表示工件 j 在机器 i 上 的加工时间； ：如果工作 j 在机器 u 上加工完 之后立即在机器 i 上进行加工，则 =1，否则 =0；M 为一个较大的正数。 Xk, j,u Xk, j,u Xk, j,u Yj,r Yj,r Yj,r Cj,i 决策变量为： 取 0，1 值，如果机器 u 在加 工完工 件 k 之后加工工 件 j ， 则 = 1 ，否则 =0。 取 0，1 值，如果工件 j 在车间 r 加工， 则 =1，否则 =0。 ：工件 j 在机器 i 上累计加 工时间的连续变量。 整体线性规划模型为： 式 (1) 是目标函数，寻找最小化的最大完工 时间： Minimize Cmax (1) Subject to: 式 (2) 表示将每个工件都安排到唯一的车间 内进行加工： ∑ f r=1 Yj,r = 1,∀j (2) 式 (3) 表示工件的完成时间大于该工件的加 工时间： Cj,i ⩾ pj,i ,∀j ,i (3) 式 (4) 表示在同一时间内，一个工件最多能在 一台机器上加工。 Cj,i ⩾ Cj,l + pj,i ,∀j,i,l,i|aj,i,l=1 (4) Xk, j,i= 1 式 (5) 和 (6) 表示在同一工厂内，一台机器最 多能同时加工一个工件；当且仅当 时，式 ( 5 ) 和 ( 6 ) 才能够同时成立，换而言之，同 一工厂的机器 i 加工完成工件 k 之后才能加工工 件 j。 Cj,i ⩾ Ck,i + pj,i − M(3− Xk, j,i −Yj,r −Yk,r),∀r,i,kk (5) Ck,i ⩾ Cj,i + pk,i − M(2+ Xk, j,i −Yj,r −Yk,r),∀r,i,kk (6) 式 (7) 表示最大完工时间: Cmax ⩾ Cj,i ,∀j,i (7) 式 (8)~(10) 为决策变量。 Cj,i ⩾ 0∀j,i (8) Yj,i ∈ {0,1},∀j,i (9) Xk, j,i ∈ {0,1},∀jj,i (10) 在实际的分布式车间调度问题中，安排到每 个车间的工件数 n 应该远远大于机器台数 m，这 样才能使得机器的生产能力得到有效的应用，缩 短平均加工时间。 2 改进区块遗传算法 为适应分布式车间调度问题的特征，对传统 遗传算法进行了改进，将基因交叉过程中重叠的 工件放入重组工件基因池中，再重新插入到解序 列中进行重组。在遗传算法中注入基于区块的高 质量的人工染色体增加解的多样性；从挑选的精 英染色体中统计出工件−车间分配矩阵和工件 −机器位置矩阵，然后根据概率矩阵挖掘区块，运 用两种组合机制构建人工染色体，协调工作车间 和车间内机器的工作量，优化搜索路径。算法步 骤如下： 1) 生成初始解。为保证初始解的质量和多样 性，本文运用 NEH 和随机性两种方式，按照最早 完工的原则初始化种群。 2) 计算适应度并挑选精英染色体。计算每 个染色体的适应值，并使适应度按从小到大的顺 序进行排序，挑选出前 30% 的染色体作为精英染 色体。 3) 更新概率矩阵。分别建立工件−车间分配 矩阵和工件−机器排序矩阵，并随着迭代过程不 断地更新概率矩阵中的信息。 4) 组合区块。根据概率矩阵中的信息，组合 区块。 5) 构建人工染色体。根据区块库和概率矩阵 中的信息，运用轮盘赌的方式构建人工染色体。 6) 对分布式车间调度问题的解序列进行重 组。将父代的染色体以某一车间中工件加工的解 序列片段为单位进行重组。 7) 筛选优精英染色体。将从重组后的染色体 与原父代的染色体进行融合，筛选出新的精英染 色体作为下一次迭代的父代。 ∆R Rthe ∆A Athe MBGA 算法流程图 (见图 1) 中 ， 为概率 模型迭代计数器， 为概率模型迭代的门槛值， 和 分别为构成人工染色体的计数器和门 槛值。 第 2 期 裴小兵，等：改进区块遗传算法解决分布式车间调度问题 ·305·
·306· 智能系统学报 第16卷 开始 间的混乱。其中前(n-/2的工件运用NEH进行 排序，剩余的工件进行随机排序，生成不同的解 初始化 序列。 每个工件在机器上的总加工时间为 计算适应值 workoad=(∑pah+pn (11) kER 挑选精英染色体 式中：R:为工件j在机器i上加工之前所经过机 器的集合；P:为工件j在机器i上的加工时间。 表1是分布式车间调度问题的案例，将8个 △R≥Re 需要加工的零件分配到两个车间进行加工，工件 清空概率模型& △R=0 在车间上的加工路径和在每个机器上的加工时间 更新概率模型 已经确定。计算出每个工件的总加工时间并进行 排序（如表2），确定工件分配的优先权。先将排 序中的前两个工件分配到车间中确定车间的编 区块挖掘 △M≥Ar 码，再将排序在后的4件工件随机插入到车间 N 1和车间2的加工序列中，根据获得的优先权和 构建染色体& NEH原则对剩余的工件进行分配和排序，最终形 基因重组 △4=0 成可行的分布式车间调度方案。 计算适应值 表1分布式工作车间中工件的加工时间和路径 Table 1 Processing time and path in distributed job shop 替换 机器 工件 加工路径 2 迭代标准 7 {1,2} 2 6 2,1} N 6 结束 3 5 6 2,1} 4 6 4 {1,2} 图1MBGA流程 Fig.1 Flow chart of MBGA 5 2,1} 2.1生成初始解 6 {2,1 传统GA随机生成初始解，生成的个体适应 7 {1,2 度较低，影响解的收敛速度和最终解的质量。本 2,1} 文混合应用NEH(Nawaz-Enscore-Ham)算法和 完全随机两种方式构造初始解，既保证解的质 表2优先排序权 量，又保持解的多样性。MBGA运用其中前n/2 Table 2 Job priority 件工件用NEH算法排序，剩余的工件随机插入 机器 总加工时间 到f家车间的解序列片段中。分别计算n件工件 工件 排序顺序 2 1s) 中的每一个工件j在m台机器上的总加工时间， 1 4 7 11 并对每个工件的总加工时间进行降序排序，将优 先排序权赋予排序在前的工件。先将排序中的 2 6 6 12 3 前∫件工件分别分配到∫家车间中，车间根据接受 3 5 6 11 5 到工件的先后次序进行编号，第1个接受到工件 4 6 4 10 6 的车间为，第2个接受到工件的车间为5，依次 5 3 5 8 7 生成车间编号。将前f件工件固化到∫家车间中， 4 8 f 剩余的n-∫件工件可以跨车间分配。假设∫家车 7 5 13 间完全相同，将前件工件固化到车间之后，能够 8 7 15 1 有效地区分车间，避免在迭代过程中造成车间之
清空概率模型& ΔR=0 Y N 计算适应值 挑选精英染色体 初始化 更新概率模型 Y N Y 开始 基因重组 计算适应值 替换 迭代标准 N 结束 区块挖掘 构建染色体& ΔA=0 ΔR≥Rthe ΔA≥Athe 图 1 MBGA 流程 Fig. 1 Flow chart of MBGA 2.1 生成初始解 传统 GA 随机生成初始解，生成的个体适应 度较低，影响解的收敛速度和最终解的质量。本 文混合应用 NEH(Nawaz-Enscore–Ham) 算法和 完全随机两种方式构造初始解，既保证解的质 量，又保持解的多样性。MBGA 运用其中前 n/2 件工件用 NEH 算法排序，剩余的工件随机插入 到 f 家车间的解序列片段中。分别计算 n 件工件 中的每一个工件 j 在 m 台机器上的总加工时间， 并对每个工件的总加工时间进行降序排序，将优 先排序权赋予排序在前的工件。先将排序中的 前 f 件工件分别分配到 f 家车间中，车间根据接受 到工件的先后次序进行编号，第 1 个接受到工件 的车间为 f1，第 2 个接受到工件的车间为 f2，依次 生成车间编号。将前 f 件工件固化到 f 家车间中， 剩余的 n−f 件工件可以跨车间分配。假设 f 家车 间完全相同，将前 f 件工件固化到车间之后，能够 有效地区分车间，避免在迭代过程中造成车间之 间的混乱。其中前 (n−f)/2 的工件运用 NEH 进行 排序，剩余的工件进行随机排序，生成不同的解 序列。 每个工件在机器上的总加工时间为 workload(j,i) = (∑ k∈Rj,i pj,k ) + pj,i ,∀i, j (11) Rj,i pj,i 式中： 为工件 j 在机器 i 上加工之前所经过机 器的集合； 为工件 j 在机器 i 上的加工时间。 表 1 是分布式车间调度问题的案例，将 8 个 需要加工的零件分配到两个车间进行加工，工件 在车间上的加工路径和在每个机器上的加工时间 已经确定。计算出每个工件的总加工时间并进行 排序 (如表 2)，确定工件分配的优先权。先将排 序中的前两个工件分配到车间中确定车间的编 码，再将排序在后的 4 件工件随机插入到车间 1 和车间 2 的加工序列中，根据获得的优先权和 NEH 原则对剩余的工件进行分配和排序，最终形 成可行的分布式车间调度方案。 表 1 分布式工作车间中工件的加工时间和路径 Table 1 Processing time and path in distributed job shop 工件 机器 加工路径 1 2 1 4 7 {1,2} 2 6 6 {2,1} 3 5 6 {2,1} 4 6 4 {1,2} 5 3 5 {2,1} 6 4 4 {2,1} 7 8 5 {1,2} 8 8 7 {2,1} 表 2 优先排序权 Table 2 Job priority 工件 机器 总加工时间 /(s) 排序顺序 1 2 1 4 7 11 4 2 6 6 12 3 3 5 6 11 5 4 6 4 10 6 5 3 5 8 7 6 4 4 8 8 7 8 5 13 2 8 8 7 15 1 ·306· 智 能 系 统 学 报 第 16 卷
第2期 裴小兵，等：改进区块遗传算法解决分布式车间调度问题 ·307· 2.2构建概率矩阵模型 置的机会，将概率矩阵中每个位置的概率值增加 精英染色体是筛选出来的高适应度解序列。 0.01；在构建人工染色体的时，每个位置可以选到 为了有效地挖掘区块，MBGA依据迭代过程中筛 剩余工件的任意一个，增加了样本的多样性，避 选的精英染色体构建了两个概率矩阵：一个是工 免缩小搜索空间。 件-车间分配矩阵，另一个是工件-机器排序矩 阵。工件一车间排序矩阵强调的是工件和车间之 精英染色体 间的关系，工件一机器排序矩阵强调的是工件在 8216 工 工厂 4375 2 12 车间内机器上的加工顺序。 3/52/5 本文采用世代累加的方式建立概率模型，统 82 6 2/53/5 4375 计工件在机器上加工的频次，构建工件-机器排 3352/5 序矩阵。在构建和更新矩阵的过程中，工件被 43 86 4253/5 7512 51/54/5 分配到车间”，工件-车间分配矩阵中相应位置的 64/515 频次就会增加1。工件k和工件j分配到同一车 85 77 入N 0 1 间，且在机器上先后加工，工件-机器排序矩阵中 必 810 的相应位置增加1。然后，将相应的频次转化为 8136 概率矩阵，并随着迭代不断更新。 5742 工件-车间分配矩阵的迭代公式为 图2工件-车间分配概率矩阵示意 足：位 如果工件在工厂 Fig.2 Schematic diagram of job-shop assignment probab- (12) ility matrix i=1,2,…,r=1,2,…,fk=1,2,…, 精英染色体 T0=70-1+2xi=1,2…,m 8216 位置 位置 (13) 4375 4 1234 k=1 r=1,2,…,ft=1,2,…,G;k=1,2,…,s 8216 0 11/51/5350 4 201/5045 4375 式(12)和(13)中，X表示工件i分配到车间 30252515 r;k代表解序列号码；n代表工件数目；s代表精 4386 4351/5150 7512 5/5251/5/5 英染色体的个数；1代表当前迭代数；G代表总 6 0 4 8512 600/545 迭代次数；T0表示工件i分配到车间r的累加 2210 725251/50 7463 次数。 件83110 件835闪0 8136 工件-机器排序矩阵的迭代公式为 5742 龙=化买程工件在机 (14) 图3工件-位置排序矩阵示意 i=1,2,…,j=1,2,…,mk=1,2,…,m Fig.3 Schematic diagram of job-position sorting matrix 2.3区块挖掘 T0=T-1）+∑Xi=12…,i 精英染色体的解序列中拥有相似的解序列片 k=1 (15) 段，算法以区块的形式将这部分信息进行挖掘用 j=1,2,…,n:t=1,2,…,G:k=1,2,…,s 于构建高质量的人工染色体。区块是高适应度解 式中：表示工件i在机器j上的总加工次数。 序列中的部分片段，由精英染色体中的高频率的 具体的工件-车间分配矩阵的更新过程如图2 基因链接组成。区块将不同机器上加工时间互补 所示，假设C,C2,…,C3为5个用于更新分配矩阵 的工件组合起来，用于平衡工件在机器上的加工 的精英染色体；以工件5为例，有1个精英染色体 时间，优化同一车间内工件的排序过程，并确定 将工件5分配到车间1，有4个精英染色体将工工件的分配过程。高质量的区块保证了人工染色 件5分配到车间2，因此工件5分配到车间1的概 体的优势，又降低了排序的复杂程度。区块的规 率为1/5，分配到车间2的概率为4/5。工件-机器 模越大，构建人工染色体的过程就越简单，但由 排序矩阵的更新原理同分配矩阵的更新原理相 于工件-车间分配矩阵和工件-机器排序矩阵中 同（如图3） 的概率都小于1（图4中的Pock为挖掘该区块的 为确保工件j拥有分配到每个车间中每个位 频率)，所以区块规模越大，挖掘该区块的概率就
2.2 构建概率矩阵模型 精英染色体是筛选出来的高适应度解序列。 为了有效地挖掘区块，MBGA 依据迭代过程中筛 选的精英染色体构建了两个概率矩阵：一个是工 件−车间分配矩阵，另一个是工件−机器排序矩 阵。工件−车间排序矩阵强调的是工件和车间之 间的关系，工件−机器排序矩阵强调的是工件在 车间内机器上的加工顺序。 本文采用世代累加的方式建立概率模型，统 计工件在机器上加工的频次，构建工件−机器排 序矩阵。在构建和更新矩阵的过程中，工件 j 被 分配到车间 r，工件−车间分配矩阵中相应位置的 频次就会增加 1。工件 k 和工件 j 分配到同一车 间，且在机器上先后加工，工件−机器排序矩阵中 的相应位置增加 1。然后，将相应的频次转化为 概率矩阵，并随着迭代不断更新。 工件−车间分配矩阵的迭代公式为 X k ir = { 1, 如果工件i在工厂r 0, 其他 i = 1,2,··· ,n; r = 1,2,··· , f ; k = 1,2,··· ,s (12) Tir(t) = Tir(t−1)+ ∑m k=1 X k ir,i = 1,2,··· ,n; r = 1,2,··· , f ;t = 1,2,··· ,G; k = 1,2,··· ,s (13) X k ir Tir(t) 式 (12) 和 (13) 中， 表示工件 i 分配到车间 r；k 代表解序列号码；n 代表工件数目；s 代表精 英染色体的个数；t 代表当前迭代数；G 代表总 迭代次数； 表示工件 i 分配到车间 r 的累加 次数。 工件-机器排序矩阵的迭代公式为 X k ir = { 1, 如果工件i在机器j 0, 其他 i = 1,2,··· ,n; j = 1,2,··· ,n; k = 1,2,··· ,m (14) Ti j(t) = Ti j(t−1)+ ∑m k=1 X k i j,i = 1,2,··· ,n; j = 1,2,··· ,n;t = 1,2,··· ,G; k = 1,2,··· ,s (15) X k 式中： i j 表示工件 i 在机器 j 上的总加工次数。 具体的工件−车间分配矩阵的更新过程如图 2 所示，假设 C1 ,C2 ,…,C5 为 5 个用于更新分配矩阵 的精英染色体；以工件 5 为例，有 1 个精英染色体 将工件 5 分配到车间 1，有 4 个精英染色体将工 件 5 分配到车间 2，因此工件 5 分配到车间 1 的概 率为 1/5，分配到车间 2 的概率为 4/5。工件−机器 排序矩阵的更新原理同分配矩阵的更新原理相 同 (如图 3)。 为确保工件 j 拥有分配到每个车间中每个位 置的机会，将概率矩阵中每个位置的概率值增加 0.01；在构建人工染色体的时，每个位置可以选到 剩余工件的任意一个，增加了样本的多样性，避 免缩小搜索空间。 8 6 4 5 2 3 7 1 8 6 4 5 2 3 7 1 C1 C2 4 6 7 2 3 5 1 8 C3 8 2 7 3 5 4 6 1 C4 8 6 5 2 1 7 4 3 C5 1 2 1 3 2 4 6 5 7 3 2 2 3 3 2 2 3 1 4 4 1 0 5 8 5 0 工厂 工件 1 2 1 3 2 4 6 5 7 3/5 2/5 2/5 3/5 3/5 2/5 2/5 3/5 1/5 4/5 4/5 1/5 0 1 8 1 0 工厂 工件 精英染色体 图 2 工件−车间分配概率矩阵示意 Fig. 2 Schematic diagram of job-shop assignment probability matrix 8 6 4 5 2 73 1 8 6 4 5 2 73 1 C1 C2 4 6 7 2 3 15 8 C3 8 2 7 3 5 64 1 C4 8 6 5 2 1 47 3 C5 1 2 1 3 2 4 6 5 7 1 1 0 1 0 2 3 1 1 2 0 0 2 2 8 3 1 位置 工件 精英染色体 3 4 3 0 0 4 2 1 1 0 1 1 1 4 1 0 1 0 1 2 1 3 2 4 6 5 7 1/5 1/5 0 1/5 0 2/5 3/5 1/5 1/5 2/5 0 0 2/5 2/5 8 3/5 1/5 位置 工件 3 4 3/5 0 0 4/5 2/5 1/5 1/5 0 1/5 1/5 1/5 4/5 1/5 0 1/5 0 图 3 工件−位置排序矩阵示意 Fig. 3 Schematic diagram of job-position sorting matrix 2.3 区块挖掘 精英染色体的解序列中拥有相似的解序列片 段，算法以区块的形式将这部分信息进行挖掘用 于构建高质量的人工染色体。区块是高适应度解 序列中的部分片段，由精英染色体中的高频率的 基因链接组成。区块将不同机器上加工时间互补 的工件组合起来，用于平衡工件在机器上的加工 时间，优化同一车间内工件的排序过程，并确定 工件的分配过程。高质量的区块保证了人工染色 体的优势，又降低了排序的复杂程度。区块的规 模越大，构建人工染色体的过程就越简单，但由 于工件−车间分配矩阵和工件−机器排序矩阵中 的概率都小于 1(图 4 中的 Pblock 为挖掘该区块的 频率)，所以区块规模越大，挖掘该区块的概率就 第 2 期 裴小兵，等：改进区块遗传算法解决分布式车间调度问题 ·307·
·308· 智能系统学报 第16卷 越低。本文运用了动态门槛值，适当地增加区块 到该染色体中，若没有找到相应的区块，则根据 的规模；区块的长度为3~5，具体的长度根据门槛 概率矩阵挑选下一个位置的工件；组合机制2先 值来确定，并且门槛值随着迭代的进行从0.5~0.8 将区块库中的区块复制到染色体中的空白位置， 不断增加。 减少工件排序的数量，再随机将没有分配的工件 位置 复制到人工染色体中剩余的空白位置。 1234 区块库 。区块库 组合机制一的具体过程为：先根据工件-车间 11/51/53/50 201E045 516 516 分配矩阵运用轮盘赌的方式分配工件，若所选的 3 0 2/52/51/5RWS 56H 843 473 工件包含于工件-车间区块中，则将该区块中所 43/51/E1W50 5/52/1/5/ Ph=040.6t08-0. 473 包含的所有工件都分配到同一车间中；若没有包 3 6001/F4/5 751 含于区块中，则继续为下一个车间筛选工件，依 工722w50 件83/151/0 次将工件分配到总加工时间最少的车间。其次， 依据工件一机器排序矩阵运用轮盘赌的方式为同 图4工件-车间分配区块挖掘方式 车间内的工件排序，如果挑选的工件位于工件- Fig.4 Job-shop assignment block mining method 机器区块库中区块的第一个位置且包含的工件都 区块的组合过程如图5，根据工件-机器排序 在该车间加工，那么就将该区块插入到相应的位 概率矩阵，通过累积计算区块生成的概率，再依 置；如果不是在区块的首位或者没有包含该工件 据一定的筛选规则组合成区块库。 的工件-机器排序区块，那么继续为下一个工件 位置 1234 排序，直到所有确定所有工件的加工顺序。如 区块库 区块库 11/S1/53/50 图6，工件8分配到第一个车间即，工件6和工 201/E04/5 516 516 'a西- 件3与工件8在同一个区块中，故工件8,6和 843 4⑦3 43/S1/1/0 3被分配到f中，在剩余工件中随机的挑选出工 51/52/51/51/F 473 件4,7,5和1分配到方中，最后的工件2分配到 6001/54/ 751 工72/52/51/50 中。在排序阶段，依据工件-机器排序矩阵运用 件83/51/51/50 轮盘赌的方式将工件8第排在第一个位置，将工 图5工件-位置排序区块挖掘方式 件4排在方中的第一个位置；工件4位于区块中 Fig.5 Job-location sorting block Mining method 的首位，将该区块复制到染色体的相应位置上； 在区块库中存在部分重复的区块，通过区块 剩余的工件依据工件一机器排序矩阵运用轮盘赌 竞争剔除质量较差并含有重叠部分的区块。区块 进行排序，直到完成所有工件的排序。 重叠分为两种：区块中工件的重复和区块内机器 区块库 区块库 重复次数超过所需要加工的工序数。在筛选高质 量区块时，优化指标为组合区块的平均概率，平均 概率越小，构建的区块质量就越差。平均概率为 =上宫网 f=86,3,2 式中：B为第n块区块；L为区块长度；p)是由 f=4,75,1 位置矩阵得出的概率。 2.4构建人工染色体 构建人工染色体是算法的另一个重点，既要 加快解的汇集速度，又要避免过早收敛，保证解 的多样性和质量。MBGA运用了两种组合机制 构造人工染色体，每种组合机制又分为两个阶 475 段，第一阶段是将工件分配到车间中，第二阶段 是为分配到同一车间的工件排序。组合机制1先 8326 根据分配概率和区块库将工件分配到车间中，再 4751 对分配到同一车间的工件进行排序，若挑选出的 图6第1种组合机制 工件包含于区块中第一个位置，则将该区块插入 Fig.6 The first combination mechanism
越低。本文运用了动态门槛值，适当地增加区块 的规模；区块的长度为 3~5，具体的长度根据门槛 值来确定，并且门槛值随着迭代的进行从 0.5~0.8 不断增加。 5 1 6 区块库 RWS 5 1 6 8 4 3 4 7 3 7 5 1 区块库 5 1 6 4 7 3 1 2 1 3 2 4 6 5 7 1/51/5 0 1/5 0 2/5 3/51/5 1/52/5 0 0 2/52/5 8 3/5 1/5 位置 工件 3 4 3/5 0 0 4/5 2/51/5 1/5 0 1/51/5 1/54/5 1/5 0 1/5 0 Pblock= 0.4+0.6+0.8 3 =0.6 图 4 工件−车间分配区块挖掘方式 Fig. 4 Job-shop assignment block mining method 区块的组合过程如图 5，根据工件−机器排序 概率矩阵，通过累积计算区块生成的概率，再依 据一定的筛选规则组合成区块库。 5 1 6 区块库 RWS 5 1 6 8 4 3 4 7 3 7 5 1 区块库 5 1 6 4 7 3 1 2 1 3 2 4 6 5 7 1/51/5 0 1/5 0 2/5 3/51/5 1/52/5 0 0 2/52/5 8 3/5 1/5 位置 工件 3 4 3/5 0 0 4/5 2/51/5 1/5 0 1/51/5 1/54/5 1/5 0 1/5 0 图 5 工件−位置排序区块挖掘方式 Fig. 5 Job-location sorting block Mining method 在区块库中存在部分重复的区块，通过区块 竞争剔除质量较差并含有重叠部分的区块。区块 重叠分为两种：区块中工件的重复和区块内机器 重复次数超过所需要加工的工序数。在筛选高质 量区块时，优化指标为组合区块的平均概率，平均 概率越小，构建的区块质量就越差。平均概率为 P avg B(n) = L −1∑L i=1 P (p) B (n) i B (n) P 式中： 为第 (p) n 块区块；L 为区块长度； 是由 位置矩阵得出的概率。 2.4 构建人工染色体 构建人工染色体是算法的另一个重点，既要 加快解的汇集速度，又要避免过早收敛，保证解 的多样性和质量。MBGA 运用了两种组合机制 构造人工染色体，每种组合机制又分为两个阶 段，第一阶段是将工件分配到车间中，第二阶段 是为分配到同一车间的工件排序。组合机制 1 先 根据分配概率和区块库将工件分配到车间中，再 对分配到同一车间的工件进行排序，若挑选出的 工件包含于区块中第一个位置，则将该区块插入 到该染色体中，若没有找到相应的区块，则根据 概率矩阵挑选下一个位置的工件；组合机制 2 先 将区块库中的区块复制到染色体中的空白位置， 减少工件排序的数量，再随机将没有分配的工件 复制到人工染色体中剩余的空白位置。 组合机制一的具体过程为：先根据工件−车间 分配矩阵运用轮盘赌的方式分配工件，若所选的 工件包含于工件−车间区块中，则将该区块中所 包含的所有工件都分配到同一车间中；若没有包 含于区块中，则继续为下一个车间筛选工件，依 次将工件分配到总加工时间最少的车间。其次， 依据工件−机器排序矩阵运用轮盘赌的方式为同 一车间内的工件排序，如果挑选的工件位于工件− 机器区块库中区块的第一个位置且包含的工件都 在该车间加工，那么就将该区块插入到相应的位 置；如果不是在区块的首位或者没有包含该工件 的工件−机器排序区块，那么继续为下一个工件 排序，直到所有确定所有工件的加工顺序。如 图 6，工件 8 分配到第一个车间即 f1，工件 6 和工 件 3 与工件 8 在同一个区块中，故工件 8，6 和 3 被分配到 f1 中，在剩余工件中随机的挑选出工 件 4，7，5 和 1 分配到 f2 中，最后的工件 2 分配到 f1 中。在排序阶段，依据工件−机器排序矩阵运用 轮盘赌的方式将工件 8 第排在第一个位置，将工 件 4 排在 f2 中的第一个位置；工件 4 位于区块中 的首位，将该区块复制到染色体的相应位置上； 剩余的工件依据工件−机器排序矩阵运用轮盘赌 进行排序，直到完成所有工件的排序。 区块库 2 4 5 8 6 3 区块库 5 1 6 4 7 3 f1=8,6,3,2 f2=4,7,5,1 8 4 8 4 3 7 5 8 6 4 1 3 7 5 2 图 6 第 1 种组合机制 Fig. 6 The first combination mechanism ·308· 智 能 系 统 学 报 第 16 卷
第2期 裴小兵，等：改进区块遗传算法解决分布式车间调度问题 ·309 组合机制2，先将工件-车间区块库中的区块 8326 8516 随机地复制到人工染色体中的空白位置，具体位 4751 254732 置由区块中首个工件分配到车间的概率和在机器 上排序的概率决定；然后根据分配和排序矩阵， 将未分配的工件插入到人工染色体的空白位置。 Pf8326 P68516 首先，随机地将区块516复制到染色体中的空 P64732 P4751 白位置（如图7）具体位置应该根据首个工件（工 件1)在各个位置的概率，运用轮盘赌来确定。剩 6 3.2 6 余的工件，还是分为两个阶段根据工件-车间和 1,5 47 工件-机器的概率矩阵用轮盘赌进行排序，直到 重组工件池 所有的工件都排序完成。 8516 236 区块库 区块库 4723 751 6 图8基因交叉 6 473 Fig.8 Gene crossing 3计算结果与分析 为了测试和验证MBGA的求解能力，在Mi- crosoft Visual Studio2012中的C++上编写该算法 8516 程序，并在Window8、32位系统、主频3.40的酷 4732 睿CPU、4GB内存的电脑上运行完成测试。本文 测试所用的数据来自Taillard中的生产车间调度 图7第2种组合机制 Fig.7 The second combination mechanism 问题的基准实例，选取工件个数为15、20、30和 机器台数为15、20共50个组合进行比较分析。 2.5基因重组 比较标准是相对百分比偏差(relative percentage 通过基因重组发现改良的染色体，直到生成 deviation,RPD),计算公式为 最优的染色体，MBGA改进了基因重组中的交叉 RPD=Alg-Min ×100 产生新的子代。染色体中每行的解序列片段是某 Min 一车间内的工件加工顺序，所有工件恰好在间 式中：AIg表示运用MBGA获得最优的最大完工 车间内加工完成。在基因交叉的过程中，以每个 时间：Min表示基准实例所给出的最小化的最大 车间内的工件加工序列（即每行的解序列片段） 完工时间。 从Taillard中选择50种具有代表性的例题测 为交换单位，既能保留父代和每个车间的有效信 息，又能搜索每个车间的所有可能解。 试该算法的寻优性能。表3中是在不同的n、 m以及加工顺序下生成的50种实例组合下，每个 适应DJSP的MBGA中，基因交叉的例子如 组合的平均RPD是对不同车间数户2，仁3，=4 图8所示，挑选两个染色体为父代(P,P),从一个 户5的最优RPD平均值。有一半以上的平均RPD 父代的解序列中随机选取2行解序列片段，剩余 为0，证明一半以上的测算实例达到了目前已知 的2行解序列片段从另一个父代中选取，按照原 的最大完工时间的下限值。 行数重新构造解序列(G),剩余的解序列片段恰 为进一步证明算法的准确性，将例题测算结 好构成另一个子代(G)。在两个新构造的解序列 果文献[I4]提出的模拟退火算法(simulated an- 中，挖出解序列中重复加工的工件放进重组工件 nealing,.SA)、启发式模拟退火算法(heuristic simu- 池，再将重组工件池中的工件分别、依次插入到 lated annealing,HAS)和文献[22]总结的遗传算法 总加工时间最短的行内，直到所有的工件都被插 得出的结果进行比较。表4给出了MBGA的平 入到解序列中。重组工件池中的工件都是两个同 均PRD与其他算法的平均PRD的数值，MBGA 时存在的，在选取工件时，应同时将两个工件分 的平均PRD数值最小为0.21。相较于GA、SA和 别插入到两个构造的解序列中。 HAS,MBGA得出的最大完工时间最小
5 1 6 组合机制 2，先将工件−车间区块库中的区块 随机地复制到人工染色体中的空白位置，具体位 置由区块中首个工件分配到车间的概率和在机器 上排序的概率决定；然后根据分配和排序矩阵， 将未分配的工件插入到人工染色体的空白位置。 首先，随机地将区块 复制到染色体中的空 白位置 (如图 7) 具体位置应该根据首个工件 (工 件 1) 在各个位置的概率，运用轮盘赌来确定。剩 余的工件，还是分为两个阶段根据工件−车间和 工件−机器的概率矩阵用轮盘赌进行排序，直到 所有的工件都排序完成。 区块库 2 4 5 8 6 3 区块库 5 1 6 4 7 3 8 6 4 2 5 7 3 1 6 4 5 7 3 1 图 7 第 2 种组合机制 Fig. 7 The second combination mechanism 2.5 基因重组 通过基因重组发现改良的染色体，直到生成 最优的染色体，MBGA 改进了基因重组中的交叉 产生新的子代。染色体中每行的解序列片段是某 一车间内的工件加工顺序，所有工件恰好在 f 间 车间内加工完成。在基因交叉的过程中，以每个 车间内的工件加工序列 (即每行的解序列片段) 为交换单位，既能保留父代和每个车间的有效信 息，又能搜索每个车间的所有可能解。 适应 DJSP 的 MBGA 中，基因交叉的例子如 图 8 所示，挑选两个染色体为父代 (P1 ,P2 )，从一个 父代的解序列中随机选取 f/2 行解序列片段，剩余 的 f/2 行解序列片段从另一个父代中选取，按照原 行数重新构造解序列 (G1 )，剩余的解序列片段恰 好构成另一个子代 (G2 )。在两个新构造的解序列 中，挖出解序列中重复加工的工件放进重组工件 池，再将重组工件池中的工件分别、依次插入到 总加工时间最短的行内，直到所有的工件都被插 入到解序列中。重组工件池中的工件都是两个同 时存在的，在选取工件时，应同时将两个工件分 别插入到两个构造的解序列中。 8 6 4 1 3 7 5 2 8 6 4 2 5 7 3 f 1 1 f2 f1 f2 8 6 4 2 3 7 3 2 8 6 4 1 5 7 5 1 P1 P2 P1 f1 P2 f2 P2 f1 P1 f2 8 6 4 7 8 6 4 7 3,2 1,5 重组工件池 8 6 4 7 8 6 4 7 G1 G2 5 2 5 1 2 3 1 3 图 8 基因交叉 Fig. 8 Gene crossing 3 计算结果与分析 为了测试和验证 MBGA 的求解能力，在 Microsoft Visual Studio 2012 中的 C++上编写该算法 程序，并在 Window8、32 位系统、主频 3.40 的酷 睿 CPU、4 GB 内存的电脑上运行完成测试。本文 测试所用的数据来自 Taillard 中的生产车间调度 问题的基准实例，选取工件个数为 15、20、30 和 机器台数为 15、20 共 50 个组合进行比较分析。 比较标准是相对百分比偏差 (relative percentage deviation, RPD)，计算公式为 RPD = Alg−Min Min ×100 式中：Alg 表示运用 MBGA 获得最优的最大完工 时间；Min 表示基准实例所给出的最小化的最大 完工时间。 从 Taillard 中选择 50 种具有代表性的例题测 试该算法的寻优性能[22]。表 3 中是在不同的 n、 m 以及加工顺序下生成的 50 种实例组合下，每个 组合的平均 RPD 是对不同车间数 f=2, f=3, f=4, f=5 的最优 RPD 平均值。有一半以上的平均 RPD 为 0，证明一半以上的测算实例达到了目前已知 的最大完工时间的下限值。 为进一步证明算法的准确性，将例题测算结 果文献 [14] 提出的模拟退火算法 (simulated annealing，SA)、启发式模拟退火算法 (heuristic simulated annealing，HAS) 和文献 [22] 总结的遗传算法 得出的结果进行比较。表 4 给出了 MBGA 的平 均 PRD 与其他算法的平均 PRD 的数值，MBGA 的平均 PRD 数值最小为 0.21。相较于 GA、SA 和 HAS，MBGA 得出的最大完工时间最小。 第 2 期 裴小兵，等：改进区块遗传算法解决分布式车间调度问题 ·309·
·310· 智能系统学报 第16卷 表3实例测试结果 Table 3 Example test results 实例规模 实例规模 实例规模 实例 平均值 实例 平均值 实例 平均值 n m n m Tai01 15 15 0 Tai18 20 15 0 Tai35 30 15 0.53 Tai02 15 15 0.84 Tail9 20 15 0 Tai36 30 15 0.27 Tai03 尔 15 0 Tai20 20 15 0 Tai37 30 15 0 Tai04 15 15 0 Tai21 20 20 0.42 Tai38 30 15 0 Tai05 15 15 0 Tai22 20 20 0.31 Tai39 20 15 0 Tai06 15 15 0.52 Tai23 20 20 0 Tai40 30 15 0 Tai07 15 15 0.36 Tai24 20 20 0 Tai41 30 20 0 Tai08 15 0 Tai25 20 0 Tai42 30 20 0.24 Tai09 15 15 0.68 Tai26 20 20 0 Tai43 30 20 0 Tai1o 15 0.81 Tai27 20 20 0 Tai44 30 汤 0 Tail1 20 15 0.90 Tai28 20 20 0 Tai45 30 20 0 Tai12 20 15 3.00 Tai29 20 20 0.24 Tai46 30 20 0 Tai13 20 15 0.76 Tai30 20 20 0 Tai47 30 20 0 Tai14 20 0 Tai31 30 15 0 Tai48 30 20 018 Tail5 20 15 0 Tai32 30 15 0.15 Tai49 30 20 0 Tail6 20 15 0.12 Tai33 30 15 0 Tai50 30 20 0 Tail7 20 15 0.26 Tai34 30 15 0 表4不同算法的RPD Table 4 RPD of different algorithms 14 GA 12 --SA 平均相对偏差 算法 10 -·-HAS 0.21 MBGA 8 -MBGA 0.38 HSA 6 0.77 SA 2 5.54 GA 0 。一--m牛三-二” 20 50 100 200 图9显示了每个算法的平均RPD与工件数 工件数 的关系。从图中，能够清楚的看出，GA和SA的 图9 平均RPD与工件数的关系 RPD值随着工件数的增加而增加，HAS的RPD Fig.9 Relationship between average RPD and number of jobs 值随着工件数的增加而波动，而MBGA的RPD 14 …GA 比较稳定，且MBGA的RPD值均小于其他3个算 =■SA 0 =·HAS 法的RPD值，表明MBGA得到的解序列更加接 8 MBGA 近标准解序列。图10表示一批工件在不同数目 6 4 工作车间加工，4种算法的RPD值变化趋势。 0 GA的RPD随着车间数的增加而减小，SA、HAS 3 和MBGA的RPD值都随着车间数的增加而减 工厂数 小，表明MBGA中基于区块的人工染色体对原有 图10平均RPD与车间数的关系 GA的改进更适合分布式车间调度问题。综上可 Fig.10 Relationship between average RPD and the num- 得，MBGA具有较优的稳定性和准确性。 ber of jobs
表 3 实例测试结果 Table 3 Example test results 实例 实例规模 平均值 实例 实例规模 平均值 实例 实例规模 平均值 n m n m n m Tai01 15 15 0 Tai18 20 15 0 Tai35 30 15 0.53 Tai02 15 15 0.84 Tai19 20 15 0 Tai36 30 15 0.27 Tai03 15 15 0 Tai20 20 15 0 Tai37 30 15 0 Tai04 15 15 0 Tai21 20 20 0.42 Tai38 30 15 0 Tai05 15 15 0 Tai22 20 20 0.31 Tai39 20 15 0 Tai06 15 15 0.52 Tai23 20 20 0 Tai40 30 15 0 Tai07 15 15 0.36 Tai24 20 20 0 Tai41 30 20 0 Tai08 15 15 0 Tai25 20 20 0 Tai42 30 20 0.24 Tai09 15 15 0.68 Tai26 20 20 0 Tai43 30 20 0 Tai10 15 15 0.81 Tai27 20 20 0 Tai44 30 20 0 Tai11 20 15 0.90 Tai28 20 20 0 Tai45 30 20 0 Tai12 20 15 3.00 Tai29 20 20 0.24 Tai46 30 20 0 Tai13 20 15 0.76 Tai30 20 20 0 Tai47 30 20 0 Tai14 20 15 0 Tai31 30 15 0 Tai48 30 20 0.18 Tai15 20 15 0 Tai32 30 15 0.15 Tai49 30 20 0 Tai16 20 15 0.12 Tai33 30 15 0 Tai50 30 20 0 Tai17 20 15 0.26 Tai34 30 15 0 表 4 不同算法的 RPD Table 4 RPD of different algorithms 平均相对偏差 算法 0.21 MBGA 0.38 HSA 0.77 SA 5.54 GA 图 9 显示了每个算法的平均 RPD 与工件数 的关系。从图中，能够清楚的看出，GA 和 SA 的 RPD 值随着工件数的增加而增加，HAS 的 RPD 值随着工件数的增加而波动，而 MBGA 的 RPD 比较稳定，且 MBGA 的 RPD 值均小于其他 3 个算 法的 RPD 值，表明 MBGA 得到的解序列更加接 近标准解序列。图 10 表示一批工件在不同数目 工作车间加工， 4 种算法的 RPD 值变化趋势。 GA 的 RPD 随着车间数的增加而减小，SA、HAS 和 MBGA 的 RPD 值都随着车间数的增加而减 小，表明 MBGA 中基于区块的人工染色体对原有 GA 的改进更适合分布式车间调度问题。综上可 得，MBGA 具有较优的稳定性和准确性。 14 12 10 8 6 4 2 0 20 50 100 200 工件数 GA SA HAS MBGA RPD 图 9 平均 RPD 与工件数的关系 Fig. 9 Relationship between average RPD and number of jobs 2 3 4 5 工厂数 GA SA HAS MBGA 14 12 10 8 6 4 2 0 RPD 图 10 平均 RPD 与车间数的关系 Fig. 10 Relationship between average RPD and the number of jobs ·310· 智 能 系 统 学 报 第 16 卷
第2期 裴小兵，等：改进区块遗传算法解决分布式车间调度问题 ·311· 4结束语 WANG Ling,DENG Jin,WANG Shengyao.Survey on optimization algorithms for distributed shop scheduling[J]. 本文针对分布式工作车间调度问题，提出了 Control and decision,2016,31(1):1-11 MBGA。算法构建了分配区块库和排序区块库， [6]AZAB A.NADERI B.Greedy heuristics for distributed 保留和传递了精英染色体中的高频率基因链，统 job shop problems[J].Procedia CIRP,2014,20:7-12. 一考虑了排序过程中每个车间机器工作量的平衡 [7]ZHANG Rui,SONG Shiji,WU Cheng.A dispatching rule- 性和排序过程中工件加工的先后顺序。借助区块 based hybrid genetic algorithm focusing on non-delay schedules for the job shop scheduling problem[J].The in 库中的区块，运用两种组合机制构建了高质量的 ternational journal of advanced manufacturing technology, 人工染色体；一种组合机制应用区块通过先分配 2013,67(1/2/3/4):5-17. 后排序的顺序构建了一类人工染色体，另一种组 [8]GAREY M R,JOHNSON D S,SETHI R.The complexity 合机制先在人工染色体中填充区块，同步进行工 of flowshop and jobshop scheduling[J].Mathematics of 件的分配和排序两个阶段，再将剩余的工件按照 operations research,1976,1(2):117-129 先分配后排序的顺序构建第二类人工染色体，增 [9]WAGNER H M.An integer linear-programming model for 加了人工染色体的多样性。改进区块遗传算法中 machine scheduling[J].Naval research logistics quarterly, 1959,6(2):131-140 的基因重组大幅度地改良了当前代的人工染色 [10]JIA HZ,NEE A Y C,FUH J Y H,et al.A modified ge- 体，保留了父代和每个车间的有效信息，又具有 netic algorithm for distributed scheduling problems[J]. 搜索每个车间的能力。算例测算表明，该算法具 Journal of intelligent manufacturing,2003,14(3/4): 有较好的稳定性和准确性。 351-362 MBGA有效地解决了分布式生产车间调度问 [1l]王和敏，谷森，魏志谦，等.基于混合遗传算法的Job Shop 题，未来还可以尝试深入研究，如改变假设条件， 问题研究与实现[).新技术新工艺，2017(8)69-73. 当每个车间的工件的加工能力存在差异时，求解 WANG Hemin,GU Miao,WEI Zhiqian,et al.The Re- 最优的调度方案。 search and implement of Job Shop problem based on hy- brid genetic algorithm[J].New technology new pro- 参考文献： cess.2017(8):69-73. [12]NADERI B.AZAB A.Modeling and heuristics for [1]JIA HZ,FUH J Y H,NEE A Y C,et al.Web-based multi- scheduling of distributed job shops[J].Expert systems functional scheduling system for a distributed manufactur- with applications,2014,41(17):7754-7763. ing environment[J].Concurrent engineering,2002,10(1): [13]CHAOUCH I,DRISS O B,GHEDIRA K.A modified ant 27-39. colony optimization algorithm for the distributed job shop [2]谢志强，周含笑，桂忠艳，等.基于拟关键路径的二车间 scheduling problem[J].Procedia computer science,2017, 综合调度算法[.计算机科学，2013,40(4)：193-198 112:296-305. XIE Zhiqiang,ZHOU Hanxiao,GUI Zhongyan,et al.In- [14]NADERI B,AZAB A.An improved model and novel tegrated scheduling algorithm of two workshops based on simulated annealing for distributed job shop problems[J]. ACPM[J].Computer science.2013,40(4):193-198. The international journal of advanced manufacturing tech- [3]BARGAOUI H,DRISS O B,GHEDIRA K.Minimizing nology,2015,81(1/2/3/4):693-703. makespan in multi-factory flow shop problem using a [15]杨敬松，夏秀峰，崔广才.混合遗传算法在分布式车间 chemical reaction metaheuristic[C]//Proceedings of 2016 作业调度中的应用[】.计算机工程与应用，2005， IEEE Congress on Evolutionary Computation.Vancouver, 41(19:213-215,225. Canada.2016. YANG Jingsong,XIA Xiufeng,CUI Guangcai.The Dis- [4]谢志强，郭禾，苏文秀，等.存在多工序同时结束的多车 tribution method of planning and scheduling based on a 间逆序综合调度算法).吉林大学学报（工学版），2018， hybrid genetic algorithm[J].Computer engineering and 48(2):578-587 applications,.2005,41(19y:213-215,225. XIE Zhiqiang,GUO He,SU Wenxiu,et al.Reversal se- [16]高雪瑶，谭涛，张春祥.遗传退火算法的模型相似性计 quence integrated scheduling algorithm of multiple work- 算方法[J].哈尔滨工程大学学报，2020,41(7) shop with multi-procedures ended together[J].Journal of 1073-1079. Jilin University (Engineering and Technology Edition), GAO Xueyao,TAN Tao,ZHANG Chunxiang.Method of 2018,48(2):578-587. calculating model similarity based on genetic annealing [5]王凌，邓瑾，王圣尧.分布式车间调度优化算法研究综 algorithm[J].Journal of Harbin Engineering University, 述U.控制与决策，2016,31(1)：1-11. 2020,41(7):1073-1079
4 结束语 本文针对分布式工作车间调度问题，提出了 MBGA。算法构建了分配区块库和排序区块库， 保留和传递了精英染色体中的高频率基因链，统 一考虑了排序过程中每个车间机器工作量的平衡 性和排序过程中工件加工的先后顺序。借助区块 库中的区块，运用两种组合机制构建了高质量的 人工染色体；一种组合机制应用区块通过先分配 后排序的顺序构建了一类人工染色体，另一种组 合机制先在人工染色体中填充区块，同步进行工 件的分配和排序两个阶段，再将剩余的工件按照 先分配后排序的顺序构建第二类人工染色体，增 加了人工染色体的多样性。改进区块遗传算法中 的基因重组大幅度地改良了当前代的人工染色 体，保留了父代和每个车间的有效信息，又具有 搜索每个车间的能力。算例测算表明，该算法具 有较好的稳定性和准确性。 MBGA 有效地解决了分布式生产车间调度问 题，未来还可以尝试深入研究，如改变假设条件， 当每个车间的工件的加工能力存在差异时，求解 最优的调度方案。 参考文献： JIA H Z, FUH J Y H, NEE A Y C, et al. Web-based multifunctional scheduling system for a distributed manufacturing environment[J]. Concurrent engineering, 2002, 10(1): 27–39. [1] 谢志强, 周含笑, 桂忠艳, 等. 基于拟关键路径的二车间 综合调度算法 [J]. 计算机科学, 2013, 40(4): 193–198. XIE Zhiqiang, ZHOU Hanxiao, GUI Zhongyan, et al. Integrated scheduling algorithm of two workshops based on ACPM[J]. Computer science, 2013, 40(4): 193–198. [2] BARGAOUI H, DRISS O B, GHÉDIRA K. Minimizing makespan in multi-factory flow shop problem using a chemical reaction metaheuristic[C]//Proceedings of 2016 IEEE Congress on Evolutionary Computation. Vancouver, Canada, 2016. [3] 谢志强, 郭禾, 苏文秀, 等. 存在多工序同时结束的多车 间逆序综合调度算法 [J]. 吉林大学学报(工学版), 2018, 48(2): 578–587. XIE Zhiqiang, GUO He, SU Wenxiu, et al. Reversal sequence integrated scheduling algorithm of multiple workshop with multi-procedures ended together[J]. Journal of Jilin University (Engineering and Technology Edition), 2018, 48(2): 578–587. [4] 王凌, 邓瑾, 王圣尧. 分布式车间调度优化算法研究综 述 [J]. 控制与决策, 2016, 31(1): 1–11. [5] WANG Ling, DENG Jin, WANG Shengyao. Survey on optimization algorithms for distributed shop scheduling[J]. Control and decision, 2016, 31(1): 1–11. AZAB A, NADERI B. Greedy heuristics for distributed job shop problems[J]. Procedia CIRP, 2014, 20: 7–12. [6] ZHANG Rui, SONG Shiji, WU Cheng. A dispatching rulebased hybrid genetic algorithm focusing on non-delay schedules for the job shop scheduling problem[J]. The international journal of advanced manufacturing technology, 2013, 67(1/2/3/4): 5–17. [7] GAREY M R, JOHNSON D S, SETHI R. The complexity of flowshop and jobshop scheduling[J]. Mathematics of operations research, 1976, 1(2): 117–129. [8] WAGNER H M. An integer linear-programming model for machine scheduling[J]. Naval research logistics quarterly, 1959, 6(2): 131–140. [9] JIA H Z, NEE A Y C, FUH J Y H, et al. A modified genetic algorithm for distributed scheduling problems[J]. Journal of intelligent manufacturing, 2003, 14(3/4): 351–362. [10] 王和敏, 谷淼, 魏志谦, 等. 基于混合遗传算法的 Job Shop 问题研究与实现 [J]. 新技术新工艺, 2017(8): 69–73. WANG Hemin, GU Miao, WEI Zhiqian, et al. The Research and implement of Job Shop problem based on hybrid genetic algorithm[J]. New technology & new process, 2017(8): 69–73. [11] NADERI B, AZAB A. Modeling and heuristics for scheduling of distributed job shops[J]. Expert systems with applications, 2014, 41(17): 7754–7763. [12] CHAOUCH I, DRISS O B, GHEDIRA K. A modified ant colony optimization algorithm for the distributed job shop scheduling problem[J]. Procedia computer science, 2017, 112: 296–305. [13] NADERI B, AZAB A. An improved model and novel simulated annealing for distributed job shop problems[J]. The international journal of advanced manufacturing technology, 2015, 81(1/2/3/4): 693–703. [14] 杨敬松, 夏秀峰, 崔广才. 混合遗传算法在分布式车间 作业调度中的应用 [J]. 计算机工程与应用, 2005, 41(19): 213–215, 225. YANG Jingsong, XIA Xiufeng, CUI Guangcai. The Distribution method of planning and scheduling based on a hybrid genetic algorithm[J]. Computer engineering and applications, 2005, 41(19): 213–215, 225. [15] 高雪瑶, 谭涛, 张春祥. 遗传退火算法的模型相似性计 算方法 [J]. 哈尔滨工程大学学报, 2020, 41(7): 1073–1079. GAO Xueyao, TAN Tao, ZHANG Chunxiang. Method of calculating model similarity based on genetic annealing algorithm[J]. Journal of Harbin Engineering University, 2020, 41(7): 1073–1079. [16] 第 2 期 裴小兵，等：改进区块遗传算法解决分布式车间调度问题 ·311·
·312· 智能系统学报 第16卷 [17]CHANG P C,HUANG W H,WU JL,et al.A block min- PEI Xiaobing,ZHANG Chunhua.An improved puzzle- ing and re-combination enhanced genetic algorithm for based genetic algorithm for solving permutation flow- the permutation flowshop scheduling problem[J].Interna- shop scheduling problems[J].CAAI transactions on intel- tional journal of production economics,2013,141(1): ligent systems,2019,14(3):541-550. 45-55. [22]CHAOUCH I,DRISS O B,GHEDIRA K.A survey of [18]CHANG P C,CHEN Menghui.A block based estimation optimization techniques for distributed job shop schedul- of distribution algorithm using bivariate model for ing problems in multi-factories[Cl//Proceedings of the 6th scheduling problems[J].Soft computing,2014,18(6): Computer Science On-line Conference.Cham,Germany, 1177-1188 2017. [19]裴小兵，于秀燕.改进猫群算法求解置换流水车间调度 作者简介： 问题.智能系统学报，2019,14(4)769-778 裴小兵，教授，博士，天津工业工 PEI Xiaobing,YU Xiuyan.Improved cat swarm optimiza- 程学会理事，主要研究方向为生产调 tion for permutation flow shop scheduling problem[J]. 度、精益生产。发表学术论文40余篇。 CAAI transactions on intelligent systems,2019,14(4): 769-778. [20们张敏，汪洋，方侃.基于改进区块进化算法求解置换流 水车间问题[J].计算机集成制造系统，2018,24(5)： 1207-1216. 孙志卫，硕士研究生，主要研究方 ZHANG Min,WANG Yang,FANG Kan.Improved 向为生产调度、智能算法。 block-based evolutionary algorithm for solving permuta- tion flowshop scheduling problem[J].Computer integ- rated manufacturing system,2018,24(5):1207-1216. [21]裴小兵，张春花.应用改进区块遗传算法求解置换流水 车间调度问题.智能系统学报，2019,14(3)：541-550. 2021中国粒计算与知识发现学术会议 2021 China Granular Computing and Knowledge Discovery Conference 由中国人工智能学会主办、中国人工智能学会粒计算与知识发现专委会协办、国际粗糙集学会支持，华 东交通大学承办的2021年中国粒计算与知识发现学术会议（第21届中国粗糙集与软计算学术会议、第 15届中国粒计算学术会议、第9届三支决策学术会议)将于2021年8月20-22日在“英雄城一江西南昌” 召开。现将会议有关征文事宜通知如下，热忱欢迎相关研究人员踊跃投稿并参会。 征文范围（包括但不限于）： 1)粗糙集与软计算；2)粒计算理论及其应用：3)三支决策模型与分析；4)知识发现与数据挖掘。 重要日期： 投稿截止日期：2021年3月25日 录用通知日期：2021年6月10日 终稿提交日期：2021年6月25日 会议举办日期：2021年8月20-22日 投稿要求及详情参见网址：https://easychair.org/conferences/?conf=cgckd202l 投稿与会务咨询： 钱老师(13775075661)：余老师(13755776891) 会务邮箱：cgckd2021@163.com 通信地址：江西省南昌市双港东大街808号华东交通大学软件学院(330013) 会议网站：htp://cgckd2021.ecjtu.edu.cn
CHANG P C, HUANG W H, WU J L, et al. A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem[J]. International journal of production economics, 2013, 141(1): 45–55. [17] CHANG P C, CHEN Menghui. A block based estimation of distribution algorithm using bivariate model for scheduling problems[J]. Soft computing, 2014, 18(6): 1177–1188. [18] 裴小兵, 于秀燕. 改进猫群算法求解置换流水车间调度 问题 [J]. 智能系统学报, 2019, 14(4): 769–778. PEI Xiaobing, YU Xiuyan. Improved cat swarm optimization for permutation flow shop scheduling problem[J]. CAAI transactions on intelligent systems, 2019, 14(4): 769–778. [19] 张敏, 汪洋, 方侃. 基于改进区块进化算法求解置换流 水车间问题 [J]. 计算机集成制造系统, 2018, 24(5): 1207–1216. ZHANG Min, WANG Yang, FANG Kan. Improved block-based evolutionary algorithm for solving permutation flowshop scheduling problem[J]. Computer integrated manufacturing system, 2018, 24(5): 1207–1216. [20] 裴小兵, 张春花. 应用改进区块遗传算法求解置换流水 车间调度问题 [J]. 智能系统学报, 2019, 14(3): 541–550. [21] PEI Xiaobing, ZHANG Chunhua. An improved puzzlebased genetic algorithm for solving permutation flowshop scheduling problems[J]. CAAI transactions on intelligent systems, 2019, 14(3): 541–550. CHAOUCH I, DRISS O B, GHEDIRA K. A survey of optimization techniques for distributed job shop scheduling problems in multi-factories[C]//Proceedings of the 6th Computer Science On-line Conference. Cham, Germany, 2017. [22] 作者简介： 裴小兵，教授，博士，天津工业工 程学会理事，主要研究方向为生产调 度、精益生产。发表学术论文 40 余篇。 孙志卫，硕士研究生，主要研究方 向为生产调度、智能算法。 2021 中国粒计算与知识发现学术会议 2021 China Granular Computing and Knowledge Discovery Conference 由中国人工智能学会主办、中国人工智能学会粒计算与知识发现专委会协办、国际粗糙集学会支持，华 东交通大学承办的 2021 年中国粒计算与知识发现学术会议（第 21 届中国粗糙集与软计算学术会议、第 15 届中国粒计算学术会议、第 9 届三支决策学术会议）将于 2021 年 8 月 20−22 日在“英雄城—江西南昌” 召开。现将会议有关征文事宜通知如下，热忱欢迎相关研究人员踊跃投稿并参会。 征文范围（包括但不限于）： 1）粗糙集与软计算；2）粒计算理论及其应用；3）三支决策模型与分析；4）知识发现与数据挖掘。 重要日期： 投稿截止日期：2021 年 3 月 25 日 录用通知日期：2021 年 6 月 10 日 终稿提交日期：2021 年 6 月 25 日 会议举办日期：2021 年 8 月 20−22 日 投稿要求及详情参见网址：https://easychair.org/conferences/?conf=cgckd2021 投稿与会务咨询： 钱老师（13775075661）；余老师（13755776891） 会务邮箱：cgckd2021@163.com 通信地址：江西省南昌市双港东大街 808 号华东交通大学软件学院（330013） 会议网站：http://cgckd2021.ecjtu.edu.cn ·312· 智 能 系 统 学 报 第 16 卷