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) 交叉操作
交叉操作的性能是使得子代能够取得父代好的特征以及产生子代的可行性。
Figure 1. A feasible dispatch Gantt chart
图1. 一个可行的调度甘特图
Table 1. Scheduling problem of test task
表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中进行检测。
Table 2. 4 × 4 Test information for test tasks
表2. 4 × 4试验任务的试验信息
Figure 2. Test plan Gantt chart for the 4 × 4 product
图2. 4 × 4产品的试验检测计划甘特图
Figure 3. The solution change of 4 × 4 products and population mean change
图3. 4 × 4产品问题解的变化和种群均值变化图
Figure 4. Gantt chart of the optimal test and detection scheme of 4 × 4 products
图4. 4 × 4产品问题的试验检测方案最优甘特图
对于委试号100000B，在不优化的前提下，总完工时间是22小时。
在本方案中，总完工时间为19小时，其效率比未经优化的方案提高了13.6%。
5. 结论
以上模型的设计以极小化产品试验检测计划的总完工时间为目标函数，结合产品的试验检测计划问题的实例，对算法进行了实现，并获得最优的计划排产结果，证明了遗传算法可以很好的解决试验检测计划的总完工时间极小化问题，对实际的试验检测计划的编排具有一定的参考价值。通过对试验检测计划方案的优化，减少了试品的转移吊装和搬运次数，同时，合理规划了在场试品的数量，腾出宝贵试验场地，减少了大量与试验有关的费用支出。这对提高试验企业的决策水平、经济效益以及市场竞争力有着很好的现实意义。