车用空调装配车间集成化生产作业管理系统

(2)约束条件

为保证换产品时物料配备，每种产品以批量L分配到生产线上连续装配，其任务批次为K，;PKi为第i种产品最后一批次的批量数。

4.1.2 基于遗传算法的车用空调装配车间生产作业调度算法

遗传算法(Genetic Algorithm，GA)是一种能处理车间生产作业调度这一复杂和非线性问题的有效方法。基于GA的车用空调装配车间生产作业调度问题的求解有五个基本步骤：染色体编码、生成初始群体、计算适应度、遗传操作(选择、交叉、变异)、调度优化结果。下面以具体的调度实例说明算法求解过程。

(1)问题描述

某车用空调制造企业在一调度期内要在Ml，Mz，M3三条线上装配J48CC，YY5，CV7，CD340四种产品。设定批量L一10，换线调整时间TH=10，各数据如表1所示。

表1 五种产品、三条装配线的实例

对于以上车用空调装配线装配任务调度问题，不同产品不同批次K在不同的生产线上加工就构成不同的排列。有序数列。O={Oij...，OIKJ

}(i代表第i种产品，k代表i种产品的第k批，k代表在第j条线上装配)总能表示出最优的调度方案。对O进行编码，首先定出每种产品的批次K。，总批次Ki决定染色体基因的个数，本例中总批次为22;再综合考虑产品的最迟完工时间以及延期完工惩罚值定出优先级，优先级高的排在编码数列的前面，本例中产品优先级排序为{P1，P4，P2，P3)，编码的基因座与优先级相同;每个基因座内的位置先后表示产品批次，并用数字“1，2，3”表示装配线。染色体编码方式如图4所示。

图4 编码方式

(3)生成初始群体

采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量S称为种群规模。本例中根据以上的编码方式，利用Cell(S)一[Fix(1)(rand())，...，Fix(22)(rand())]随机生成S=20个合法的初始种群，每个染色体拥有22个基因。

(4)计算适应度

为了引导遗传搜索，应定义一个适应度函数。遗传算法法则是努力将基因的适应度函数最大化。适应度函数由目标函数变换而成。通过式(1)、式(4)和式(5)分别计算出每代群体中所有个体的(R，Q，C)，并统计出每代群体中的最大值和最小值。经过对(R，Q，C)的标准化处理，定义的适应度函数

式(11)中WR，Wo,Wc是权重，在本例中取值为0.4，0.3，0.3。利用式(11)计算出初始种群每个个体的适应度值。

(5)遗传操作

选择：根据初始种群各染色体的适应度值，采用轮盘赌方法，从初始种群中选择出20个后代种群。交叉：设定交叉概率P。一0.85，采用部分映射交叉方法(Partially Mapping Crossover，PMX)，对以上选择出的后代种群中85%的染色体进行逐对交叉;该交叉方法是同基因座基因间的交叉，不会产生非法染色体。

变异：设定变异概率Pc=0.05，采用基于次序的互换变异方法，以0.05的概率进行变异。先随机地产生两个变异位置，然后交换这两个变异位置上的基因。

修复:为保证经过变异的染色体的可行性，采用修复策略设计算子。先根据已知建立判断刃矩阵A(表示i产品不能在1条线装配)，如a,}2表示第一种产品不能在第二条线上装配;再将变异后的种群个体与矩阵A比较，判断出非法染色体的非法基因，利用随机数产生合法基因并替换非法基因。

遗传操作变化过程如图5所示。

图5 调度的退传操作过程简图