基于遗传算法的面向绿色制造的车间调度优化*

2012-11-24齐晓宁汪永超张魁伟

组合机床与自动化加工技术 2012年10期

齐晓宁，汪永超，贾婧，张魁伟

(四川大学制造科学与工程学院，成都 610065）

0 引言

绿色制造是现代制造业的热点之一，它综合考虑了资源效率和环境影响因素，旨在减少制造过程的资源消耗和环境污染，实现企业经济效益和社会效益的协调优化。机械加工系统是典型的制造系统，它在将加工资源转变为产品或半成品的同时，也产生了大量的资源消耗和环境影响问题，国内外针对机械加工系统的绿色制造展开了大量的研究工作，但大多数集中在工艺以及产品的设计方面。然而在实际生产中，加工任务调度方案的不同，不仅影响制造系统的生产进度、效率、质量、成本等同时也会对加工过程中的资源消耗和环境排放等产生影响［1-2］。车间的合理调度能在保证产品加工质量、时间的同时，最大限度的减少机械加工系统生产过程中的资源消耗和环境污染，因此其研究具有重要的理论意义和工程价值。由于车间调度本身就是一个非常难解的组合问题且面向绿色制造的车间调度考虑因素众多［3-4］，传统的优化算法不能保证最优结果，因此采用遗传算法求解该优化问题。

遗传算法(Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的随机搜索算法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，能同时使用多个搜索点的搜索信息，在各调度方案间进行交叉和变异操作，搜索范围广、不易陷入局部最优解同时具有原理和操作简单、通用性强、并行性等优点被广泛应用于优化计算方面［5］。本文通过选择合理的编码方法、算子、适应度值的计算和相关参数的设置，用遗传算法来解决面向绿色制造的车间的优化调度问题，并应用于实例。

1 数学模型的建立

1.1 问题描述

面向绿色制造的车间调度主要是研究n个工件在m台机床上的加工，各工件在各个机床上的加工时间和消耗的电能已知，要求确定各工件在机床上的安排顺序，使得工件的绿色度最高。假设加工过程满足以下约束条件:

(1）机械加工系统中的m台机床的加工性能基本相同;

(2）有n个需加工工件，每个工件在每台机床上仅需加工一次;

(3）每台机床同一时刻最多只能有一个工件在加工;

(4）每个工件同一时刻最多只能在一台机床上进行加工;

(5）每一个操作一旦开始就不能中断，必须等到该工件加工完毕才能在该机床上加工其它工件;

(6）不同零件之间没有优先权上的限制，且所有工件的加工准备时间为0。

1.2 面向绿色制造的车间优化调度数学模型

绿色制造是要综合考虑制造过程中的时间、质量、成本、资源消耗和环境污染五个方面的影响，因此面向绿色制造的机床调度优化理想中应该以时间最小、质量最好、成本最低、资源消耗最少、环境影响最小为目标。但在实际生产中由于调度问题本来就是一个NP难题，由于零件的质量通常只需要能达到零件的图纸规定的质量要求即可，不必追求质量最好而环境影响很难用具体的数值表示，在实际中，可依据工人的加工经验判断某个工件在某台机床上加工是否满足工艺质量要求，是否会违反环境法规和工厂自行的一些环境条例，若质量不合格或违反环境法规则应避免安排该工件在该机床上加工，因此在该模型中，将质量和环境影响作为约束条件，以时间和资源消耗为目标。

1.2.1 调度方案变量体系

由上述问题的描述可知，该调度问题即为确定n个工件在m台机床上的加工安排，某一时刻工件在机床上的状态分为两种，工件i在机床j上加工和不在其上加工。因此采用0－1整数变量矩阵对调度方案变量 X={xij|i=1，2，…，n;j=1，2，…，m}进行描述，即当工件i安排在机床j上加工时，xij=1，否则xij=0。其中i=1，2，…，n，j=1，2，…，m用n × m矩阵 X={xij}，(i=1，2，…，n;j=1，2，…，m）表示调度方案变量。

1.2.2 调度目标函数

(1）时间T

实际生产中，时间标准为最大完工时间Makespan(从工件开始加工到最后一个工件加工结束所经历的时间）。其计算公式为:

式中:tij——工件i在机床j上加工时所需要的加工时间和辅助时间。

(2）资源消耗R

机械加工过程中的资源消耗主要有物料消耗和电能消耗，物料消耗主要是指原材料、切削液等主要是由工艺参数选择、切削液选择及设计参数等决定的。合理的调度最直观的是能合理的使用电能，加工过程中的电能消耗如下:

式中:eij——工件i在机床j上加工时产生的能量消耗。

(3）质量环境影响

由于质量、环境影响的模糊复杂性，在该模型中我们将二者作为一个约束考虑。引入一个0－1变量qeij对质量、环境影响进行约束。当工件i安排在机床j上加工满足质量要求且不会有严重环境污染时，qeij=1，否则qeij=0。则将其纳入到时间和资源消耗函数总来，得到:

即目标函数为:

1.2.3 约束条件

(1）由上可知变量X={xij}为一个0－1矩阵，应该满足 xij=0，1(i=1，2，…，n;j=1，2，…，m）;

(3）qeij=0，1(i=1，2，…，n;j=1，2，…，m）。

2 遗传算法求解模型

2.1 调度问题编码

这里采用二进制编码，因其编码和解码操作简单，且交叉和变异操作等便于实现。一种调度方案对应一个染色体，染色体由n个基因段连接而成。假如工件工件i安排在机床j上加工，则将十进制数j对应的二进制数作为工件i对应的基因段。每个基因段有固定的长度l，取j的最大值对应的二进制数的长度作为l，若基因段长度不够则在其前面补充相应位数的0。

2.2 适应度

对于多目标调度问题，利用线性加权和公式把多个目标函数值映射为染色体的适应度，由于事先很难知道权重系数的具体值而且T(X）、R(X）均为求极小值，因此综合适应度为:

但是在这之前要先对调度方案的各个指标值进行无量纲标准化处理，处理公式如下:

式中:Tmax(X），Tmin(X）——调度产生的完工时间最大值和完工时间最小值;

Rmax(X）、Rmin(X）——调度产生的电能消耗最大值和电能消耗最小值。

由公式(7）、(8）可看出，在进行多目标调度求解之前，要先用遗传算法算出 Tmax(X）、Tmin(X）和Rmax(X）、Rmin(X），由于完工时间和电能消耗均要求越小越好，因此采用变权重的方法确定权重系数。

式中:N——每代的种群个数;

i——整数集合［1，N］的一个随机数。

这样在每一代计算中就增加了选权重的过程，由于w1、w2是随机选取的，这样遗传算法的搜索方向也是随机的。这样就能产生足够大的群体得到更多的非劣解，避免陷入局部最优解。

2.3 选择操作

选择是用来确定重组或交叉个体，其基于排序选择。选择的第一步是计算适应度值并将其按由大到小排序，按一定的淘汰比例将适应度值小的个体淘汰掉，并采用“精英策略”补充同样数目的上代较优秀个体［6］。个体适应度值的大小决定了其子孙遗留的可能性，若有M个个体，某个个体i的适应度值为fi，则它被选择的概率为:

2.4 交叉操作

交叉操作可以将父代的良好基因通过信息互换而产生更好的子代，此处采用单点交叉法。它是随机地从遗传种群中选取两个个体C1和C2作为父代，并随机在C1上选取一个基因位x1，在C2上选取同样的基因位，将C1、C2上该基因位后的基因段互换，产生两个新的子代个体。

2.5 变异操作

变异是产生新个体的一种方法，通过变异操作可以改善遗传算法的局部搜索能力和维持种群的多样性，避免陷入“早熟”，较低的变异概率可以防止群体中重要的单一基因丢失，但降低了遗传算法开辟新搜索空间的能力;较高的变异概率将使遗传操作趋于纯粹的随机搜索，降低了算法的收敛速度和稳定性，因此要选择合适的变异概率［7-8］。这里采用交换变异即在父染色体中随机选取两个变异位置然后将其上基因互换。