电子装配物联制造中智能排程算法研究

蒋 城，蔡晋辉

（1.杭州鸿雁智能科技有限公司，浙江 杭州 310007；2.中国计量大学，浙江 杭州 310018）

0 引言

随着物联制造车间的发展，智能排程算法受到重视，产生了很多新的算法，如：领域搜索技术[1]、模拟退火算法（SA）[2]、禁忌搜索算法[3]、遗传算法[4]、神经网络技术[5]、蚁群算法[6]、粒子群算法[7]、蜂群算法[8]、萤火虫算法[9]、蛙跳算法[10]等。

其中，遗传算法（GA）以其全体搜索策略和群体中个体信息交换特点，被广泛应用于求解车间调度问题。国内外学者对遗传算法做了大量的研究，在Reeves[11]验证了遗传算法的优越性后，Murata[12]将局部搜索引入遗传算法中，形成基于遗传算法求解车间调度问题的框架。之后遗传算法的调度优化成为研究重点。例如，王金鹏[13]运用最优子群遗传算法来求解柔性流水车间问题，王军强[14]设计了多样性判定增强算子，分析算子时间复杂度，对自适应遗传算法进行优化求解。王蕾等[15]以加工完成时间、机器损耗、员工操作舒适度为多目标函数，改进遗传算法。

但遗传算法存在局部搜索能力较差，易产生“早熟”收敛的问题，单纯对遗传算法进行优化很难解决这些问题，研究人员将遗传算法与其他算法结合，以取得更好调度结果。程子安等[16]提出双种群机制，分别负责全局搜索和局部搜索，并设计相关遗传算法来弥补局部搜索能力不足的问题。赵诗奎[17]设计了一种两级领域搜索混合算法，利用遗传算法搜索全局变量，对两级领域算法进行改进，实现局部搜索。但这些改进算法存在设计复杂，耗时长等问题，且多针对机械化调度排程，本文以电子企业装配车间为研究对象，针对员工车间排程设计了改进遗传退火算法（GASA），在算法中加入了最优解存储器，能够保证适应度值一直往最优化方向发展，克服遗传算法易早熟，以及模拟退火算法波动幅度大、搜索速度慢的缺点。

1 车间排程数学模型建立

本文智能排程的实质是对电子企业车间装配生产线员工的生产调度分配。假设生产线加工装配过程共有m位员工，加工的产品共有n种，形成产品集合J，员工集合M，工序集合O。所有产品加工时间可以用时间矩阵T来表示，矩阵T每一行代表一种产品，每一列代表一道加工工序，未经过的工序用0表示，矩阵T可以表示为：

上式中，产品1生产过程共需要n1道工序，每道工序的加工时间分别为T11、T12…T1n，产品i生产过程共需要ni道工序。因为各道工序在不同员工Mk加工时间不同，所以各加工时间值不固定，因此才有生产调度的必要，以期求出最优解。

本文首先在满足约束条件并且不考虑其他扰动因素的情况下，建立装配生产车间调度模型。为追求所有产品的最大完成时间最短，产品的总加工时长可以用T1表示，表达式为：

其中，Ciek表示产品Ji在最后一道工序加工完成的时间，即该产品总加工时间。在实际应用中，还需将满足交货期限的指标放入模型中。客户对产品交货期的需求，可以用满意度指标E/T指标T2表示，表达式为：

要使产品交货期控制在客户期望交货区间内，提前和延后都会使调度结果不能最优化，所以设定产品i的提前惩罚系数αi和延后惩罚系数βi。T2值越小，表明产品交货期越接近客户期望交货区间，客户满意度越高。生产调度的总目标函数可以表示为： min[T1，T2]

2 改进遗传退火算法设计

传统遗传算法为保证基因的多样性，引入变异操作以避免某些基因缺失。但实验证明遗传退火算法在进化后期，进化会因变异操作而出现较大的波动。而遗传退火算法中模拟退火可以保证基因的多样性，而不需引入变异操作。遗传退火算法可以分为以下四个步骤：确定问题的编码方案、确定适应度函数、设计遗传退火算子、设置算法参数。

2.1 染色体编码和解码设计

表1 3×3调度问题基础数据表

假设给定染色体[2 3 1 3 2 2 1 3 1]，数字表示产品J1，每个数字产生几次表明该产品有几道工序。再根据表1基础数据表的对应关系，可得到其加工所需时间。以此类推，最终得到该染色体对应的员工列表为[M2M1M3M3M1M3M1M2M2]和对应的时间列表，最终得到染色体解码操作表，如表2所示。

表2 染色体解码操作表

根据该解码操作表可得到可行调度方案如图1所示。

图1 基于工序编码的可行调度

2.2 适应度函数设计

本文选用倒数选取法构造适应度函数。目标函数为最小值问题的适应度函数为：

式（1）中，T（t）为关于种群中第 i个优化方式总加工时间的函数。

2.3 遗传退火算子设计

遗传退火算子的设计包括以下部分：

2.3.1 选择算子

选择操作是将优良个体从父代种群中挑选出来，保留到子代，个体适应度值是判断个体优良性的重要依据。本文采用赌轮法进行选择操作。

遗传选择算子公式为：

式（2）中，f（xi）为个体适应度值，Pi为个体被选中概率。

退火选择算子公式为：

式（3）中，t为退火温度，favg为当前种群平均适应度值。

2.3.2 交叉算子

本文设计了一种以产品工序作为基因片段的交叉方式，具体步骤如下：

步骤一：首先随机选择两个个体P1、P2，随机选择个体中两个产品J1、J2将个体染色体中两个产品所有基因按照原顺序重新组成新基因片段A1、A2，在P1、P2中被提取的位置用0代替，如下所示：

步骤二：将新基因片段调换顺序，依次替换掉对方个体中为0的基因片段，产生新的子代个体B1和 B2，如下所示：

步骤三：把子代B1、B2所有基因反序排列，得到最终个体C1、C2，以提高种群多样性，避免遗传算法早熟收敛，如下所示：

2.3.3 最优解存储器

最优解存储器用来记录调度过程中遇到的最优解，存储器主要包括两个部分p*和f*，p*用来存储最优解，f*用来存储该最优解的目标函数值。在算法运行过程中，产生的优秀个体目标函数值f与存储器中已有最优解目标函数值f*比较，若f优于f*，则p*=p，f*=f，以此保证优化结果为最优解。

2.4 算法参数设置

在调度算法开始运行之前，需要对算法参数进行设置，主要包括以下几个方面：

（1）种群大小 N

（2）编码串长度 l

（3）交叉概率 pc

本文设计的交叉概率与适应度值相关联，当个体适应度值大于种群平均适应度值时，应尽量保留该优秀个体，pc值应较小，反之则应较大，具体计算公式为：

式（4）中，fmax为种群最佳个体适应度值，favg为种群平均适应度值，f为两个要交叉个体中较大的适应度值，k1、k2为交叉概率调整系数，取k1=k2=1。

（4）终止条件

设定如果进化达到最大代数N或者当温度降低到给定终止温度Te时，算法终止，停止进化，返回最优解。

（5）初始温度 T0

初始温度影响全局搜索能力，温度越高搜索能力越强，但所用时间也越长。在实际车间调度问题中，T0的取值公式为：

式中，fmax、fmin分别为初始种群中个体适应度值的最大值和最小值，r取10。

（6）退温函数

退温函数采用指数函数的方式进行退温，能够保证后期缓慢降温，退温函数为：

式中，T0为初始温度，降温系数a取0.9，k为循环次数。

2.5 遗传退火算法流程

遗传退火算法的设计步骤如下：

步骤一：建立目标函数，确定适应度函数。

步骤二：初始化算法参数：种群大小N、交叉概率 pc、初始温度 T0、降温系数 a。

步骤三：编码产生初始种群P0，令i=0，k=0。

步骤四：采用赌轮法选择个体，按照自适应交叉概率pc执行交叉操作，更新存储器中的f*和p*，生成新的临时种群S。

步骤五：新的临时种群S作为模拟退火算法的初始种群，对种群中各个个体进行模拟退火操作，计算种群中染色体适应度，更新存储器中的f*和p*。

步骤六：判断是否满足终止条件，如是，则输出最优解并结束算法；否则转步骤四。

遗传退火算法的流程如图2所示。

图2 遗传退火算法流程

3 实验结果及分析

3.1 调度问题理想状态甘特图

为验证算法的有效性，采用Job-shop benchmark基准问题做对比。本文采用FT06基准问题数据来验证遗传退火算法的有效性。算法初始运行参数设置为：种群规模N=50，交叉概率pc=0.7，初始温度T0=100℃，终止温度Te=0.01℃，降温系数a=0.9，最大迭代次数G=100。整理后得到6×6调度问题基础数据，整理后数据如表3所示。

表3 6×6调度问题基础数据表

根据本文设计的GASA算法运行结果，得到其中一个最优染色体为[5 6 1 2 6 3 4 1 6 4 3 5 1 4 5 6 4 1 5 2 6 5 1 3 2 4 5 6 1 2 3 2 3 4 2 3]。通过GASA算法得到的最优染色体需要的加工时间为55秒，对于FT06问题，6×6规模的最优目标函数值f*=55，因此达到该问题最优解，验证了算法的有效性。最优解调度甘特图如图3所示。算法收敛曲线如图4所示。

图3 最优解调度甘特图

图4 算法收敛曲线

从图4中可以看出，经过50次迭代后，遗传退火算法最终收敛，得到的最优适应度值为55。表明改进遗传退火算法有较快的搜索速度和较高的搜索精度。为更直观的比较GASA算法、GA算法和SA算法，分别对基准问题进行求解，得到它们的收敛曲线，如图5所示。

图5 三种算法收敛对比图

从图5可看出，SA算法和GASA算法都能达到最优解，但分别在76代和50代时完成收敛找到最优值，表明改进模拟退火算法收敛速度更快，并且SA算法在迭代初期波动幅度很大，而GASA算法由于在算法中加入了最优解存储器，能够保证适应度值一直往最优化方向发展。对比GA算法和GASA算法，可以看出GA算法在19代时完成收敛，但并未达到全局最优解，表明GA算法在进化过程中容易陷入“早熟”，得到局部最优解。综上所述，遗传退火算法在进化过程中收敛平滑，收敛速度适中，全局最优解搜索能力强，能够克服遗传算法易早熟的缺点，又能克服模拟退火算法波动幅度大搜索速度慢的缺点，验证了算法的有效性和优越性，符合本文设计目标。

3.2 实际情况下调度甘特图

上文给出的最优解是在理想状态下得到的，但在实际生产过程中经常出现各种干扰因素，如电子企业经常出现临时插单的情况。为应对该情况，本文将临时订单到来时刻作为再调度的初始时刻，将临时插单数据输入到初始时刻，对于在此刻加工的产品及工序不做打扰，对产品未完成的工序进行再调度。例如，在图3理想状态调度甘特图时刻为30min时，出现临时订单，需要优先加工产品J7，要求该产品必须在30分钟之内加工完成，其基础数据如表4所示。

表4 临时插单产品基础数据表

按照临时插单调度优先的规则，若不采取再调度，则每位员工在该产品经过自己工序时，需要优先加工该产品，此时的总加工时间为66min，产品J7加工完成时刻为56min，加工用时26分钟，其甘特图如图6所示。采取临时插单再调度后，产品总加工时间为63min，产品J7加工完成时刻为60min，加工用时30分钟，在满足30分钟内加工完成这一约束性目标的前提下，使各产品总加工时间最小化，其甘特图如图7所示。

图6 未采用临时插单的调度甘特图

图7 采用临时插单的调度甘特图

理想状态最优调度甘特图适用于客户对交货期不做更改的情况，但在实际生产过程中，部分客户可能在加工阶段对产品交货期做出改变，此时需要在原调度方案的基础上，改变员工加工产品的顺序，以满足产品交货期更改需求。例如客户在时刻为30min时对产品J3期望交货期提出修改，将该产品交货期提前至[45，50]之间，进行再调度后，产品J3的加工完成时刻提前至46min，其调度甘特图如图8所示。

图8 交货期提前的调度甘特图

4 总结

本文针对电子装配车间自动化水平低、生产以人工加工装配为主的实际生产情况，适应物联制造建设需要，研适用于人工生产的智能排程方法。首先对车间生产调度问题进行分析并建立多目标调度模型。其次根据模型设计了改进遗传退火算法，研究了算法实现的过程以及各参数的设定，并给出了遗传退火算法的具体流程。最后利用Job-shop benchmark FT06基准问题作对比，验证了改进算法的有效性，给出了最优解调度结果及其甘特图。同时针对实际生产过程中出现的临时插单和交货期提前事件，给出了再调度方法及其甘特图。排程计划最终通过生产任务的派工执行实现电子装配企业员工生产效率的提升。