第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,k<n, j>k (5) Ck,i ⩾ Cj,i + pk,i − M(2+ Xk, j,i −Yj,r −Yk,r),∀r,i,k<n, j>k (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},∀j<n,k>j,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·