并行机间歇过程生产调度的遗传局部搜索算法

摘要：

研究了一类集成分批的并行机间歇过程调度问题(parallel machine batch process scheduling problem,简称PBPSP),将此问题转化为固定费用运输问题(6xed charge transportation problem,简称FCTP)后,提出了具有集中邻域搜索机制和局部最优逃逸机制的遗传局部搜索算法(genetic local search algorithm,简称GLSA).GLSA算法用先根遍历边排列模式编码生成树解,具有高效的子树补充式单点交叉操作.将基于网络单纯型方法的邻域搜索作为变异算子,并提出了连续随机节点邻域搜索的集中邻域搜索策略以及随机旋转变异与全局邻域搜索相结合的局部最优逃逸策略,极大地强化了遗传局部搜索算法的全局寻优能力.实验表明:GLSA算法获得的解质量优于基于排列编码的遗传算法和基于矩阵编码的遗传算法,得到了所有Benchmark问题的最优解,且具有高鲁棒性.针对一定规模的FCTP问题,GLSA算法比Tabu启发式搜索算法具有更高的获得最优解几率.

关键词：间歇过程、调度、固定费用运输问题、生成树、遗传算法、局部搜索

所属期刊栏目：17

分类号：TP316(计算技术、计算机技术)

资助基金：国家自然科学基金60573086;国家高技术研究发展计划863计划2003AA4Z3210;高等学校博士学科点专项科研项目20030213027

在线出版日期：2007-01-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：2589-2600