基于SO-GP的智能车间组合调度规则挖掘

马丽萌，乔 非，马玉敏，刘 鹃

(同济大学 电子与信息工程学院，上海 201804)

0 引言

随着信息科技的迅速发展，制造业已经成为国民经济的支柱产业。生产调度问题是制造业管理的核心内容，也是提高企业核心竞争力的关键，其研究主要包括基于智能搜索和基于调度规则两种方法。智能搜索算法如禁忌搜索[1]、蚁群算法[2]、遗传算法(Genetic Algorithm, GA)[3]、人工免疫系统[4]等，在解决经典的作业车间和流水车间调度问题时可以找到良好的最优近似解，然而当问题规模较大时计算成本巨大，不能满足智能车间实时调度的要求。相比之下，调度规则易于实现、求解的时间复杂度较低并能对动态变化及时做出响应[5-6]，比较适合求解智能车间这种高度复杂动态环境下的调度问题。然而传统的简单调度规则只利用了有限的生产调度过程信息，其优化性能一般较差[7]。一些研究人员针对经典的作业车间问题研究了组合调度规则，这些规则是单一调度规则的启发式组合，旨在继承前者优点，研究结果表明，组合调度规则在调度质量方面好于单个调度规则[7-8]。

根据组合规则的结构特征，可将其分为线性加权组合式调度规则和非线性组合调度规则。前者是根据具体的车间环境，以不同的权重对简单规则进行线性组合，这种方法的缺点是受限于所选调度规则的调度性能，而且无法解决规则之间关联性问题；非线性组合规则对规则的组合不局限于简单的线性加权，具有更灵活的形式，通过合适的组合可以改善线性加权规则的局限性。

组合规则的设计方法包括手工方法和智能方法。早期大多使用手工方法对已有规则进行组合，所得到的规则形式简洁，便于理解，但其需要根据领域知识进行手工设计，过程十分耗时，而且所生成的规则一般不具普适性。用于调度规则设计的智能方法主要有进化算法[9]、数据挖掘[10]、遗传规划(Genetic Programming, GP)[11]等，其中遗传规划的学习机制简单且表现形式灵活，比较适合对调度规则进行挖掘设计。Nguyen等[12]采用GP算法为单目标作业车间调度问题生成新调度规则，并通过实验验证了集成系统和机器属性的表示可以提高演化规则的质量；Tay等[13]采用GP算法生成的调度规则解决多目标柔性作业车间问题；Duraseviĉ等[14]采用GP算法为具有随机性能指标的无关机器环境的并行机调度问题自动设计调度规则，实验结果表明，采用GP算法生成的调度规则的整体性能优于传统调度规则。

上述方法在解决以智能车间为代表的高复杂度生产系统的调度问题时具有局限性，主要表现在：①上述方法大多采用数学模型对生产环境建模，为了方便建模而对一些环境特性进行简化或忽略，使得约束条件相对实际环境有很大程度的松弛，例如将车间的初始状态设为零初始状态，导致对实际生产车间的建模不准确，而且对不同的调度目标往往需要重新设计测试用例；②由于智能车间具有结构复杂、单/批量加工方式交错、随机性等特点，导致其难以用数学模型描述。

针对上述问题，本文将智能车间离散仿真[15]与GP算法结合，以避免对智能车间调度问题进行数学建模；并以简单启发式规则为基础，提出一种组合式调度规则挖掘方法。该方法挖掘得到的规则在保留简单启发式规则复杂度低、易于实施的同时，优化制造系统整体性能，满足了智能车间生产调度规模大、复杂性高的特点。为了进一步避免GP进化过程产生的无意义调度规则所带来的挖掘时间成本，本文对构成GP算法的终止集进行归一化改进。

1 基于SO-GP的调度规则挖掘框架

1.1 调度规则的表达

根据优化的调度目标分类，简单启发式规则一般包括基于工件的等待时间、基于工件的加工周期、基于工件的交货期和基于生产线均衡负载等规则，这些简单的启发式规则利用有限的生产调度过程信息对工件的加工顺序进行排序，例如最早交货期(Earliest Due Date，EDD)是通过对工件的交货期进行排序，优先选择具有最早交货期的工件进行加工。

本文组合规则由函数节点和终止符节点以树的结构构成。其中终止符节点是构成二叉树的叶子节点，在文中表示为简单启发式调度规则；函数节点为构成二叉树的非叶子节点，用于将简单规则组合起来，包括加、减、乘、除等操作函数。如图1所示为树形组合规则的例子，其中EDD、最短剩余加工时间(Smallest Remaining Processing Time, SRPT)是简单启发式规则，对该二叉树进行中序遍历，得到组合规则的表达式为EDD+(EDD-SRPT)。

1.2 智能车间调度规则挖掘框架

基于仿真优化与遗传规划(Simulation Optimization-Genetic Programming，SO-GP)的智能车间调度规则挖掘框架如图2所示，可划分为调度规则离线挖掘模块和在线调度模块两部分，本文主要对调度规则离线挖掘模块进行研究，以优化调度规则库，支持后期的在线调度。离线挖掘过程包括基于GP算法的挖掘模块和基于SO适应度值的评价模块。

GP算法挖掘模块主要完成组合规则挖掘的进化过程。首先确定用于生成调度规则(GP个体)的终止符集和函数集，对其编码生成树形结构的组合调度规则；然后初始化种群并将生成的规则输入SO适应度值评价模块得到对应的性能指标，将其作为GP算法个体的适应度值来促进种群进化(包括个体的选择和复制、交叉、变异等操作)，完成进化后即得到优异的组合调度规则。

基于SO适应度值评价模块对GP算法生成的组合规则适应度进行评价。根据智能车间的生产线数据生成智能车间生产线仿真模型，通过将模型的调度规则设置为GP算法挖掘模块生成的组合调度规则，得到某一生产状态下生成的各个调度规则对应的性能指标。

2 SO-GP算法设计

GP算法是Koza在1992年借鉴GA提出的一种进化计算方法。在GP算法设计中，个体的构造采用树形结构，由终止符节点和函数节点构成，相比于GA固定长度的二进制字符串，它是一种更为灵活的可变分层结构，能够独立表示各个变量之间的算术或逻辑关系。GP算法设计包括函数集和终止符集的确定、种群进化过程以及适应度函数的确定。

2.1 组合规则的构成

2.1.1 终止符集的确定

启发式调度规则是车间调度问题中常用的调度方法，它是按照工件特征属性集中的某个属性或多个属性的组合来计算得到工件的优先级。本文对新的调度规则的挖掘是基于简单的启发式规则，将简单启发式规则作为终止符集，通过函数集中的函数操作产生新的调度规则。本文所用终止符集如表1所示。

表1 终止符集

然而，直接使用这些规则作为终止符集，在进行函数操作时可能会生成没有意义的规则。例如生成的规则为EDD+SRPT*EDD，加法操作符两边的量纲不统一，理论上无法进行加法操作，虽然在进化过程中这些无意义的规则必然会淘汰，但是会影响整个进化的过程。为了避免这种情况，本文对这些简单规则进行了归一化处理，如式(1)所示，将工件i在该规则下的优先级作为该规则的属性值参与计算。

(1)

式中：kmax，kmin分别为待排序工件中由简单调度规则确定的工件属性k的最大值和最小值；ki为工件i的属性k的值。Rk,i为经过归一化处理后的简单启发式调度规则，即归一化后，由属性k确定的工件i的优先级。

以SRPT规则为例，归一化后的SRPT规则所确定的工件i的优先级为

式中：RPTmax，RPTmin分别为待排序工件中剩余加工时间的最大值和最小值；RPTi为工件i的剩余加工时间；RRPT,i为归一化后，由属性RPT确定的工件i的优先级。

2.1.2 函数集的确定

与GP算法解决其他的优化问题类似，本文函数集选择加减乘除4种基本操作符以及一些规则中常见的最大、最小函数，其中当除法操作的除数为0时返回1，其他情况返回正常计算值。

2.2 种群的进化过程

2.2.1 初始种群的生成

初始种群的生成方法有多种，常用的有完全法、生长法和混合法3种[16]。其中，完全法保证生成的个体扩展到最大深度，生长法使生成的个体具有多样的结构，混合法则综合了完全法和生长法的优点。因此，本文采用混合法产生初始种群，即初始种群中的一半个体用完全法生成，另一半个体用生长法生成。

GP个体用二叉树的结构表示，个体生成过程：在函数集和终止符集中随机产生根节点，然后随机产生子树作为根节点的子节点，子节点若为终止符，则终止该分支的生长；若为函数操作符，则继续生长；以此类推，直至达到最大深度。

2.2.2 遗传操作

GP算法进化过程包括个体的选择、复制、交叉、变异等操作。本文采用竞争选择法对种群进行选择和复制，同时为了保证最优的个体能够生存到下一代，采用精英保留策略保留最优个体。

(1)交叉操作 针对复制的每一对个体，若产生一个随机数小于交叉概率，则执行交叉操作，即在该对个体中随机选取某节点作为交叉点，相互交换以交叉点为根节点的子树，得到两个子代。

(2)变异操作 针对每一个个体，若产生一个随机数小于变异概率，则执行变异操作，即在该个体中随机选择除根节点之外的节点作为变异点，删掉以变异点为根节点的子树，然后在变异点随机生成新的子树，新子树的深度不能超过最大深度。

2.3 基于SO的适应度函数设计

本文采用的SO方法是将仿真的输出作为优化算法中的评价值，其主体流程如图2中基于SO的适应度评价部分。将仿真的输出输入优化模块，在优化算法中通过比较仿真运行得到的输出结果来判断解的优劣，从而做出进一步优化。由于离散事件建模方法在智能车间生产线建模方面有较大优势，本文通过对智能车间生产线建立离散事件仿真模型来配合GP算法挖掘调度规则。

2.3.1 智能车间离散事件仿真模型的设计

离散事件仿真模型的设计包括数据模块设计和仿真模块设计。数据模块设计是将生产线车间模型数据经过分类处理后整理成几个基本数据表，如表2所示；仿真模块主要通过对数据模块提供的数据进行建模，描述整个生产线加工的逻辑关系，并对事件进行控制，包括数据导入模块、初始化模块、流程控制模块、调度规则模块、数据统计输出模块等。为了能与GP算法结合，除了上述模块完成生产线的基本流程外，还需用函数运算模块对GP算法的个体进行解码。

表2 生产线车间模型基本数据表

2.3.2 适应度函数

GP进化过程中每代得到的表达为树形的个体可以通过中序遍历解码成相应的调度规则。本文将解码得到的规则输入智能车间离散事件仿真模型来计算个体适应度值，具体过程为：每次计算前先对仿真模型进行初始化；当有机器空闲时，将该机器的工件等待队列按照所输入的规则计算优先级并排序，对优先级最高的工件进行加工；经过一个调度周期后，将得到的性能指标作为个体适应度值，个体的适应度越好，被选择并保存到下一代种群中的概率越大；照此规则不断进行优胜劣汰。

本文智能车间生产线模型与GP算法之间通过数据库进行数据交互。每当GP算法进化得到一代个体，就触发仿真模型从数据库读取生成的规则并计算适应度值。对于GP种群个体适应度值的计算，由于进化过程中每一个GP个体都要输入到仿真模型中计算适应度值，而仿真模型一次只能计算一个个体的适应度值，为了提高计算效率，本文采用并发计算方式，即同时启动多个仿真模型计算种群中不同个体的适应度值。另外，因为每一代GP种群规模均有限且确定，所以仿真可以计算出每一代个体的适应度值。然后，将计算得到的每代个体适应度值通过数据库反馈给GP算法进行优胜劣汰，如此往复，直到满足终止条件，最后生成优异的规则。

从上述过程可以看出，虽然仿真优化的方式较费时，但是SO-GP算法的挖掘过程可以离线进行，挖掘出的优异规则在实际在线使用时与传统简单规则的时间成本相差不多，能够满足智能车间调度的实时性需求。GP算法设计流程图如图3所示。

3 实验设计和结果分析

3.1 仿真案例的设计

本文采用MiniFAB模型作为仿真模型进行实验验证。MiniFAB模型是Kempf博士由Intel公司的半导体生产线提炼出的模型[17]，其由3个加工区、5台设备组成，共有6个加工工序，工艺流程如图4所示，其中Ma，Mb为多卡并行加工设备，最大加工批量为4卡。模型层运行局部图如图5所示，解码模块的逻辑控制图如图6所示。

3.2 实验参数设置

(1)仿真模型参数的设置

MiniFAB模型每次的仿真时间为30天，设置生产线上生产3种产品，以固定间隔投料方式进行投料，每种产品的投料数在[10,20]之间均匀分布。为了提高所挖掘规则的鲁棒性，随机生成5个不同的生产线初始状态构成训练集，对组合调度规则进行挖掘。另外，为了提高种群的进化速度，采用并发计算的方式，在仿真层同时运行多个生产线仿真模型，每次训练向每个仿真模型输入同一条生产线状态数据来初始化仿真模型生产状态。

(2)GP算法参数的设置

采用数据包络分析效率评价[18]方法，对常见的简单启发式规则的效率(启发式规则对多种生产性能的兼顾程度)进行评价，根据评价结果选用EDD，SRPT，CR，FSVCT 4个启发式规则构成本案例的终止符集。经过测试，GP算法的参数设置如表3所示。其中，为了避免所生成的规则过于复杂，控制初始种群中个体的最大深度不超过3。

表3 GP算法的参数设置

3.3 实验结果与分析

3.3.1 对终止符归一化的分析

为了验证对终止符即简单规则进行归一化处理的必要性，本文分别以平均加工周期(Mean Cycle Time, MCT)最小与准时交货率(On-time Delivery Rate, ODR)最大为调度目标设计实验进行分析。

(1)以平均加工周期最短为目标

以MiniFAB为模型，MCT最短为目标，分别对终止符进行和不进行归一化处理，迭代相同次数后，每种情况下各挖掘3个GP规则，GP表示进行归一化处理后生成的规则，GP_N表示不进行归一化处理生成的规则，如表4所示。

表4 以MCT最短为目标挖掘的调度规则

在MiniFAB仿真模型上遍历这6种调度规则，记录30天后采用不同调度规则产生的MCT的性能。绘制20条测试样本(即20个不同的生产线初始状态)在不同调度规则下的生产性能对比图，如图7所示，其MCT指标平均值如表5所示。

表5 不同调度规则下的MCT指标平均值 h

(2)以准时交货率最大为目标

以MiniFAB为实验模型，ODR最大为目标，分别通过对终止符集进行和不进行归一化处理生成规则，如表6所示。

表6 以ODR最大为目标挖掘的调度规则

在MiniFAB仿真模型上遍历这6种调度规则，记录30天后采用不同调度规则产生的ODR的性能。绘制20条测试样本在不同调度规则下的ODR指标，如图8所示，其ODR指标的平均值如表7所示。

表7 不同调度规则下的ODR指标平均值 %

由图7和图8可以看出，在相同迭代次数下，对于不同的调度目标，终止符集进行归一化处理后挖掘出的调度规则比不进行归一化处理挖掘出的调度规则整体性能都要好，而3个归一化处理后挖掘的调度规则在性能方面均较接近，3个没有归一化处理挖掘出的调度规则的性能也较接近。从性能的平均值来看，对于MCT来说，归一化处理后挖掘出的规则比不进行归一化挖掘出的规则性能提高23.6%；对于ODR，归一化处理后挖掘出的规则比不进行归一化挖掘出的规则性能提高7.5%，以上结果说明对终止符集进行归一化处理能够有效提高GP算法的挖掘效率。

3.3.2 对长期性能指标的分析

由于对终止符集进行归一化处理的有效性，以下对不同调度目标下的调度规则挖掘均采用归一化的终止符集。为验证SO-GP算法挖掘的调度规则对提高长期指标的有效性，本文分别以MCT最小和ODR最大为目标设计实验进行分析。

(1)以平均加工周期最短为目标

以MiniFAB为实验模型，以MCT最短为目标进行规则挖掘，选取表4中的3个生成规则GP1，GP2，GP3。

在MiniFAB仿真模型上遍历8种调度规则，即3种GP生成的规则+4种候选基本规则+线性组合式调度规则，线性组合调度规则的参数权重为SRPT∶EDD∶CR∶FSVCT=0.64∶0.10∶0.22∶0.04，权重的确定方法参考文献[19]，确定记录30天后采用不同调度规则所产生的MCT的性能。20条测试样本在不同调度规则下的MCT性能对比如图9所示，其MCT指标平均值如表8所示。

表8 不同调度规则下的MCT指标平均值 h

由图9可见，对于MCT，由GP算法挖掘出的3个调度规则在性能方面比较接近，而且性能比简单启发式规则和线性加权组合规则的性能整体好。由表8可见，对于MCT，GP1规则的性能比SRPT规则提高33%，比CR规则提高45%，比EDD规则提高54%，比FSVCT规则提高58%，比线性组合式提高30%。

(2)以准时交货率最大为目标

以MiniFAB为实验模型，以ODR最大为目标进行规则挖掘，选取表6中的3个生成规则GP1，GP2，GP3。

与本节实验(1)一样，在MiniFAB仿真模型上遍历这8种调度规则(其中线性组合调度规则的参数权重为SRPT∶EDD∶CR∶FSVCT=0.23∶0.56∶0.09∶0.12)，记录30天后采用不同调度规则的ODR性能。20条测试样本在不同调度规则下的ODR性能对比如图10所示，其ODR平均值如表9所示。

表9 不同调度规则下的ODR指标平均值 %

由图10可见，对于ODR，由GP算法挖掘出的3个调度规则在性能方面比较接近，而且性能整体上比简单启发式规则和线性加权组合规则好。由表9可见，对于ODR，GP1规则性能比SRPT规则提高5.17%，比EDD规则提高5.76%，比CR规则提高8.62%，比FSVCT规则提高5.72%，比线性组合式规则提高3.43%。

从以上分析可以看出，GP算法挖掘出的调度规则对长期性能指标优化具有有效性。

3.3.3 对短期性能指标的分析

为验证SO-GP算法挖掘的调度规则对短期性能指标优化的有效性，分别以日平均移动步数(Mean Daily Movement, MDayMOV)和瓶颈设备利用率最大为目标设计实验进行分析。

(1)以日均移动步数最大为目标

以MDayMOV最大为目标进行规则的挖掘，最后选取所生成的3个优异规则如表10所示。

表10 以MDayMOV最大为目标挖掘的调度规则

在MiniFAB仿真模型上遍历以下8种调度规则，即3种GP生成的规则+4种候选基本规则+线性组合调度规则，线性组合调度规则的参数权重为SRPT∶EDD∶CR∶FSVCT=0∶0∶0∶1，相当于FSVCT规则，记录8 h后采用不同调度规则产生的MDayMOV性能。20条测试样本在不同调度规则下的MDayMOV性能对比如图11所示，其MDayMOV指标平均值如表11所示。

表11 不同调度规则下的MDayMov指标的平均值

由图11可以看出，对于MDayMOV，由GP算法挖掘出的3个调度规则在性能方面比较接近，而且整体上比简单启发式及线性加权规则的性能好。由表11可见，对于MDayMOV，GP1规则的性能比SRPT提高20.76%，比EDD规则提高11.67%，比CR规则提高19.97%，比FSVCT规则提高6.91%，比线性加权规则提高6.91%。

(2)以瓶颈设备利用率最大为目标

以MiniFAB为实验模型，瓶颈设备Me的利用率(OEE_Me)最大为目标进行规则挖掘，最后选取所生成的3个优异规则如表12所示。

表12 以OEE_Me最大为目标挖掘的调度规则

与本节实验(1)一样，在MiniFAB仿真模型上遍历这8种调度规则(其中线性组合调度规则的参数权重为SRPT∶EDD∶CR∶FSVCT=0.22∶0.33∶0.21∶0.24)，记录8 h后采用不同调度规则产生的OEE_Me的性能。20条测试样本在不同调度规则下的OEE_Me性能对比如图12所示，其OEE_Me指标平均值如表13所示。

表13 不同调度规则下的OEE_Me指标的平均值 %

由图12可以看出，对于瓶颈设备利用率，由GP算法挖掘出的3个调度规则在性能方面比较接近，虽然性能整体上比简单启发式规则和线性加权规则好，但是提高并不明显。由表13可见，对于瓶颈设备利用率，GP1规则的性能比SRPT规则提高1.08%，比EDD规则提高0.33%，比CR规则提高1.19%，比FSVCT规则提高0.83%，比线性加权规则提高0.61%。从平均值来看，GP挖掘的规则对性能的提高也不明显，这是因为瓶颈设备的利用率在任何规则下的性能都很高，而GP在其性能已经很高的情况下仍然能够有所提升，不过这种性能提升空间不大的生产指标在多数情况下没有提升的必要。

从以上分析可以看出，SO-GP算法挖掘出的调度规则对短期性能指标的提高具有有效性。

本文采用GP算法与仿真相结合的方法对调度规则进行挖掘。GP算法计算量大，耗时长，而且使用仿真计算适应度值的过程比较费时，本文使用SO-GP算法的目的在于产生优秀的新规则来补充在线调度规则库，并通过离线计算获取挖掘规则。由于挖掘出的优异规则是有关各个属性的多项式，其在在线实时调度中的时间开销与传统的简单规则相当，并不会明显提升在线调度时间。

4 结束语

本文提出一种将离散仿真与遗传规划算法结合的调度规则挖掘方法，在挖掘过程中，为了提高GP算法的挖掘效率，对构成GP个体的简单规则进行归一化处理，并通过实验验证相同时间下，对终止符集归一化处理后挖掘的组合规则性能优于不作处理挖掘的规则性能。以MiniFAB为对象，分别使用MCT最短与ODR最大为调度目标，分析SO-GP算法挖掘的规则与简单启发式调度规则和线性加权组合规则的性能，实验表明SO-GP算法能够有效提高长期性能指标。然后，分别以MDayMOV最大和瓶颈设备利用率最大为目标验证SO-GP算法对提高短期性能指标的有效性。由于采用SO-GP算法对调度规则的挖掘为离线进行，实际中使用所挖掘的规则与传统的简单规则的时间成本相差不多，满足智能车间实时调度的要求，为智能车间调度问题的求解提供了解决思路。

本文采用SO-GP方法挖掘调度规则时，候选规则只从常见的规则中通过效率分析得到，而实际有几十种启发式规则，今后可全面对其进行分析并增加候选规则的数目。