ABSTRACT

With the rise of the Internet of things and big data analysis technology, more and more enterprises transform from the traditional manufacturing industry to intellectualization to achieve industrial upgrading. For complex products, total completion time minimization is an important part of production planning in manufacturing enterprises. If we can establish the total completion time minimization model accurately, both of the program accuracy and working efficiency can be greatly improved. The proposed method of test and detection plan to minimize the total completion time can improve the test and detection efficiency and shorten the test cycle. Verified by examples, it has good application effect.

Keywords:Genetic Algorithm, The Total Completion Time, Minimization, Test and Detection

基于遗传算法的试验计划总完工时间极小化模型设计与实现

赵红武¹，黄小瑜²，史亚斌¹，秦彪²，王东¹，丁懿³

¹西安高压电器研究院有限责任公司，陕西 西安

²西安电子科技大学，陕西 西安

³西安邮电大学通信与信息工程学院，陕西 西安

收稿日期：2016年8月1日；录用日期：2016年8月21日；发布日期：2016年8月24日

摘 要

伴随着物联网技术和大数据分析技术的兴起，越来越多的企业由传统制造业向智能化转型，以实现产业升级，而总完工时间极小化，尤其是复杂产品的总完工时间极小化，是制造企业生产计划编制中的重要环节。若能实现总完工时间极小化模型的准确建立，既能改善计划的准确性也可以大幅度提高检测业务的工作效率。本文提出的试验检测计划的总完工时间极小化方法，经算法实现后得到的试验检测方案能够有效的提高产品的试验检测效率，缩短产品的试验检测周期。经实例验证，有良好的应用效果。

关键词 :遗传算法，总完工时间，极小化，试验检测，试验计划调度

1. 引言

近年来，随着国家电网对输配电装备的需求日益增长，国内的输配电行业试验检测业务数量急剧增加，迫切要求各试验企业扩大试验检测产能，缩短产品的试验交货期，满足不断发展的试验检测业务需求。高压电器产品试验检测过程具有多约束等特点，这使得公司在试验设备和计划实施上存在着很多问题 [1] [2] ，主要有：

1) 上级下达和检测室接收检测任务都是凭借人为经验估计，导致下达和接收的任务量都可能不合理。

2) 不同品种产品试验检测项目的资源需求不同，且在试验检测过程中存在着试验项目的先后顺序、资源数量有限等多种约束，使得试验计划调度过程很复杂。

3) 被测产品种类规格各异，使得各试验检测设备上的负荷不同，从而造成产品积压或设备及人员闲置，最终导致不均衡试验或试验效率偏低。

上述原因会使得试验计划调度工作难以进行，进而造成一些试验任务无法按计划完成以及试验资源无法按需求进行合理调度，因此，有必要建立试验计划的总完工时间的极小化模型，在考虑各种约束的情况下，使它的排序计划最优，为计划编制工作提供依据。

关于总完工时间最小化的问题，谭建荣等提出了Pareto进化算法 [3] ，解决了车间调度多目标优化前提下的总完工时间最小化问题。Allahverdi A [4] 在2013年提出了PAL算法及遗传算法，解决了在最大完工时间受限条件下的无等待车间(NWJSP)总完工时间极小化问题。田乐等 [5] 讨论了并行工件同时加工排序问题，即n个同时到达的工件在m台批处理机上排序的问题，目标函数是极小化总完工时间。首先对同型批处理机的情况给出了动态规划算法。许瑞 [6] 等以求解目标为极小化总完工时间的批调度问题，考虑不同的编码方式，提出了基于工件序列的蚁群算法和基于批序列的蚁群算法。在国外，美国Purushothaman Damodaran等 [7] [8] 先后提出了一种贪婪随机自适应搜索过程方法和一种模拟退火算法以解决最小化完工时间问题。这两种方法的前提条件为非零的工作准备时间、任意工作尺寸和任意工序时间。韩国的Mi-Yi Kim等 [9] 提出了一种混合启发式算法来最小化其总完工时间并在实际中得到了应用。近年，Aydilek H [10] 、Al-Anzi F S [11] 、Xiong F L [12] 和美国的Shanthi Muthuswamy [13] 等也提出了模拟退火算法、差分进化算法和粒子群优化算法等一些方法，解决了各种情况下的总完工时间最小化问题。伊朗的Seyed Habib A. Rahmati等 [14] 开发生物地理学优化BBO算法，并将此算法与一种遗传算法做了对比。西班牙的Pedro Gomez-Gasquet等 [15] 成功解决了混合流水调度车间的最小化其最大完工时间问题。

关于遗传算法，Domdorf [16] 等人用遗传算法进化工件分配的优先规则序列。HajriS [17] 等提出了一种受控遗传算法，该遗传算法的编码方式采用并行机编码，初始种群的生成采用启发式算法，并采用多交叉操作产生新群体。王伟玲等 [18] 提出双种群的遗传算法求解多目标作业车间调度问题。赵诗奎 [19] 利用混合方式的交叉与变异的遗传算法，实现了极小化FJSP的总完工时间问题的高效求解，同时还研究了最大机器负荷和最大工件加工时间指标的优化。彭运芳等 [20] 和张腾飞 [21] 都通过使用遗传算法来找到作业调度问题的最优方案。

本文以某公司高压电器产品的试验检测为研究对象，结合实际的试验检测计划方案的制定问题 [22] ，总结了现有试验计划检测方案的不足，把遗传算法用到试验检测计划问题中，对试验检测计划的遗传算法模型进行了详细的设计、分析和说明。

2. 试验检测计划模型的数学问题描述

试验检测任务：一般，一个试验任务包含n个试验产品，每个试验产品包含一个或多个试验项目(如T100s电寿命，空载特性试验等)，这n个试验产品要在m个检测室下进行。试验计划调度问题包括：一、确定各试验产品的检测室和确定各个检测室上的检测先后顺序；二、在试验计划调度问题中试验检测任务所要满足的约束有：

1) 每个检测室中的某设备在同一时间只能加工某任务的某个试验项目。

2) 每个试验项目必须在指定的检测室中的检测设备上进行检测。

3) 每个试验项目必须在它之前项目检测完成后才能开始下一个项目。

4) 每个试验项目在试验检测过程中不会被另外的试验项目中断。

5) 试验任务检测的过程中，没有新试验项目的加入，也不取消试验任务的加入。

针对上述的数学描述，得到试验检测计划的目标函数(试验产品在检测设备上的总完工时间最小化)为：

(1)

约束条件的数学模型为：

(2)

(3)

(4)

(5)

其中，式(2-2)至(2-5)分别表示试验项目约束条件决定的各试验产品的各个试验项目和各检测设备的先后检测顺序。式中，符号和分别为i产品在检测设备k上的完成时间和加工时间；M是一个足够大的正数；和分别为指示系数和指示变量，其意义为：

(6)

(7)

3. 试验计划模型的遗传算法参数设计 [23]

3.1. 编码

在基于试验项目(工序)的编码方式中，每个染色体由个代表试验项目的基因组成，是所有试验项目的一个排列，其中各试验项目号均出现次。检测设备的检测矩阵为：

上述问题对应的调度结果执行顺序如下，(M1)表示操作在设备M1上进行，调度甘特图如图1，试验任务的调度问题如表1所示：

试验产品1的第一个操作(M1)；

试验产品2的第一个操作(M1)；

试验产品3的第一个操作(M2)。

试验产品2的第二个操作(M2)；

试验产品2的第三个操作(M3)；

试验产品3的第二个操作(M1)。

试验产品1的第二个操作(M3)；

试验产品3的第三个操作(M2)；

试验产品1的第三个操作(M3)。

3.2. 生成初始种群

由于本算法采用的是基于试验项目的编码方法，该编码方式已经保证了随机产生种群的可行性，因此，初始种群可由系统随机生成。

3.3. 适应度函数

在此试验检测计划的模型中，以极小化试验检测计划的总完工时间为目标函数，适应度函数如式(8)所示：

(8)

上式中为的最大值估计，取当前群体中的最大值。

3.4. 遗传操作

本算法的选择操作、交叉操作以及变异操作设计如下：

1) 选择操作

本算法中选择操作采用的是轮盘选择法。

2) 交叉操作

交叉操作的性能是使得子代能够取得父代好的特征以及产生子代的可行性。

图1. 一个可行的调度甘特图

表1.试验任务的调度问题

具体的交叉操作设计如下：假设两个父代染色体和，从染色体基因为任意选择()个试验产品的编号，在父代染色体中的基因中删除所选择的编号，保持这些编号的相对顺序不变，然后分别保存在新的基因串和中，同时保留父代个体和中所选择的这些编号的位置为空，接着将和分别插入到和的空位中，然后将新得到的染色体和分别左移和右移个基因位置，分别生成新个体和。

对于的试验计划调度问题，若检测室中检测设备的检测顺序如下所示：

假设和如下所示：

在和中分别选择试验产品2、3，将和中含有这两个试验产品号的基因从中抽取出来，产生新的基因串和为：

则此时和为：

将中的基因串按顺序插入到的空位中，将中的基因串按顺序插入到的空位中，然后对和分别左移和右移操作，移动的位置均为两个位置，最终得到新的个体和如下所示：

3) 变异操作

具体的变异操作如下：从当前种群中选择一个个体作为父代，从所需要检测的试验产品号中任意选择两个号码，将这两个试验产品号交换，最后再将染色体中的基因左移或右移个位置。

假设染色体如下所示：

交换染色体中试验产品号1、4的位置，其中1和4是任意取的试验产品号，得到结果为：

接着右移一个基因位置，得到的结果为：

3.5. 算法终止条件

遗传算法终止条件是根据算法的迭代次数，即遗传代数和收敛条件来确定的。

4. 实例分析

遗传算法编码的实现采用MATLAB中的m语言实现。遗传操作的参数设定为：种群大小为40，代沟为0.9，交叉算子为0.8，变异算子为0.1，迭代代数20。

的产品试验检测计划问题

产品种类为：；检测室种类为：；试验产品在检测室中的作业步骤与作业时间如表2所示。

对应产品的试验检测计划方案的甘特图如图2所示：

图2中V1、V2、V3和V4分别为试验产品VD4SG-1、VD4SG-2、VD4SG-3和VD4SG-4的缩写，各产品的试验项目的的检测顺序是按T1、T2、T3和T4依次进行的，如上图的试验检测产品VD4SG-1，它的试验项目T1是四个试验项目中最先执行的，在检测室JCS-1中进行检测。

对应着上面的表格数据，检测室编号矩阵：J = [2,3,1,0;1,0,2,3;3,2,0,1;0,1,2,3;]；试验项目时间矩阵：T = [3,4,3,1;3,3,2,8;3,2,1,6;4,6,2,1]。因此，经算法运算后的算法种群寻优收敛过程和试验检测计划结果如图3、图4所示：

如图3所示，10含义为：加工号100000B的试验产品VBGs-1的T1试验项目在检测室3中进行检测。其中1代表的是试验产品VBGs-1，0代表的是T1试验项目。其余代号如21，31的含义类似。图4就是一个4个试验产品，每个试验产品有4个试验项目的检测方案图。比如试验产品VBGs-1的试验项目顺序，它的1号试验项目在检测组3中进行检测，2号试验项目在检测组4中进行，3号试验项目在检测组2中进行检测，4号试验项目在检测组1中进行检测。

表2. 4 × 4试验任务的试验信息

图2. 4 × 4产品的试验检测计划甘特图

图3. 4 × 4产品问题解的变化和种群均值变化图

图4. 4 × 4产品问题的试验检测方案最优甘特图

对于委试号100000B，在不优化的前提下，总完工时间是22小时。

在本方案中，总完工时间为19小时，其效率比未经优化的方案提高了13.6%。

5. 结论

以上模型的设计以极小化产品试验检测计划的总完工时间为目标函数，结合产品的试验检测计划问题的实例，对算法进行了实现，并获得最优的计划排产结果，证明了遗传算法可以很好的解决试验检测计划的总完工时间极小化问题，对实际的试验检测计划的编排具有一定的参考价值。通过对试验检测计划方案的优化，减少了试品的转移吊装和搬运次数，同时，合理规划了在场试品的数量，腾出宝贵试验场地，减少了大量与试验有关的费用支出。这对提高试验企业的决策水平、经济效益以及市场竞争力有着很好的现实意义。

文章引用

赵红武,黄小瑜,史亚斌,秦 彪,王 东,丁 懿. 基于遗传算法的试验计划总完工时间极小化模型设计与实现
Design and Implementation of the Total Completion Time Minimization Model of Test Plan Based on Genetic Algorithm[J]. 数据挖掘, 2016, 06(03): 116-124. http://dx.doi.org/10.12677/HJDM.2016.63014

参考文献 (References)