基于SOMA的多目标优化作业车间自适应调度研究

周竞涛，蒋腾远，袁 乔，路朝留

（1.上海航天壹亘智能科技有限公司，上海 201306；2.西北工业大学 机电学院，西安 710072）

0 引言

随着产品需求的多样化、定制化、个性化以及市场竞争的日趋激烈，产品的及时交付成为一个企业维持竞争力的有效途径，而生产调度对产品的及时交付至关重要[1]。为了能够更好的模拟作业车间的生产调度过程，相对于仅考虑作业车间单目标调度问题，同时针对多个调度目标进行优化调度研究更加贴近实际的生产过程，因此针对作业车间多目标调度问题的研究具有重要的意义，成为作业车间调度的备受关注的研究方向[2～9]。

针对作业车间的多目标调度研究，国内外学者面向不同的作业车间优化目标，采用了多种方法进行研究，能够更为有效的符合实际的生产过程，如：魏巍等[2]以加工成本、加工质量及制造工期为目标，采用改进的强度Pareto进化算法对作业车间进行优化调度；刘爱军等[3]将最小化拖期惩罚和加工时间作为调度目标，采用纵横协同的多种群遗传算法完成了工艺路线和加工顺序的优化；Hamed等[6]针对碳排放量和总延迟时间作为调度目标，运用改进的多目标遗传算法完成了作业车间的调度问题；朱传军等[7]以调度稳定性和鲁棒性为优化目标，提出混合重调度策略，并运用多目标差分进化算法求解调度问题；Rong-Hwa H等[8]以时间跨度、作业延迟及分批成本为优化目标，运用改进的蚁群算法完成多目标调度求解；Hadi Mokhtari等[9]以总完成时间、系统利用率以及总能源成本为目标，结合增强进化算法和全局标准，完成问题的求解过程。通过对上述文献的研究发现，现有的多目标柔性车间调度问题都是针对车间扰动的某一个方面或者某一特定的目标进行调度研究，通过算法优化得到的结果是各个目标的优化值，而不是权衡多个目标的全局调度优化结果。

因此，本文针对柔性作业车间调度问题，以最小化生产成本、最小化生产周期以及交货紧张度因子作为调度目标，根据作业车间中发生问题的不同，采用动态的自适应调度策略，赋予调度目标不同权值，实现针对扰动的自适应调度过程，获取权衡多个目标的全局最优解。在求解优化问题的各类方法中，自组织迁移算法（Self-organizing Migrating Algorithm，SOMA）是由Zelinka和Lampinen根据动物的觅食行为共同开发的一种基于合作-竞争的进化学习，由于具有收敛速度快、调节参数少、并行协同好、自适应等优点，被广泛用于多个领域[10，11]，其中文献[12]将改进的SOMA运用在流水车间的调度问题，显示了很好的求解最优解的能力。本文通过对SOMA算法进行改进，采用动态步长，提高算法搜索性能；引入二次插值提高种群的多样性，从而提高了SOMA算法的自适应能力，以此提高算法的性能。最后通过案例仿真，验证了提出方法的有效性。

1 问题描述及数学模型

1.1 问题描述

本文研究的自适应调度问题可以描述为：已有调度在车间进行生产情况下，某时刻发生随机扰动引起生产环境的改变，进而影响到正常生产情况，需要根据扰动进行自适应的调度，对生产资源进行重新的分配，生产新的调度方案，以降低随机扰动的影响直至所有加工任务完成。

生产车间的调度问题可描述为：车间正在执行的任务集合为：task={τ1，τ2，...，τm}，其中n为车间总任务数目；制造系统中包含的机床集合为：machine={1，2，...，m}，，其中m为车间中机床的总数量；加工任务τi由一系列工序po={poi1，poi2，...，poinb}，其中nbi表示任务τi的工序数，poki，j表示任务τi的第j道工序在机床k上加工。

1.2 多目标优化模型

大多数文献采用生产周期、加工成本等作为指标进行调度方案的评估，这些指标虽然能够在很大程度上反映调度方案的优劣，但是没有考虑到不同任务的优先程度和紧迫程度。本文通过对已有文献的分析，分别考虑生产成本、生产周期和交货紧张度因子三个目标，用以表达调度方案的成本、时间和任务的紧迫程度，其数学模型如下：

最小化生产成本

其中：Cost表示生产车间总成本，Costready表示加工准备成本，Costprocess表示加工成本，Costearly表示提前完工惩罚费用，Costdelay表示拖期完工惩罚费用，crki，j表示任务τi的第j道工序在机床k上加工的准备成本系数，cpi，j表示任务τi的第j道工序在机床k上加工成本系数，ceki，j表示任务τi的第j道工序在机床k上加工提前完工惩罚费用系数，cdki，j表示任务τi的第j道工序在机床k上加工拖期完工惩罚费用系数，Dki，j表示任务τi的第j道工序在机床k上加工的截止日期。

最小化生产周期

交货紧张度因子

约束：

式(4)表示工件的加工时间不为负；式(5)表示每一道工序的准备时间在加工时间之前；式(6)表示上一道工序完成才能进行下一道工序的加工；式(7)表示任意确定时刻，机器k不能同时加工任意两个不同的工件，其中Ykab，ij=1表示任务τa的工序b先于任务τj的工序j在机床k上加工；式(8)表示任一任务不能的加工不能超过去截止日期。

生产调度的优化过程是使各优化目标达到一种平衡，获取生产过程近似最优解，因此将上述三种优化目标进行整合，形成单一整体目标。在进行优化目标整合前，需要对单一优化目标进行归一化处理，因此采用下式对优化目标进行归一化处理：

其中α为优化目标归一化后的结果，bmax表示优化目标的最优值，bmin表示优化目标的最劣值，b表示优化函数的当前值。

基于以上归一化后的三个优化目标，采用权系数的方法将其归一化为单一调度目标，如下式：

1.3 自适应权重因子

为了能够适应生产过程中针对不同扰动进行自适应调度，需要根据不同的扰动赋予调度目标不同的权重，从而使调度模型能够适应扰动，给出较为合理的生产调度方案。因此，本文针对任务拖期、紧急订单以及设备故障三种典型情况给出相应的权重赋予结果，用以指导自适应调度过程，具体情况如下：

Situation1：当车间进行正常生产时，任务的优先级已经确定，此时选用的策略模型为最小生产周期与最少生产成本，此时赋予三个调度目标的权重分别为ω1=0.5，ω2=0.5，ω3=0。

Situation2：当有紧急订单插入时，紧急插入的订单一般具有较短的交货期，因此，应优先考虑紧急订单的调度问题，此时，调度的策略以交货紧张度因子为首要调度目标，再配合最小生产周期和最少生产成本进行任务的调度，此时三个调度目标的权重分别为ω1=0.25，ω2=0.25，ω3=0.5。

Situation3：发生故障时，首先需要对故障的影响进行分析，以当前任务的最少生产成本和最小生产周期为主要调度目标，再配合任务交货紧张度因子进行调度，此时三种的权重分别为ω1=0.4，ω2=0.4，ω3=0.2。

针对不同的扰动，运用不同的权重进行调度规划，生成更加符合实际的生产调度方案，从而实现作业车间扰动的自适应调度。

2 基于改进SOMA的调度算法

为了能够提高SOMA算法的自适应能力，本文将自适应步长与二次插值结合使用，利用自适应步长提高算法的自适应勘探能力，避免算法的早熟，利用二次插值提高SOMA的多样性，进而增大寻优的概率。其中算法中的每一个个体相当于调度过程中的一个方案，优化目标则作为算法的适应度函数，用于对个体进行评估，实现最后的优化过程。

2.1 编码与解码

为了能够将实际的调度问题与优化算法相结合，编码是非常关键的问题。为了保证所得染色体能够与调度结果相对应，以及调度过程中工序不发生混乱，本文借鉴[刘爱军，柔性作业车间多目标动态调度]中提出的加工工序与加工机器相融合的两层编码方法，提出一种三层染色体编码方法，第一层编码用于表达产品的工序，第二层编码用与表达加工产品相应工序所用到的机器。如在3×3问题中，假设给定的染色体为[321122331]，其中1代表工件τ1，2代表工件τ2，3代表工件τ3，每件工件都有三道工序，所以每个工件出现三次。机器层用于表达加工该工序的可用机器集合中，如m31是表达用于加工工序po31可用的机床集合。第三层的种群层是将所表达的工序机器与种群初始化得到的结果对应起来，根据最后形成的最优种群对染色体进行调整，从而实现对工序的优化。

2.2 自适应步长设置

在SOMA个体迁移过程中，步长step表示个体向最优解方向搜索范围的大小，在标准的SOMA算法中，其推荐值为0.11。但在实际的仿真应用过程中发现，算法运行的初期，可以采用较大的步长，提高算法的勘探能力，在运行的后期，采用较小的步长，加强算法的局部搜索能力，在保证提高算法收敛速度的同时，有效利用算法的局部搜索能力。因此，本文采用文献[12]提出的线性递减步长策略，令初始步长即为最大步长Stepmax，终止步长即为最小步长Stepmin，且在每次评估过后进行步长的自适应更新，自适应步长定义为：

其中，Count表示当前评价次数，Sum Count表示品鉴次数上限的估计值，根据文献[12]的实验结果，这里Stepmax设为0.7，Stepmin设为0.4。

2.3 自适应个体迁移运动

与其他进化算法不同的是，SOMA算法用一个在[0，1]之间的实数PRT表示扰动，用于决定个体是否向领导者迁移。PRT是一个敏感的参数，其可以决定算法的收敛速度，当值越大时，算法收敛越快，一般将PRT的值设为[0.7，1]。用PRT决定个体迁移的过程是通过产生的随机数与PRT进行比较，进而构建扰动矩阵，其构建过程如下：

当扰动矩阵Ai，j的值为1时，表示个体可以向领导者迁移，当扰动矩阵Ai，j的值为0时，个体不允许向领导者迁移。其移动过程模仿生物觅食活动中的协作行为，生成一个新的位置，其具体的位置迁移过程如下：

其中，xti，j表示个体的新位置，表示个体的原位置，表示领导者的原位置，s∈[0，step]，Ai，j表示扰动矩阵。为了能够提高种群的多样性，本文参考文献[11]引入二次插值用于解决扰动矩阵Ai，j为0的情况，进而提高种群的多样性，增大获取最优解的概率。

当扰动矩阵Ai，j为0时，选择种群中的最优个体（领导者）和两个随机个体，利用二次插值方法创建一个新的个体，其公式如下：

其中R1表示领导者，R2和R3是从种群中随机选择的个体，如果新的个体比原个体的适应度值要好，则用该个体代替原个体，实现个体向最优结果的迁移过程。

2.3 改进SOMA基本流程

为此，根据以上提出的综合自适应步长与自适应个体迁移运动的改进SOMA，该算法的基本流程如下：

步骤1：参数定义。根据要解决的问题，定义算法必要的参数，如：PathLength，NP（个体数），ML（最大循环数），PRT，Stepmax，Stepmin等。

步骤2：粒子初始化，在解空间内初始化产生NP个粒子，ML=0。

步骤3：根据目标函数评价每一个体所对应的适应度值。

步骤4：确定最优的适应度值的个体作为领导者，其他的个体作为迁移者。

步骤5：根据扰动矩阵创建新的个体，如果Ai，j=1，用公式X创建新的个体位置，并评价其适应度值，如果由于当前个体，则用新个体取代当前个体，否则不变；如果Ai，j=0，则转步骤6。

步骤6：利用二次插值公式创建新个体，并评估其适应度值，如果优于当前个体适应度值，则取代当前个体，否则不变。

步骤7：对新的种群进行评估，选择出新的领导者和迁移者。

步骤8：判断结束条件，如果未达到转到步骤5，否则执行步骤9。

步骤9：算法结束。返回最优个体值，或者根据情况返回所有个体值。

3 算例分析

3.1 算法性能比较

根据参考文献[13]，选择一下3个测试函数：

1）Ackley函数

2）Schwefel函数

3）Rana函数

为了能够方便进行优化效果比较，参数设置参照文献[12]：所有测试函数的维数均为30。群体规模均为20，适应度函数的评估次数上限为500，函数优化结果保留6为小数，同时令每个测试函数独立运行10次，取其平均值。

参照文献[12]，SOMA中的参数设置为PRT=0.1，PathLength=3，Step=0.11。基于改进的SOMA的参数设置为Stepmax=0.7，Stepmin=0.4，其余参数同基本SOMA。在处理器为Intel Celeron CPU N2940，主频为1.83GHz，内存为3.89GB的硬件条件下应用MATLAB2016编写仿真试验程序。图1～图3给出了两种SOMA算法收敛曲线。通过图中可以看出，改进SOMA算法在开始时，其收敛速度与基本SOMA算法保持一致，随着迭代次数的增加，其收敛速度逐渐快于基本SOMA算法，这主要是因为采用线性递减的步长策略使算法具有更好的局部搜索能力，以及采用二次插值提高了种群的多样性，使算法能够跳出局部最优解。通过对比图1～图3可以看出，改进的SOMA算法优于基本SOMA。

图1 Ackley函数动态寻优曲线

图2 Schwefel函数动态寻优曲线

图3 Rana函数动态寻优曲线

表3 工件加工准备时间、准备成本系数、加工时间、加工成本系数

3.2 算例分析

某机加车间有6台机床组成，需要生产4种零件，完成每个零件的加工需要三道工序，每道工序可以选择在三台不同的设备上加工完成。零件的交货期，提前、拖期惩罚如表1所示，其中工件的准备时间、准备成本系数、加工时间、加工成本系数。

表1 染色体编码

表2 工件交货期、提前、拖期惩罚系数

其中每组数据机床加工相应工序的准备时间、准备时间成本系数、加工时间、加工时间成本系数，如2，3；2，5表示工件1的第一道工序在机床1加工的生产准备时间为2，准备时间成本为3，加工时间为2，加工成本为5。

本次实验算法的基本参数如下S t e pmax=0.7，Stepmin=0.4，PRT=0.1，PathLength=3。通过算法进行仿真，获得目标函数的最优值0.790078，其中成本为122，生产时间为66，从仿真的结果可以看出，任务1的松弛度最大为2，如果出现扰动时，可以优先调整任务1以适应扰动。其调度的甘特图如图4所示。

图4 4×6算例的甘特图

4 结语

为解决针对生产车间动态扰动的多目标调度问题，本文采用自适应调度策略与改进的SOMA算法相结合的方法对调度问题进行自适应优化。首先，根据任务的调度目标，生成当前场景下的调度策略，形成相应的多目标调度优化模型；然后，针对多目标调度问题改进了SOMA算法，采用自适应步长的思想，提高SOMA算法的搜索能力，将二次插值问题运用在种群迁移过程中，提高种群的多样性，解决算法早熟的问题，从而实现运用改进SOMA算法对多目标调度进行自适应优化的过程。通过仿真试验可以证明，本文提出的改进SOMA算法可以有效求解动态生产车间的针对扰动的多目标调度问题。