基于仿真集成的遗传算法在单元制造系统中的人机调度问题优化

康雯轩

（燕山大学 经济管理学院，河北 秦皇岛 066000）

0 引言

单元生产是基于成组技术发展出来的，也是精益生产的一部分。单元生产的优点有：生产中产生的在制品库存少，物料搬运成本少，单元内设备利用率较高等[1]。

Seru生产方式是指以Seru为基本单位的生产线组织，由流水线生产方式分割、转化为多个Seru的生产组织形式[2]。本文研究的背景是把Seru生产运用到单元制造中，单元中不再单一的考虑机器，而是在单元里把机器因素与人共同考虑，本文采用仿真集成的遗传算法来求解seru生产下的单元制造车间调度多目标优化问题。

1 模型建立

1.1 问题描述

假设n个零件按照固定的工序依次通过不同的单元，每个单元内包含一定数量的机器和多能工，零件的工序可以在不同的单元内完成，但是零件在单元内的移动是有时间的消耗。

1.2 参数符号

n：零件的数量；

m：机器的数量；

o：工人的数量；

oij：第j零件的第次的操作，

pijk：操作oij在机器上的处理时间；

ptijw：工人w处理操作oij时间；

stij：生产oij所需要的准备时间；

CTij：oij的加工完成时间；

tuu'：部件从单元u移动到单元u'时的单元间移动时间，当u=u'时tuu'=0；

c：单元的数量；

dj：j零件的最长生产时间；

Dj：零件j的最晚交货时间；

Fij：Oij作业的完成时间；

Sij：Oij作业的开始时间

决策变量：

1.3 建立模型

约束（1）确保每个操作只能分配给其中一个机器。约束（2）确保每个操作只能分配给其中一个工人。式（3）确保工人只能被分配给一个单元，约束（4）表示从这个工序的开始时间到下个工序的完成时间是由机器与工人的处理时间和部件的移动时间构成的。约束（5）表示如果指定操作机器和零件处在不同的单元中，单元间移动时间将发生。约束（6）是零件到期日约束。约束（7）表示操作的加工完成时间表示。约束（8）限制了一个单元内的工人数；约束（9）确保订单只能分配到可行的单元。

2 仿真集成的混合遗传算法

仿真集成混合遗传算法（SHGA）是将离散事件仿真（DES）和遗传算法（GA）集成在一起的改进遗传算法，在SHGA种群中的每个个体都使用离散事件仿真来评估。

2.1 编码

本文采用三层编码方式对每个零件的每个操作数所对应的机器和单元进行编码，其中第一层中的值表示零件j的索引，其出现的次数表示操作i的索引，第二层表示操作所在的机器，第三层代表操作所在的机器所在的单元。

2.2 适应度函数

本文求解的是最小化目标函数，因此通过上面初始个体的染色体编码数据计算适应度，通过保留较小目标函数值的个体，即适应度大的个体，构成下一代。

2.3 选择运算

本文使用轮盘赌的方法选择优秀的个体，其主要思想是选择路径的概率与适应度成正比，适应度越大，选择概率越大。

2.4 交叉运算

本小节提出了一种扩展的偏序交叉算子，用于从一对父染色体（父染色体1和2）中生成子染色体（子染色体1和2）。首先我们把所有部分随机分成两组，即S和S0。我们将那些部分包含在集合S中的基因从父代1复制到子代1的相同位置。我们用来自父代2的那些基因填充子代1的剩余空白位置，这些基因具有属于集合S0的部分，而不改变它们的序列。子2的生成方式类似。

2.5 变异运算

应用随机插入变异算子。突变操作通过从亲本染色体中随机选择两个基因i和j，并将位置j的三层基因插入位置i之前，进行突变。

2.6 算法框架

通过上述分析，本文提出的仿真集成混合遗传算法流程图如图1所示。

图1 仿真集成混合遗传算法流程图

3 数值实验

本实例问题包括6个零件、10台机器和2个单元。每个零件的工序次数都是6，其中工件加工计划如表2所示。在遗传算法中，使用这些参数的不同组合进行仿真，以对它们进行微调，其参数设置结果如表1、表2所示，人工数量为10人。本文的算例所使用的仿真集成混合遗传算法（SHGA）使用MATLAB编程。

表1 仿真集成混合遗传算法参数

表2 工件加工计划表

通过仿真得到最佳函数值从最初72min下降到最小值48min，从计算的最优的结果来看，人工成本达到了最小，由此可见本模型可以共同考虑机器与工人合作生产。为了对比算法有效性，本文使用蚁群算法进行对比，对比结果如表3所示。通过实例可以看出，离散事件仿真集成的遗传算法在计算实例过程中表现良好，得到了良好的结果。见图3。

表3 SHGA 与ACO 对比

图3 使用SHGA 算法求解的甘特图

4 结语

本文提出了一种用于单元制造系统与seru单元结合的工序调度的仿真集成遗传算法，以最小化最大完成时间为目标。仿真集成遗传算法提供了一种解决方案，可以共同考虑机器与工人合作生产。从计算结果表明，仿真集成遗传算法在合理的时间内表现良好，在求解目标问题上得到了良好的结果。