基于遗传算法的装配车间调度问题的研究(3)

每道工序可以在不同的机器上加工，工序的加工时间因使用机器不同而不同。要求确定与工艺约束条件相容的各机器上所有工件的各道工序在每台机器上排序，以达到加工性能最佳，既满足目标要求的最小实际值。

模型约束条件为：

ａ．同一零件在各机器上的加工工序有顺序约束，不同零件在各机器上的加工工序无顺序约束。

ｂ．每台机器一次只能加工一个零件，且加工一旦开始就不能发生中断。

‘

ｃ．零件在某一时刻只能在一台机器上加工。ｄ．所有加工工件优先级相同。ｅ．忽略一切机器故障。

遗传算法ＧＡ（ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ）是一种模拟自然界生物进化过程的仿生算法［８］。它通过模仿生物的进化过程来优化解的集合，其基本操作是通过选择、交叉和变异搜索解的空间。其对空间的搜索具有隐含并行性，它不同于随机搜索（解空间中的枚举搜索），它的选择机制可以大大减小搜索空间，因而可以在有限时间内得到二个最优解或较优解，并且遗传算法还是一种具有全局优化能力的搜索方法。

加工时间目标函数定义如下：

Ｔ＝ｍａｘ｛ｍａｘｔ“｝

ｌ≤ｔ≤ｎ

ｌ≤Ｊ≤研。

式中，以为待加工的零件数；优为加工机器数；％为第ｉ种零件在第ｊ个机器完成加工的时闻。

遗传算法流程如图３所示。

厂网

、

ｉ开始】

．任务约束ｌ秽

Ｉ时间约束１

计数个竿适应度卜＿掣

．设备约束Ｉ

ｏ≥

．工序约束ｌ

输出结果

工艺约束Ｉ

Ｌ（结束】／

图３遗传算法

ａ．适应度函数。遗传算法在搜索过程中以适应度函数作为依据，通过适应度函数评价每个染色体的性能。适应度函数一般由目标函数变换而成，如

＜机械与电子｝２０１２（４）

万方数据

果目标函数可以直接利用，则目标函数即为适应度函数，否则需要对目标函数的值域进行映射，进而获得相应的适应度函数。

ｂ．个体编码。常用的编码方式有二进制和十进制２种编码方案。这里采用二进制编码，即用一个二进制向量作为一个染色体，表示为五。该向量的长度依赖于区间长度和要求精度，这里取精度为小数点后２位数。

ｃ．群体初始化。由于遗传算法群体型操作的需要，必须为遗传操作准备一个由若干初始解组成的初始群体。在确定群体规模后，为了提高算法的效率和质量，初始种群采用基因空间均匀分布算法

ＧＳＢＳ（ｇｅｎｅｓｐａｃｅｂａｌａｎｃｅ

ｓｔｒａｔｅｇｙ）［９１产生初始种

群，使初始种群大致的均匀分布于解空间中。这种方法可以在一定程度上缓解遗传算法局部收敛的问题，从而改善最优解的质量。

ｄ．选择策略。选择的目的是从当前的群体中选出优良个体，使他们有机会成为父代，以便繁殖后代。判断个体优良与否的准则是各自的适应度值，这里采用轮盘赌选择方法，其公式为：

Ｃ

Ｐ（ｉ）＝ｆ（ｉ）／∑，（ｆ）

ｉ＝ｌ

式中，Ｐ（ｉ）为个体ｉ的选择概率；，（ｉ）为个体ｉ的适应值，其取值为个体解码取得的最大完工时间的倒数，即厂（ｉ）＝１／Ｆ（ｆ）。这种方法有助于算法快速收敛，从而获得最优解。

ｅ．交叉与变异。在初始种群中，按照染色体适应度值折算的概率选取染色体进行交叉或者变异操作，适应度大的染色体被选择的概率较大，从而保证

优势个体在种群中以更大的概率存活。

交叉是主要的遗传操作，新染色体大部分由交叉获得，交叉操作能够有效地保留父项信息，这里交叉算子采用部分映射交叉方式。

变异操作的目的是通过随机改变染色体某些基

因来引入新个体，提高种群多样性，这里变异算子采用逆序操作。

２仿真及结果分析

２．１问题描述

产品生产过程由零件部装及部件总装２部分构成，共包含６个部装区，每个部装区分别由若干个可以拆分但具有工序约束关系的工艺过程组成。每个

５。