一种求解作业车间调度问题的文化遗传算法

一种求解作业车间调度问题的文化遗传算法) ) ) 王伟玲李铁克施灿涛

一种求解作业车间调度问题的文化遗传算法

王伟玲李铁克施灿涛

北京科技大学, 北京, 100083

摘要:针对传统遗传算法缺乏有效指导, 容易陷入局部极值的缺点, 提出了以一种采用种群空间和信仰空间的双层进化结构进行寻优的作业车间调度算法。该算法针对调度问题的特点, 以遗传算法为主群体空间, 利用优良调度方案的知识信息构成信仰空间。为充分利用父代个体的优良特征加速收敛, 算法采取不同的策略在主群体空间中指导遗传操作, 在选择操作中引入k 近邻法的思想进行动态学习, 在变异操作中通过选择合适的变异点进行邻域搜索变异。典型算例的仿真实验与分析表明, 算法在计算效率和求解质量上均具有较好的效果。

关键词:作业车间调度; 文化遗传算法; 邻域搜索变异; k 近邻法

中图分类号:T P301. 6 文章编号:1004) 132X(2010) 03) 0303) 07

An Effective Cultural Genetic Algorithm for Job Shop Scheduling Problem

Wang Weiling Li Tieke Shi Cantao

University of Science and T echnology Beijing, Beijing, 100083

Abstr act :Aiming at the disadvantages of traditional genetic algorithms that are lack of efficient guidance and easy to get into local extremum, this paper developed a double evolution frame popula 2tion space and belief space to solve job shop scheduling pr oblem. CGA was to extract the excellent in 2dividuals' schema of the scheduling solution from the population space of genetic algorithm as the use 2ful knowledge to form belief space. A nd the belief space was utilized to guide the genetic operator of selection and mutation by two different ways respectively in order to make use of the characteristics of excellent individuals. k -near est neighbor method was introduced to do dynamic learning in selection operator, and do neighbor sear ch mutation in mutation operator at an appropriate position. T he differ 2ent sizes of the benchmark data taken from literature wer e used to analyze the efficiency of this algo 2r ithm. Exper imental results indicate that it outperforms current approaches in computational time and quality of the solutions.

Key words :job shop scheduling; cultural genetic algorithm(CGA) ; neighborhood search mutation; k -near est neighbor method

0 引言

车间作业调度问题已被证明属于典型的NP -hard 组合优化问题[1], 主要原因是:¹解空间随着工件数和机器数非线性增加; º工件的各个工序之间存在机器顺序约束。调度问题的早期研究主要集中在开发有效的启发式规则, 但由于启发式规则自身的局限性, 研究者们开始关注各种智能算法, 以期在合理的时间内获得满意解, 其中包括禁忌算法、遗传算法、粒子群算法等, 但是这些算法大多存在进化速度慢或早熟的不足。

文化算法(cultur al algorithm) 的主要思想是模拟人类社会的演化过程, 从进化种群中获取有用的知识(信仰) , 并反馈这些知识用于指导搜索过程, 因此与进化算法相比能够大大节省运行的

收稿日期:2009) 04) 30

基金项目:国家自然科学基金资助项目(70771008, 70371057)

时间[223]。由于文化算法的柔性与高效性, 其理论研究及应用正受到学者们的广泛关注。文献[4]应用文化算法来求解背包问题, 文献[5]对比研究了自适应进化搜索过程中文化算法的规范知识与形势知识如何发挥作用, 文献[6]对水火电力系统日常发电计划问题应用文化算法进行优化, 文献[728]分别用文化算法来求解约束优化问题以及对乙烯精馏塔产品质量软测量进行建模, 实验结果均证明该算法具有较好的计算效果。目前关于文化算法在调度问题中的应用, 只有少数文献有过报道, 其中, Rivera 等首次将文化算法应用到作业车间调度问题, 通过大量的数值实验并与其他最优化方法比较, 表明该算法优于其他启发式方法。

已有研究中存在的问题是, 文化算法在进化算法的基础上利用信仰空间中的知识指导搜索过程, 但是只是影响变异操作, 且只是利用局部信息进行插入变异, 算法的时间复杂度会随着问题的

#303#

[9]

中国机械工程第21卷第3期2010年2月上半月

规模呈指数级增长; 邻域搜索变异在变异操作的基础上加入邻域搜索以提高算法跳出局部搜索能力, 同时增加搜索区域的宽度, 但其搜索方向缺乏有效的指导, 具有一定的盲目性。针对上述问题, 本文应用文化算法的理论框架, 提出对于不同遗传操作提取具有问题特征的优良染色体模板, 构建信仰空间; 提出两种指导选择和变异操作的知识学习策略, 从而形成算法的双层进化结构, 使个体在搜索空间中加快收敛速度, 避免出现早熟而收敛于局部最优解。最后通过数据仿真实验, 验证了所提出的文化遗传算法的有效性。

t S gj -t ij +M(1-x igj ) \p ij P i, g(i X g) , P j

(3)

t E ij , t ij \0 P i, P j

(4) (5) (6)

a ihj =0或1 P i, P j, h(j X h) x ig j =0或1 P i, g(i X g) , P j

式(1) 中目标函数为最小化完工时间; 约束式(2) 表示同一工件上两个相邻工序的优先顺序约束; 约束式(3) 表示同一机器上的相邻工件在加工

时间上不能出现重叠(独占性约束) ; 约束式(4) ~式(6) 表示变量取值范围。

2 求解算法

1 问题建模

1. 1 问题描述

作业车间调度问题(job shop scheduling problem, JSSP) 可以简单地描述如下

[10]

:有n 个

待加工的工件I 需要通过m 台不同的机器J 来处理; 各个工件在每台机器上加工一次且仅一次, 并分别按指定的工艺路线通过所有的机器; 工序一旦开始加工, 就不能中途停止; 在任意时刻每台机器最多只能加工一个工件; 优化目标为所有零件的完工时间(makespan ) , 记作C max 。按照A |B |C 三参数法[11], 目标函数为最小化时间跨度的经典作业车间调度问题可以归结为J m +C max 。1. 2 数学模型

对于具有n 个工件和m 台机床的车间作业调度问题, 为便于模型的建立, 引入以下符号:n 为工件总数; m 为总机器数; i 为工件的编号, i =1, 2, , , n; j 为机器的编号, j =1, 2, , , m; O ij 为工件i 的第j 道工序; I 为工件集合, I ={1, 2, , , n};J 为机器集合, J ={1, 2, , , m};p ij 为工件i 的工序O ij 在机器M j 上的加工时间; FS 为可行排序集合; M 为足够大的正整数; t S

ij 为工件i 在机器j 上的开始加工时间; t E

ij 为工件i 在机器j 上的结束完工时间; C i 为工件i 的最大完工时间, C i =max E

P j I J

(t ij ) ; a ihj 为指示系数; x igj 为指示变量。a ihj 和x igj 的表达式分别为

a 1 若机器h 先于机器j 加工工件i ihj =0 否则

x 1 若工件i 先于工件g 在机器j 上加工igj =

0 否则

根据上述问题描述以及符号定义, 可用如下数学模型来表示车间作业调度问题:

min C *max =min FS

(C max ) =min FS

max P i I I

(C i )

(1)

t S ij -p ih +M(1-a ihj ) \t S ih

P i, P j , h(j X h) (2)

#304#

2. 1 算法框架

社会学家认为, 文化是一种保存个体以往经验的知识库, 在一定时期为群体的特定部分所共享, 在知识库中新的个体可以学到它没有直接经历过的知识, 从而促使群体以一定的速度进化和适应环境。从本质上讲, 文化算法是在进化算法的基础上发展起来的, 可以看作为一种基于知识的进化算法。

具体地讲, 文化算法由主群体空间和信仰空间两部分组成。在微观层面, 主群体空间进行问题的迭代求解形成知识信息; 在宏观层面, 信仰空间保存上述知识信息并通过与微观层面的交流, 对主群体空间的迭代过程进行指导, 使两者在两个层面进行相互影响、相互促进。进化算法与文化算法之间的本质区别是:进化算法的搜索过程具有完全随机特性, 而文化算法的迭代过程有知识信息的指导, 并不是完全随机的; 随着迭代次数的增加, 文化算法的信仰空间会定期更新, 从而形成一种双重的继承机制。主群体空间可以选择任意一种群体智能算法, 这是文化算法柔性的一种表现。应用文化算法求解优化问题时应注意:¹信仰空间的设计, 即提炼什么类型的知识才能对主群体空间的进化过程具有指导作用, 以及如何提炼这种知识; º学习策略的制定, 即信仰空间的知识信息如何才能更有效地引导群体空间的进化过程。

本文针对作业车间调度问题, 采用遗传算法作为主群体空间, 因此称为文化遗传算法(cultur 2al genetic algor ithm, CGA) 。在连续性优化问题中, 由于其解集为连续的欧氏空间, 通常提取有用的值域知识存储在信仰空间, 在其中值域知识的指导下将搜索空间中无用的部分剪掉并改善想要的部分, 以此来缩减搜索空间并将知识代代相传。

调度问题为典型的离散性优化问题, 其解空间为

一种求解作业车间调度问题的文化遗传算法) ) ) 王伟玲李铁克施灿涛

欧氏空间的一个点集, 也是离散性的。对此, 本文提出一种不同于连续优化问题以值域知识构造信仰空间的方式, 针对不同的遗传操作, 提出将从主群体空间中抽取优良调度方案的不同染色体模板保存在信仰空间, 用来指导迭代操作, 这一模型的应用类似于禁忌搜索算法中的禁忌表; 对于学习策略, 提出与A 信仰空间中的染色体进行对比选择适当的基因位置来指导变异操作, 利用k 近邻法的思想使B 信仰空间的个体影响选择操作。算法的总体框架如图1

所示。

其中如果不推迟至少一道其他的任何工序或者违反任意一台机器的约束条件, 将没有工序可以被更早地开始加工。

定义2 半活动调度也是一种可行的调度方案, 其中如果不改变加工顺序或者违反任意一台机器上的约束条件, 将没有工序可以被更早地开始加工。

半活动调度算法生成的调度方案的完工时间大于等于活动调度算法, 且并不能保证获得最优值。活动调度算法所生成的调度方案一定包含最图1 CGA 的总体框架

2. 2 算法描述

2. 2. 1 编码方式

使用遗传算法求解经典作业车间调度问题时, 许多编码方式容易生成不可行、冗余以及非活动调度方案, 这样就需要花费额外的计算将其转

化为可行解。为了避免求解过程的复杂性, 本文采用重复置换工件号的编码方式[12]。即对一个规模为n @m 的作业车间调度而言, 一条染色体有n @m 个基因, 每个基因表示一个工件号, 工件号在染色体中出现的位置表示其对应的工序, 如图2所示。这种编码方式的优点是不需要修复机制,

因为它进行的遗传操作不产生不可行解。

图2 3@3JSSP 的编码方式

2. 2. 2 解码

我们使用基于活动调度的解码算法。活动调度与半活动调度[11]的定义如下:

定义1 活动调度是一种可行的调度方案,

优值。所以我们的解码算法直接采用生成活动调度的方法。半活动调度算法的时间复杂度为O(nm) , 而活动调度的编码算法的时间复杂度为O(n 2m 2) 。

2. 2. 3 设计信仰空间

(1) 信仰空间的组成。信仰空间由A 和B 两部分构成, 分别由接受函数accep t 1

() 和accept 2() 来决定。假设主群体空间中共有L 条染色体, 令c hm l 表示主群体空间中第l 条染色体, c hm l 的适应度值F l 为其对应调度方案的所有工件的最大完工时间C max , 则信仰空间A 为

accep t 1() :A =[chm *]

F *=1min [l [L

F l

即由最优染色体构成信仰空间A 。信仰空间B 为

accept 2() :B =[chm 1, chm 2, , , chm x ]

首先按照染色体的适应度值的大小, 依次排列为F 1

(2) 信仰空间的更新。每迭代既定的次数后, 更新信仰空间, 使信仰空间持续保存当前最好的知识信息。因此, 该算法一直采用当前最好的部分调度方案作为学习对象。将信仰空间相邻两次更新之间的算法迭代次数称为更新频率, 记作f 0。2. 2. 4 交叉操作

交叉算子用于随机交换种群中的两个父代个体的某些基因, 在解空间中进行有效搜索, 从而组合出新的子代个体, 它是遗传算法的最重要操作。两点交叉算子是以概率1收敛, 具有全局搜索能力, 尤其当解空间基因位置关联紧密时此种交叉方式性能较好, 能够继承父代的有效模式[13214]。

作业车间调度问题采用重复置换工件号的编码方式时, 染色体基因位置具有关联紧密性, 所以本文采用两点交叉的方式。2. 2. 5 变异操作

变异有利于遗传算法跳离搜索空间的一个固

#305#

中国机械工程第21卷第3期2010年2月上半月

定区域, 搜索更广阔的解空间, 以改善算法的局部搜索能力, 维持群体的多样性, 一般的标准遗传算法中的变异操作都是随机进行的。文献[9]提出一种通过利用最优调度模板知识来指导插入变异, 其时间复杂度为O(n m ) 。本文结合邻域搜索变异[15](neighbor search mutation) 法对这种方法进行了改进, 使变异操作在信仰空间A 中知识的指导下以更宽的搜索区域进行迭代, 下面给出其具体实现过程:

首先, 确定变异点的选择范围。根据变异概率P m 在子空间中随机选择一条染色体, 与最优染色2

q =q+1; }} pos =pos(1:q -1) ; q =q-1;

//根据q 的大小选择不同的变异操作, 其中P 为1到q 之//间的随机序列.

if q [2then{//随机选择3个变异点, 进行邻域搜索变异.

tempsolution =repmat(curr ent_individual, 6, 1) ; P =randperm(l) ;

x 1=pos(P(1) ) ; x 2=pos(P(2) ) ; x 3=pos(P(3) ) ; do neighbor search mutation ; } else {

体比较, 并记录基因取值不同的染色体位置pos 和个数q(q 为偶数) 。

然后, 根据q 的大小进行不同的变异操作:(1) 当q [2时, 随机选择变异点, 进行邻域搜索变异。

(2) 当q \4时, 则先产生一个由1到q 之间的整数所组成的随机序列P , 令u 表示进行邻域搜索变异的基因个数, v 表示循环次数, w 表示最大循环次数, 且w 为q/u 向下取整, 即w =[q/u], 一般情况下u =3, 具体过程如下:¹令v =1; º从左到右依次取随机序列P 上的3个元素P[uv -2]、P [uv -1]、P[uv]来决定pos 上进行邻域搜索变异的基因位置; »进行邻域搜索变异; ¼将v z v +1, 若v [w 则转到º; 否则, 算法结束。

很显然, q 的数值越大, 说明被变异染色体和最优染色体之间的基因取值不同的位置越多; 反之, 则越少。该变异方式具有自学习的特点, 因此将其命名为自学习邻域搜索变异(self-learnable neighborhood search mutation, SNSM ) , 其时间复杂度为O(q) , 其中q 等于当前染色体与信仰空间A 中染色体之间基因位置取值相异点的个数, 其伪代码如下:

Pr ocedure LNSM (P opSize, P m , A, y, pos, q, P) {for i =1:P opSize do {//PopSize 为群体规模.

//与最优染色体进行比较, 记录与其不同的基因位置pos //和个数q.

randnumber =r and (0, 1) ; //生成0~1的随机数. if randnumber

//如果随机数小于变异概率P m , 则进行变异操作. cur rent_individual=crossset(i, :) ; q =0; f or ii =1:y do {//y 为染色体的长度.

//best_individual为信仰空间A 中的最优染色体. //cur rent_individual为当前进行变异操作的染色体. if best_individual(ii) X curr ent_individual(ii) then { pos(q) =ii;

#306#

//当q \4时, 从随机序列P 中取3个数确定个体的基因//位置并进行邻域搜索变异, 依次重复w 次. tempsolution =repmat(current_individual,6, 1) ; P =randperm(q) ; w =q/u;

for v =1:3:w do {

x 1=pos(P (v) ) ; x 2=pos(P (v +1) ) ; x 3=pos(P(v+2) ) ;

do neighbor sear ch mutation; }}}}}}

2. 2. 6 选择操作

在遗传算法中, 选择是根据对个体适应度的评价从种群中选择优胜的个体, 淘汰劣质的个体。一般的标准遗传算法中的选择操作都是随机进行的, 如最佳个体保存法和锦标选择法。本文引入k 近邻法[16](k-nearest neighbor method ) 的原理, 利用信仰空间B 中的知识指导选择操作, 具体描述如下:

(1) 利用基于轮盘赌的选择方式生成初始子群体空间;

(2) 在子群体空间中选择既定数量为k 的优良个体集合, 根据k 近邻法将这些个体与信仰空间B 中的染色体一一进行相似性指数计算;

(3) 查找k 个相似性指数S d 最大的个体, 并将这些个体插入到当前子群体空间中, 同时淘汰掉k 个最差的个体。其相似性指数计算公式如下:

S d (chm 1, chm 2) =

áchm 2(i) (1)

i=E chm

(i) 1

如果两条染色体中对应基因位置的取值相同, 则c hm 1(i) áchm 2(i) 返回值为1, 否则为0, 其计算公式如下:

chm 1 chm 1(i) =chm 2(i) 1(i) áchm 2(i) =

0 chm 1(i) X chm 2(i)

(2)

其中, c hm 1和c hm 2分别表示两条染色体, i 表示染色体中基因所处的位置, y 表示染色体的长度, 一般在规模为n @m 的作业车间调度问题中其大

一种求解作业车间调度问题的文化遗传算法) ) ) 王伟玲李铁克施灿涛

小为y =nm 。

相似性指数S d 表示两条染色体编码之间的海明距离(H amming distance ) , 其中海明距离指的是两个长度相同的码字, 其相对应的位可能不同, 彼此不同位的个数。因为两个解之间的不同与染色体编码之间的海明距离几乎成正比[17], 所以通过计算相似性指数可以推出两个解之间的相近程度, 如果相似性指数S d 的取值越大, 则两条染色体就越相近, 反之亦然。该操作方式主要进行相似性计算, 因此将其命名为相似性选择操作(selection with similarity ) 。2. 3 算法流程

CGA 的算法流程如图3所示, 具体实现步骤如下:

(1) 初始化主群体空间。

(2) 初始化信仰空间A 和信仰空间B 。(3) 如果已达到最大迭代次数max I ter s, 或在迭代过程中最优值连续不提高的次数达到Stag _times, 迭代停止; 否则转步骤(4) 。

(4) 根据更新频率f 0, 决定是否更新信仰空间; 否则转步骤(5) 。

(5) 相似性选择操作。首先生成初始子群体空间, 然后在子群体空间中选择既定数量的染色体, 分别计算它们与信仰空间B 中染色体的相似性指数。根据相似性指数的大小, 采取优胜劣汰的策略保证部分最优个体进入子群体空间。

(6) 交叉操作。采用两点交叉的方式。

(7) 自学习邻域搜索变异。将进行变异的染色体与信仰空间A 中最优染色体进行比较, 根据基因取值不同的数量决定变异操作的方式。

(8) 生成新一代种群, 返回到步骤(3) 。

3 仿真实验

3. 1 数据与参数

本文采用MA TLAB 编程语言, 在CPU 为116GHz, RAM 为1GB 的PC 机上进行算法实现。

算例的所有数据均来自OR-library 的Job Shop 排序的FT 和LA 系列Benchmark 算例。算法选用的基本参数如下:群体规模Pop Size =200、交叉概率P c =017、变异概率P m =011、信仰空间B 的既定染色体数量x =5、相似性选择操作中既定染色体的数量k =5、更新频率f 0=5。3. 2 结果与分析

表1列出了文化遗传算法CGA 对不同规模FT 和LA 系列Benchmark 算例各运行20次后的实验结果以及Parallel GRASP [18]﹑H GA [

19]

图3 文化遗传算法流程图

的实验结果, 其中, Parallel GRASP 在196MH z SGI R10000PC 上实现, H GA 在1133GH z AMD Thunder bird PC 上实现。值得指出的是, 加粗数值表示对应算例目前已知的最优值。表1中, V min 和E mr 分别为最小值和最小相对误差, V ave 、T ave 和E ar 分别为平均值、平均时间和平均相对误差, Parallel GRASP 中T ave 数据由文献[18]中直接获得, 为尊重原文, 该栏数据的有效位数未能一致。

在求解质量方面, 73%的问题算法CGA 都取得了最优解, 除了LA22和LA25以外, 其他问题相对其他算法而言也有了一些改进。从统计数据来看, 算法CGA ﹑Par allel GRASP ﹑H GA 的平均最小相对误差分别为0129%、0148%、0143%。总体而言, 算法CGA 的求解效果还是很明显的。

从计算时间上看, 算法CGA ﹑Parallel GRASP ﹑H GA 的平均计算时间分别是162s 、93680s 、1009s 。值得注意的是, 算法CGA 对中小规模问题的求解时间有了很大的提高, 算例LA01~LA20中除了算例LA07外, 计算时间均在20s 之内。

总之, 无论在求解质量还是计算效率上, 算法CGA 都较以往算法有一定的改善。

4 结束语

文化算法在解决车间作业调度问题时较少应用领域知识, 更适合于解决实际生产中的调度问

#307#

中国机械工程第21卷第3期2010年2月上半月

表1 文化遗传算法Benchmar k 实测结果

算例FT06FT10FT20LA01LA02LA03LA04LA05LA06LA07LA08LA09LA10LA11LA12LA13LA14LA15LA16LA17LA18LA19LA20LA21LA22LA23LA24LA25LA26LA27LA28LA29LA30LA31LA32LA33LA34LA35LA36LA37LA38LA39LA40

规模n @m 6@610@1020@510@510@510@510@510@515@515@515@515@515@520@520@520@520@520@510@1010@1010@1010@1010@1015@1015@1015@1015@1015@1020@1020@1020@1020@1020@1030@1030@1030@1030@1030@1015@1515@1515@1515@1515@15

已知最优[***********][***********][***********][***********][***********][***********][***********][***********]2331222

V min [***********][***********][***********][***********][***********][***********][***********][***********]2481232

CGA 算法测试结果E mr (%) [***********]000000. 481. 6201. 390. 8200. 320. 332. 5200000000. 721. 251. 220. 820. 29

V ave [***********]590595. [***********]221045. 411501297. 31207948. 1789. 2853. 8849. 6908. 31078. 7958. 51032965. 61015. 61225. 21247. 01273. 31238. 81357. 51792. [***********]286. 51444. 21298. 81254. 11262. 8

E a r (%) 000001. 3700. 42000. 050000. 6200. 4100. 330. 660. 680. 900. 703. 133. 4003. 273. 950. 590. 974. 717. 530. 180. 4800001. 463. 388. 601. 713. 34

T a ve (s) 0. 67. 56. 92. 34. 87. 413. 65. 74. 626. 37. 86. 34. 86. 25. 37. 29. 16. 47. 18. 38. 75. 215. 392. 072. 028. 031. 075. 0191. 0175. 0290. 0304. 0263. 0532. 0552. 0517. 0596. 0682. 0315. 0368. 0325. 0350. 0575. 0162. 0

Parallel GRASP [18]V min [***********][***********][***********][***********][***********][***********][***********][***********]2481244

E mr (%) T ave (s) 00. 860. [***********]00001. 05002. 030. 7202. 750. 744. 430000001. 500. 931. 841. 221. 800. 48

0. [**************]0. 082109. 629. 515. 710. 1090. 80. 1581. 670. 341. 150. 3140. 2890. 320. 5724. 5529516. 58453. 5302. [***********]93. [***********][***********]2283026761. 266875. 114016. 53483. [***********][***********]

V min [***********][***********][***********][***********][***********][***********][***********][***********]2461241

H GA [19]

E m r (%) T a ve (s)

[***********]00000. 5500. 8601. 930. 9201. 701. 323. 820000000. 870. 791. 921. 051. 550. 43

[***********][***********][***********][***********][***********][***********][***********][1**********]

平均值

题。本文将遗传算法纳入文化算法的模型中, 针对作业车间调度问题设计有用的知识构成信仰空间, 通过计算相似性指数来指导选择操作确保优秀个体进入下一次迭代的子空间; 通过在指定范围的变异点进行自学习邻域操作变异, 保证个体在迭代过程中有效继承父代的优良特征, 从而加速搜索过程不断向最优的方向逼近, 其原理同样适用于其他类型的调度问题。FT 和LA 系列算例的仿真结果可以证明这种双层进化算法的有效性, 在未来的研究中, 将尝试采用其他的方式设计#308#

信仰空间, 探讨更好的学习策略, 以进一步改善求解质量, 提高搜索效率。

参考文献:

[1] Garey M R, Johnson D S, Sethi R. The Complexity of

Flow Shop and Job-shop Scheduling[J].Mathematics of Operations Resear ch, 1996, 1(2) :1172129.

[2] Reynolds R G. An Introduction to Cultural Algorithms

[C]//Proceedings of the 3rd Annual Conference on Evolutionary Programming. Singapore:World Scientific

一种求解作业车间调度问题的文化遗传算法) ) ) 王伟玲李铁克施灿涛

Publishing, 1994:1312139.

[3] Chung C J, Reynolds R G. A Testbed for Solving Opti 2

mization P roblems Using Cultural Algorithms [C]//Pr oceedings of the F ifth Annual Conference on Evolu 2tionary Programming. Cambridge, Massachusetts:MIT Pr ess, 1996:2252236.

[4] Reynolds R G, Michalewicz Z, Cavaretta M. Using Cul 2

tural Algorithms for Constraint Handling in GENO 2COP[C]//P roceedings of the F ourth Annual Confer 2ence on Evolutionary Progr amming. Cambridge, Massa 2chusetts:MIT Press, 1995:2982305.

[5] Reynolds R G, Chung C J. A Self-adaptive Approach

作者简介:王伟玲, 女, 1979年生。北京科技大学经济管理学院博[C ]//Proceedings of the Genetic and Evolutionar y Computation GECCO2004. Ber lin:Springer, 2004:2102221.

[18] Aiex R M, Binato S, Resende M G C. Parallel GRASP

with Path -relinking for Job Shop Scheduling[J].Parallel Computing, 2003, 29(4) :3932430.

[19] Goncalves J F , Mendes J M, Maur cio G C, et al. A

Hybrid Genetic Algorithm for the Job Shop Schedu 2ling P roblems[J].Eur opean Journal of Operation Re 2search, 2005, 167(1) :77295.

(编辑马尧发)

to Representation Shifts in Cultural Algorithms [C]//Pr oceedings of IEEE International Conference on Evo 2lutionary Computation. Citeseer:the Scientific Literature Digital Librar y, 1996:94299.

[6] Yuan Xiaohui, Yuan Yanbin. Application of Cultural

Algor ithm to Gener ation Scheduling of Hydrothermal Systems [J ].Energy Conversion and Management, 2006, 47(15) :219222201.

[7] 黄海燕, 顾幸生, 刘漫丹. 求解约束优化问题的文化算

法研究[J]. 自动化学报, 2007, 10(33) :111521120. [8] 黄海燕, 顾幸生. 基于文化算法的神经网络及其在建

模中的应用[J].控制与决策, 2008, 23(4) :4772480. [9] Rivera D C, Becerr a R L, Coello C A C. Cultural Algo 2

rithms, an Alternative Heur istic to Solve the Job Shop Scheduling Problem [J ].Engineering Optimization, 2007, 39(1) :69285.

[10] Jain A S, Meer an S. Deterministic Job-shop Schedu 2

ling:P ast, Present and Future[J].European Journal of Oper ation Research, 1998, 113(2) :3902434. [11] Pinedo M. Scheduling Theory, Algorithms and Sys 2

tems[M]. New Jersey:Prentice Hall, Upper Saddle River , 2002.

[12] Varela R, Vela C R, Puente J, et al. A knowledge -based Evolutionary Strategy for Scheduling Problems with Bottlenecks[J]. European Jour nal of Operational Research, 2003, 145(1) :57271.

[13] 任庆生, 曾进, 戚飞虎. 交叉算子的极限一致性[J].

计算机学报, 2002, 25(12) :140521410.

[14] 熊军, 高敦堂, 沈庆宏, 等. 遗传算法交叉算子性能对

比研究[J].南京大学学报(自然科学) , 2004, 40(4) :4322437.

[15] T sujimura Y, Gen M, Cheng R. Improved Genetic Al 2

gorithms for Solving Job -shop Scheduling P roblem [J]. Engineering D esign and Automation, 1997, 3(2) :1332144.

[16] Hastie T, Tibshirani R, Friedman J. The Elements of

Statistical Learning[M].New York:Springer, 2001.

[17] Tay J C, Wibowo D. An Effective Chromosome Repre 2

sentation for Evolving F lexible Job -shop Schedules

士研究生。研究方向为生产调度与控制、智能算法设计与复杂性分析。李铁克, 男, 1958年生。北京科技大学经济管理学院教授、博士研究生导师。施灿涛, 男, 1979年生。北京科技大学经济管理学院讲师。

(上接第262页) 参考文献:

[1] 宋天田, 肖正学, 苏华友, 等. 上公山TBM 施工2. 22

卡机事故工程地质分析[J].岩石力学与工程学报, 2004, 23(增刊1) :454424546.

[2] Sugimoto M, Sramoon A. Theoretical Model of Shield

Behavior dur ing Excavation. I:Application[J]. Journal of Geotechnical and Geoenvironmental Engineering, 2002, 128(2) :1382155.

[3] Komiya K, Soga K, Akagi H, et al. Finite Element Mod 2

elling of Excavation and Advancement Processes of a Shield Tunneling Machine [J].Soils Found. , 1999, 39(3) :37252.

[4] Marshall M A, Milligan G W E, Mair R J. Movements

and Stress Changes in London Clay Due to the Con 2struction of a Pipe Jack [C]//Geotechnical Aspects of Underground Construction in Soft Ground. Rotterdam:P roc. Int. Symp. , 1996.

[5] 施虎, 龚国芳, 杨华勇. 盾构掘进机推进压力控制特性

分析[J]. 工程机械, 2008, 39(5) :23226.

[6] 施虎, 龚国芳, 杨华勇. 盾构掘进机推进速度控制性能

分析[J]. 机床与液压, 2008, 36(8) :77279.

[7] 张厚美, 吴秀国, 曾伟华. 土压平衡时盾构掘进试验及

掘进数学模型研究[J]. 岩石力学与工程学报, 2005, 11(增刊2) :576225766.

[8] 曾晓星. 异质岩土工况下土压平衡盾构载荷等效及传

递特性研究[D ]. 上海:上海交通大学, 2009.

(编辑马尧发)

作者简介:丁晟, 男, 1984年生。上海交通大学机械与动力工程学院硕士研究生。主要研究方向为重型装备的动力学分析。余海东, 男, 1975年生。上海交通大学机械与动力工程学院讲师。王皓, 男, 1973年生。上海交通大学机械与动力工程学院副教授。

#309#