基于改进的单倍体遗传算法生产调度设计

赵锦东，张 婷，金 雁

（唐山学院，唐山 063000）

基于改进的单倍体遗传算法生产调度设计

赵锦东，张 婷，金 雁

（唐山学院，唐山 063000）

0 引言

生产调度，作为制造执行系统的关键环节在企业信息化和管理一体化的进程中发挥着重要作用 ，良好的生产调度对企业生产健康高效的运转具有重要的作用。生产调度技术在满足车间内机械装置生产能力、客户订单计划和产品质量标准的条件下，参照当前的库存状况，以缩短时间为尺度，以市场需求为目标，评价生产数据和其他和生产密切相关的物性数据，实现产品结构、产品质量、生产车间组织结构和生产运作方式的优化。

市场竞争的日益激烈，对生产管理与生产调度提出了更高的要求。如何设计生产调度的方法、如何建立适合生产调度的优化算法对于加快企业对市场变化的快速反应、提高产品生产率、降低生产成本、节约能源的关键所在。

1 单倍体遗传算法及其改进

1.1 单倍体遗传算法

单倍体遗传算法(Partheno Genetic Algorithm,PGA)是由日本学者KOJI M在将基本遗传算法运用于调度问题时最先提出来的。该算法突破了基本遗传算法选择、交叉、变异三种遗传算子的要求，取消了交叉操作，通过对变异操作进行不断的研究与改进进行繁殖后代的。单倍体遗传算法是一种新型的基于序号编码的遗传方式，具有与基本遗传算法相似的遗传、进化机制，与基本遗传算法不同的是遗传算子的种类、操作及对遗传编码的处理方式。单倍体遗传算法的基因重组算子具有与基本遗传算法交叉算子相同的功能，同时经过单倍体遗传算法进化后的子代个体几乎保留了父代个体所具备的全部遗传特征。

1.2 改进的单倍体遗传算法

对单倍体遗传算法在搜索方式上提出改进，即对单倍体遗传算法适应度函数的变换进行改进，采用改进的指数适应度函数，通过控制指数函数值的变化来改善单倍体遗传算法的性能.改进前的指数变换方法如下：

1）式中指数函数的系数α一般取正数，f(x)为经过指数变换之前的适应度函数，f'(x)为变换后的适应度函数。

对原来的指数变换改进如下：

2）式中f(x)与f'(x)的含义与在改进前的指数变换中的意义相同。如问题自身性质是求解最小值，则f(x)直接取目标函数；如要求解的是目标函数的最大值，先将问题的目标函数进行线性变换，将求解最大值问题转换为求解最小值的。改进后的指数变换中，指数α是一个动态变化的函数，而不再是一个常数，α随个体进化代数的变化而逐渐变化的正数，根据单倍体遗传算法的进化特点，将原来指数变换的指数系数α用一个自适应的动态调整函数表示。通常，遗传进化初期favg的值较大，有时可达到进化迭代过程中出现的最大值，这样α的值很小，甚至会达到进化过程中的最小值，随着遗传迭代的不断进行，favg呈现减小的趋势，此时进化代数t逐渐变大，总体来看α的取值逐渐变大。

2 基于改进的单倍体遗传算法生产调度设计

2.1 生产调度问题描述

生产调度(Job-Shop Production Scheduling)问题可描述为：在技术、工艺等一系列约束条件下，对于某个可以被分解的任务，合理安排其组成部分所占有的加工时间、物料资源，在满足用户需求的前提下提高生产效率、降低生产成本、节约生产所耗能源。即研究在m台机器上加工n个工件的过程，加工过程中的约束条件是工序的加工时间及工件工件的加工次序，有硬件约束又有技术约束，最终目的是求得与工艺约束条件相容的加工设备上的全部工件的加工次序，使加工性能达到预期目标或者接近预期目标。

2.2 生产调度问题建模

2.2.1 约束条件

在典型的Job-Shop调度问题中，除技术、工艺、资源约束外，通常还假定以下条件：待加工工件在不同机器设备上的加工顺序必须以生产该工件的工艺流程为准则； 生产工件的初始加工时间定为0，且须保证一台加工设备在同一时间内只能对一个工件进行加工操作，一个被加工工件在同一时间仅能够在一台加工设备上进行加工；工件在加工过程中，在一台机器设备上完成一个生产任务以后，才能进行另一个生产任务；工件在前驱工序结束以后，才能进行后继工序；待加工工件的优先权在生产调度中不予以考虑；同一台机器设备不允许工件重复加工；工件在加工过程中不可以被中断。

2.2.2 建模步骤

在对车间生产调度建模过程中，变迁集合中包含的元素不仅有资源变迁而且还有工序变迁。资源获得库所、设备库所和状态库所构成了库所的集合。

1）建立任务所包含的工序和工序变迁之间的一对一关系；

2）建立状态库所和变迁触发后的状态之间的一对一关系；

3）确定生产任务，并为每个任务建立一个起始状态库所；

4）将以上三个步骤中所确定的状态库所和工序变迁用有向弧连接起来；

5）建立资源获得库，在工序变迁与资源获得库间建立一对一的关系；

6）建立资源库与相应资源间的一对一关系；7）给资源分配库确定资源分配变迁；

8）起点为需要资源的变迁，终点为工序变迁对应的资源库的有向弧的现实意义是将工序变迁所需要的资源释放掉；

9）将确定的资源获得库所、资源库所和资源分配变迁用有向弧连接起来；将工序变迁和相应的资源获得库所用有向弧连接起来；

10）资源库着色，为有向图中的有向弧标注权值，颜色默认值为-1，有向弧权值的默认值是0；以每道工序的加工时间为依据，给每一个工序变迁设置初始加工时间，其余变迁的加工时间默认为0。

2.3 生产调度系统主要功能设计

2.3.1 系统开发环境

操作系统：W I N D O W S X P；开发工具：.Net2.0, Microsoft Visual Studio 2005；开发语言：C# ；数据库：Oracle 9i；网络协议：TCP/IP；浏览器：IE 6.0以上

2.3.2 主要功能设计

该系统主要实现生产调度的任务的合理安排，使整个生产调度过程花费的时间最小。系统主要功能模块如下：

1）资源管理模块：实现对车间相关资源的系统管理与控制。包括设备管理、客户信息管理、职工信息管理、物料管理和订单管理五个子功能。

2）生产调度模块：改进的单倍体遗传算法在生产调度中的应用模块。设计界面中输入生产调度参数及改进的单倍体遗传算法的相关参数，如初始种群数目、遗传迭代次数、变异概率等数据。进行参数录入以后，系统就将加工工件的加工时间及相应的约束条件筛选出来，根据工艺数据库，将待加工的工件分解成相关工序的集合。再结合录入的加工时间，转化为算法中对应部分的相关参数。

图1 调度结果显示界面

由于车间生产调度系统从定单生成到代码的下载，工艺、资源等之间存在的大量的数据流动，将车间生产调度的结果存储到调度管理数据库中，通过查看调度数据库中的数据可以确定设备的详细加工任务及加工流程。图1为调度结果显示界面。

3 结论

应用提出的改进的单倍体遗传算法对建模后的车间生产调度模型进行优化，并给出了具体的优化步骤。使用改进的单倍体遗传算法，进行车间生产调度系统设计，并通过对数据的采集、分析及模拟得出相应结果。设计实现证明基于改进后的单倍体遗传算法设计的调度系统在算法的寻优速度和收敛精度上有明显提高。

[1]马正元,王伟玲,王玉生.生产调度问题的系统研究[J].成组技术与生产现代化,2005,34(6):10-14.

[2]AMIT K G,APPA I S.Job shop scheduling techniques in semiconductor Manufacturing[J].Int J Adv Manufacture Technology,2006,34(27):1163-1169.

[3]周岭.车间作业调度与控制技术研究[J].械加工与自动化,2002,11(12):19-22.

[4]张铃,张钱.遗传算法机理的研究[J].软件学报,2000,11(7):945-952.

[5]裴金勇,陈评,等.机组优化组合的改进遗传算法[J].武汉大学学报,2001,34(l):73-76.

[6]李茂军,等.单亲遗传算法在Flow shop问题中的应用[J].系统工程与电子技术,2000,22(6):84-89.

[7]李茂军,童调生,罗隆福.单亲遗传算法及其应用研究[J].湖南大学学报,1998,25(6):164-179.

Based on improved partheno genetic algorithm in enterprise production scheduling

ZHAO Jin-dong, ZHANG Ting, JIN Yan

在对车间生产调度进行建模和仿真的基础上，基于改进的单倍体遗传算法设计实现车间生产调度系统。设计实现证明基于改进后的单倍体遗传算法设计的调度系统在算法的寻优速度和收敛精度上有明显提高。

生产调度；单倍体遗传算法；设计

赵锦东（1978 -），女，讲师，硕士，主要从事计算机教学工作。

TP391

B

1009-0134(2011)5(上)-0027-04

10.3969/j.issn.1009-0134.2011.5(上).10

2010-10-15