基于关联规则的作业车间调度问题改进遗传算法研究

2022-01-12乔东平柏文通文笑雨李浩王雅静

河南理工大学学报(自然科学版) 2022年2期

乔东平，柏文通，文笑雨，李浩，王雅静

（1.郑州轻工业大学机电工程学院，河南郑州 450002；2.河南省机械装备智能制造重点实验室，河南郑州 450002）

0 引言

中国制造2025的明确提出加快了工业化与信息化的深度融合，将推动传统制造业升级转型，实现智能制造［1］。新一轮工业革命的兴起，促使信息技术迅速融入到工业制造过程中，工厂积累了大量的生产数据，这些数据呈现出不规则性和多样性［2］。传统作业车间调度问题（job-shop scheduling problem，JSP）研究往往忽略了工业生产中历史调度数据的潜在价值，造成大量数据资源浪费。因此，研究历史调度数据与智能调度算法对求解作业车间调度问题的影响具有重要的现实意义。

由于遗传算法不受限制性条件约束，在求解作业车间调度问题中得到了广泛应用［3］。采用遗传算法求解作业车间调度问题时，初始种群质量会对遗传算法求解效率产生一定影响，初始种群质量越高，算法求解效率越高，越能提高遗传算法的整体性能［4］。目前主要采用随机初始化的方法生成初始种群，很难确保初始种群质量，从而会出现求解算法运行效率低、易早熟和运算周期长等问题［5］。为了提高遗传算法的初始解质量，国内外学者对此开展了一系列研究。杜修力等［6］将均匀设计运用到连续变量的函数中，通过对搜索区域均匀网格化以优化初始种群，虽然在一定程度上解决了遗传算法进化缓慢的问题，但是该方法操作复杂度随着问题规模的增大呈指数增大；周帅等［7］通过能动法和无延迟法生成的新个体替换随机初始种群中较差的个体，从而提高初始种群质量，但是效果不明显；赵志伟［8］提出一种基于反向学习的自适应差分进化算法，该算法结合标准进化算法的初始种群A和反向学习产生的种群B，选择适应度最好的N个个体作为求解算法的初始种群，并引进控制参数自适应机制和变异参数自适应机制，有效改善了算法的性能；I.Poikolainen等［9］提出一种基于聚类的种群初始化方法，优化求解算法的初始种群，通过局部搜索算法对局部空间进行搜索，并利用聚类算法增强算法全局搜索能力；陈思远等［10］提出一种基于指针网络改进遗传算法种群模型，该模型以随机策略生成的种群S和指针网络解集T，按比例取其适应度值高的子集作为初始种群，通过改善遗传算法初始种群结构提高算法性能；李林瑛等［11］通过设计禁止区间法的启发式构造算法生成初始种群，避免了不可行个体的产生，互换染色体处于全等待的基因位置，提高了算法的局部搜索能力；王建华等［12］针对遗传算法的随机搜索问题，引入正交试验的均衡原则，利用均衡分散原则对随机生成的初始种群进行优化，提高了算法初始种群质量。

目前提出的方法有效提高了算法的求解速率，但仍存在以下问题［13］：（1）初始种群质量提高效果并不明显；（2）算法运行周期长，例如基于反向学习的方法，在每次迭代过程都进行反向学习，通过计算所有个体的适应度值来选取最优者；（3）采用优化算法生成较优个体替代种群中较差的个体，算法求解效率提升并不明显。

针对上述问题，本文提出基于关联规则的改进遗传算法，该算法通过关联规则获取基因序列上的频繁工序块，将频繁工序块插入子代基因序列中结合禁忌矩阵生成初始种群。以此为基础，设计3种交叉方式，根据不同待交叉个体选择不同交叉方式，充分发挥不同交叉算子的特性。变异过程引入分段海明距离，使种群的变异过程具有方向性，以加快算法对最优解的搜索。最后通过基准案例验证改进遗传算法的有效性。

1 作业车间调度问题描述

作业车间调度问题可以描述为：在m台机器上加工n个工件，每个工件都有m道工序，且每道工序的加工机器以及加工时间都是已知的。问题的约束条件为：（1）加工开始时，所有工件均处于待加工状态，所有机器均处于空闲状态；（2）不同工件的工序之间没有先后顺序约束，同一工件的工序之间有先后顺序约束；（3）同一时刻，一个工件只能在一台机器上加工，并且机器一旦开始加工中间不能中断。

本文相关符号的定义：m台机器表示为Mk=｛M1，M2，M3，…，Mm｝；n个工件表示为Ji=｛J1，J2，J3，…，Jn｝；Oij为第i个工件的第j道工序；sik为工件i在机器k上的开工时间；tik为工件i在机器k上的加工时间；cik为工件i在机器k上的完工时间，M是一个无穷大的数。本文的主要优化目标是使作业车间调度问题方案的最大完工时间Cmax最小化。模型描述如下。

式（1）为目标函数，表示最小化最大完工时间，即各机器上加工工件的最大完工时间最小；式（2）为加工工序的前后约束关系；式（3）为工序的非阻塞约束关系；式（4）为加工工序开始/结束的时间约束；式（5）为工件的开工时间均大于0；式（6）和（7）分别为对aihk和xijk系数的定义。

2 基于关联规则的改进遗传算法设计

以遗传算法为基础，结合关联规则、频繁工序块、禁忌矩阵和分段海明距离等概念，提出基于关联规则的改进遗传算法。具体求解算法流程如图1所示，步骤如下。

图1 JSP求解算法流程图Fig.1 JSP solving algorithm flowchart

步骤1设置AR-GA算法参数：迭代次数Nmax，混合式比例a，最小支持度minsup，最小置信度minconf，交叉概率Pc，变异概率Pm。

步骤2随机选取历史调度数据集规模的50%作为测试集，寻找基因序列中的相邻优势工序组。

步骤3采用关联规则寻找历史调度数据中具有关联性的相邻工序组组成频繁工序块。

步骤4判断是否找到频繁工序块，如果没有，跳转步骤2，否则，继续步骤5。

步骤5构造禁忌矩阵，对禁忌矩阵中对应频繁工序块中的工序进行标记。

步骤6将整个频繁工序块插入子代基因序列中，并结合禁忌矩阵生成新的基因序列，基于关联规则的改进遗传算法生成初始种群的比例为a，随机初始化策略生成初始种群规模为（1-a）。

步骤7执行锦标赛选择策略。

步骤8按照交叉概率Pc选取待交叉个体，根据含有频繁工序块的待交叉个体数量，选择相应的交叉方式；如果两个交叉个体都具有频繁工序块，进行两点交叉；如果两个交叉个体只有一个具有频繁工序块或两个交叉个体都不具有频繁工序块，则进行POX交叉。

步骤9利用分段海明距离引导种群进行变异操作。

步骤10更新频繁工序块信息。

步骤11判断是否达到结束条件，若未达到，跳转步骤7～11，否则，结束循环并输出最优解。

2.1 编码和解码

本文采用文献［14］提出的基于工序的编码方式，即基因序列由n×m个基因组成，基因序列中所有的基因采用对应的工件号表示，工件号出现的次数表示该工件的第几道工序。以表1给出的一个3×3的JSP案例为例，随机生成一条基因序列［132132213］，其中，1，2，3分别表示工件J1，J2和J3，例如基因序列中第1基因位上的1表示工件J1的第一道工序，第4基因位上的1表示工件J1的第2道工序，第8基因位上的1表示工件J1的第3道工序。

表1 一个3×3 JSP案例Tab.1 An example of 3×3 JSP

采用文献［15］提出的插入式贪婪式解码算法，即主动调度方法，从左到右依次读取染色体上的工序排列顺序，如果工序Oij是机器k分配的第一道工序，则机器k直接加工工序Oij；如果机器k已经安排加工其他工件，则依次检查该机器安排加工的第一个加工工序之前的空闲时间以及各个工序之间空闲时间段，将工序Oij插入到满足条件的空闲时间段。对基因序列［132132213］解码后的基因序列为［132231231］，解码过程如图2所示。

图2 基于工序编码的解码过程Fig.2 Decoding process based on operation encoding method

2.2 种群初始化方法

在遗传算法求解作业车间调度问题中，初始解的优劣影响算法的收敛速率和求解质量。通过种群初始化获得较高质量的初始种群，可以达到改善算法求解效率的目的。本文通过关联规则寻找基因序列中的频繁工序块，结合禁忌矩阵优化算法的初始种群。为了保持初始种群的多样性，初始种群采用混合式生产方式，基于关联规则的改进遗传算法生成初始种群规模的比例为a，随机初始化方法生成初始种群规模的比例为（1-a）。

2.2.1 关联规则

关联规则是数据挖掘中一种常用方法，可有效挖掘基因序列中的优良工序组合，提高算法求解性能［16］。本文利用关联规则分析基因序列中工序排列顺序，探索工序间排列顺序存在的相关性，寻求具有关联的优势工序组。

关联规则（association rules）基本概念［17］是一种包括先导（left-hand side，LHS）和后继（righthand side，RHS）的论断，如果购买了先导项集，则很有可能对后继项集感兴趣，这表明项集之间存在一定关联。在关联规则中有两个重要参考指标，即支持度和置信度［18］，其中，支持度表示获得的项集是否有效，置信度表示获得项集的有效程度。

本文引入关联规则寻找基因序列中具有关联性的相邻工序组，令历史调度数据集中所有工序的集合为P=｛p1，p2，…，pn×m｝，其中n×m为基因序列的长度；L=｛l1，l2，…，ln×m｝表示在基因序列中对每一个基因位置上的工序统计集合，li的规模为历史调度数据集中基因序列的数量集，liP；基因序列中第i个基因位置上的一个工序子集表示为Xi=｛x1，x2，…，xλ｝，Xili，λ＜n×m，xλ表示在该基因位置上满足最小支持度的工序；工序xλ的发生在一定程度上引起相邻工序yλ的发生，即xλyλ，xλ>P，yλ>P，且xλyλ=。

本文引入支持度确保获得的相邻工序组合有效，支持度（support（xλyλ））表示基因序列中某一基因位置上工序xλ和相邻基因位置上工序yλ同时出现的总次数占population的比例，即

本文引入置信度确保相邻工序组合的有效程度，令置信度（confidence（xλyλ））表示基因序列中某一基因位置上工序xλ出现频率满足支持度的前提下，其相邻基因位置上工序yλ也出现的概率，即

式中：population为历史调度数据集的规模；sup（xλ）为各基因序列中某一基因位置上工序xλ发生的总次数；sup（xλyλ）为各基因序列中某一基因位置上工序xλ和相邻基因位置上工序yλ同时发生的次数；support（xλyλ）为工序xλ和相邻工序yλ之间的支持度大小；confidence（xλyλ）为工序xλ和相邻工序yλ之间的关联性程度。

2.2.2 频繁工序块

本文提出的频繁工序块（frequent process blocks）概念为：在基因序列中满足最小支持度和最小置信度的相邻工序组称为频繁工序块。通过关联规则分析基因序列，发现工序排列顺序之间的相关性，寻找具有关联性的相邻工序组组成频繁工序块，并将频繁工序块作为一个整体直接插入子代基因序列，提高算法初始种群质量。需满足约束条件如下：在频繁工序块中一道工序或者几道相邻工序同时出现的频率满足支持度的条件下，其相邻的下一道工序发生概率满足置信度条件；要求频繁工序块中相邻工序数目不小于2。

如果关联规则中的支持度和置信度都大于设置的最小支持度和最小置信度的阈值，则称为强关联规则［19］，为了确保频繁工序块的有效性，本文讨论的关联规则均为强关联规则。本文设置的最小支持度阈值minsup=s1，最小置信度阈值minconf=c1。利用关联规则寻找频繁工序块的操作流程如下。

步骤1随机选取历史调度数据集规模的50%作为测试集寻找相邻优势工序组。

步骤2从基因序列中的第一个基因位置开始计算各个工序的出现次数，筛选出满足最小支持度的工序。

步骤3如果该基因位置上的工序不满足条件，继续筛选下一道相邻基因中各工序的出现次数。

步骤4如果找到support（xλyλ）≥s1的工序，分别计算该工序的下一道相邻基因位置上的工序是否满足confidence（xλyλ）≥c1，如果满足，只保留置信度较高的相邻工序，并对基因序列中满足最小支持度和最小置信度的相邻工序进行标记，否则跳到步骤3。

步骤5将步骤4获得的最小支持度与最小置信度的相邻工序作为一个频繁工序块；在测试集中判断步骤4获得的频繁工序块是否满足最小支持度，如果不满足，将该频繁工序块输出，跳转步骤3；否则，计算该频繁工序块的下一道相邻工序是否满足confidence（xλyλ）≥c1。

步骤6如果confidence（xλyλ）＜c1，输出步骤4得到的频繁工序块，并计算该基因位置上的工序是否满足support（xλyλ）≥s1，如果满足跳转步骤4；否则，则将该道工序添加到频繁工序块中。

步骤7以此类推，直至基因序列中的工序全部统计。

步骤8判断频繁工序块的数目是否大于等于1，如果是，输出所有满足条件的频繁工序块并结束循环；否则，跳转步骤1。

2.2.3 初始种群的生成

考虑到频繁工序块中相邻工序的固定位置和工序之间的排列顺序对初始种群生成的影响，构建禁忌矩阵MJ。在禁忌矩阵中，行表示工件，列表示工序，禁忌矩阵中第i行第j列的数字表示工件i的第j道工序，如图3所示。

初始种群生成的方法：如图3（a）所示，从禁忌矩阵MJ中找出对应各个频繁工序块中的工序并进行标记，被标记的工序不能被选择；填充基因序列中第一个基因位置时，首先判断第O1列中是否有未被标记的工序，可以得到O11，O21，O31和O41没有被标记，随机选择其中一道工序放到该基因位置上并标记选中的工序。如图3（b）所示，在填充第6位基因时，先判断第O1列中是否有未被标记的工序，发现第O1列中只有O31未被标记，故选择工序O31填充到第6基因位置上；在填充第7位基因时，第O1列中的工序全部被标记，再去判断第O2列中是否有未被标记的工序，可以得到工序O32和O42未被标记，随机选择其中一道工序放到该基因位置上并对选中的这道工序进行标记。如图3（c）所示，填充第9位基因时，第O1列和第O2列中的工序已经全部被标记，再判断第O3列中的工序是否有未被标记的工序，可以得到工序O23和O33未被标记，则随机选择其中一道工序放到该基因位置上，并对选中的这道工序进行标记，剩下一道工序插入到最后一个基因位置后并对其标记。如图3（d）所示，将禁忌矩阵中所有未被标记的工序根据列的先后顺序，依次插入到基因序列中的空基因位置上，生成初始种群。

图3 初始种群的生成流程Fig.3 Generation process of initial population

2.3 选择

选择操作的本质是促使种群中优良基因得以保留，进而加快算法对最优解或近似最优解的探索。锦标赛选择算法具有更好的收敛性和较低的计算复杂性［20］，因此本文采用锦标赛算法。锦标赛操作流程：（1）随机选择两个基因序列；（2）选择适应度值高的个体进行交叉操作，另一个个体继续放回待选种群中；（3）重复以上操作，直至填满交叉池。

2.4 交叉

初始种群采用混合式生成方法，其部分个体是随机生成的，是基因序列中没有被标记的频繁工序块，所以交叉操作时会出现3种情况：（1）选择的两个个体都具有频繁工序块；（2）选择的两个个体只有一个具有频繁工序块；（3）选择的两个个体都不具有频繁工序块，详细交叉策略如下。

当出现情况（1）时，为了防止优秀基因组合被破坏，采用两点交叉操作［21］，如图4所示，即对基因序列上的每一个频繁工序块中第一个工序位置进行标记，然后随机选择其中2个标记点之间的基因片段进行交换。如果基因序列中只有一个频繁工序块，就进行单点交叉方式［22］，以此降低因交叉操作对优良基因的破坏。

图4 两点交叉Fig.4 Two point crossover

当出现情况（2）时，采用POX交叉操作［23］，如图5所示，因交叉操作产生的Child3，Child4子代个体，进行子代适应度值大小计算。如果子代个体的适应度值小于父代个体适应度值，则产生子代个体不含频繁工序块；反之，则Child3，Child4个体基因序列对应父代频繁工序块基因位置上的相邻工序作为新的频繁工序块，并且更新频繁工序块信息。通过上述产生新的频繁工序块增加遗传算法的局部搜索能力。

图5 POX交叉Fig.5 POX crossover

当出现情况（3）时，采用POX交叉操作，且经过POX交叉操作产生的子代基因序列不含频繁工序块，其作用是增加种群的多样性，见图6。

图6 POX交叉且Job=｛1，2｝Fig.6 POX crossover and Job=｛1，2｝

2.5 变异

为了使种群朝着优化的趋势变异，在遗传算法的变异操作中引入“分段海明距离”，即取两个基因序列中某一段基因片段相异的基因个数作为分段海明距离［24］。由于频繁工序块对子代种群质量有着重要影响，本文选取基因序列中从第一个频繁工序块的首块工序到最后一个频繁工序块的尾块工序之间的基因片段计算个体之间的海明距离。如果基因序列中只有一个频繁工序块，则选取基因序列中从第一个频繁工序块的首块工序到基因序列的最后一道工序之间的基因片段计算个体之间的海明距离。采用分段海明距离引导变异操作时，迭代前期种群中个体之间差异较大，分段海明距离较大，需要变异的基因位置多，加强了算法的局部搜索能力；迭代后期种群中个体之间差异变小，分段海明距离较小，需要变异的基因位置少，增强了算法的稳定性。

从种群中选取一个适应度值最高的个体与待变异个体计算分段海明距离。如果被选中个体的分段海明距离为0，则该个体不再进行变异操作；如果被选中的个体的分段海明距离不为0，则随机选择其中几个（偶数）相异点进行基因互换，以此降低两个个体之间的分段海明距离，见图7。

图7 变异操作Fig.7 Mutation operation

3 结果与分析

通过以上分析，采用C++编程语言对本文所提出的算法进行设计验证，选用JSP问题基准算例中若干组中小型的实验进行测试，其中包含30个LA问题算例和2个FT算例。实验环境：64位Windows7操作系统的计算机，CPU主频为3.3 GHz，内存为4 GB。整个实验过程中，AR-GA算法的相关参数设置为：（1）JSP问题的种群规模为500；（2）最小支持度为0.35；（3）最小置信度为0.75；（4）混合式比例a=80%；（5）交叉概率Pc=0.8；（6）变异概率Pm=0.1；（7）每个JSP问题实例独立运行20次；（8）最大迭代次数为100。本文符号定义与解释如表2所示。

表2 符号定义与解释Tab.2 Symbol definition

采用AR-GA算法对32个JSP问题算例进行测试，实验结果如表3所示，为了对比AR-GA算法的初始种群能否更好地提高种群解质量和种群稳定性，在表3中同时给出了传统GA算法求解JSP问题测试结果。

表3 案例测试结果Tab.3 Case test results

AR-GA算法的相对误差ε和传统GA算法的相对误差ε′计算式为

为了更好地验证AR-GA算法的可行性和有效性，本文测试了32个基准算例，表格3中的LA15，LA16，LA17，LA21，LA22，LA24，LA25，LA26，LA27，LA28，LA29，LA30和FA20基准案例计算结果表明，与传统GA相比较，AR-GA算法在最优解、平均最优解、相对误差和程序运行时间等几个方面获得了更好的近似最优解，并且随着解决问题规模增大，AR-GA算法的优势越明显。

图8为不同规模案例的收敛过程，迭代初期，AR-GA算法的初始解质量明显优于传统GA算法的，表明通过关联规则改善遗传算法初始种群的方法是有效可行的；迭代前期，AR-GA算法的最优解曲线和平均解曲线相比传统GA算法下降速率更快，AR-GA算法表现出收敛速度快和全局搜索能力强等特点；迭代后期，AR-GA算法获得最优解的迭代次数以及最优解的质量要优于传统GA算法的，在获得最优解后，AR-GA算法最优解曲线不出现反弹且平均最优解曲线仍继续下降，AR-GA算法表现出较强的稳定性和寻优能力。因此，提高算法初始种群质量和个体之间的关联性，可在相同时间内搜索更多有价值的解子集，从而能够获得更好的最优解。

图8 不同规模案例的收敛曲线Fig.8 Convergence curves of different scale cases

由图9可知，AR-GA算法的相对误差和程序运行时间优于传统GA算法，前者说明AR-GA算法的稳定性更优，后者说明AR-GA算法求解速率更快，其主要原因在于AR-GA算法利用关联规则找到基因序列中具有关联性的优势工序组合，提高了算法初始解质量，改善了算法的稳定性。图10显示了AR-GA算法求解不同规模案例的计算结果。