摘要
研究了一类集成分批的并行机间歇过程调度问题(parallelmachinebatchprocessschedulingproblem,简称PBPSP),将此问题转化为固定费用运输问题(fixedchargetransportationproblem,简称FCTP)后,提出了具有集中邻域搜索机制和局部最优逃逸机制的遗传局部搜索算法(geneticlocalsearchalgorithm,简称GLSA).GLSA算法用先根遍历边排列模式编码生成树解,具有高效的子树补充式单点交叉操作.将基于网络单纯型方法的邻域搜索作为变异算子,并提出了连续随机节点邻域搜索的集中邻域搜索策略以及随机旋转变异与全局邻域搜索相结合的局部最优逃逸策略,极大地强化了遗传局部搜索算法的全局寻优能力.实验表明GLSA算法获得的解质量优于基于排列编码的遗传算法和基于矩阵编码的遗传算法,得到了所有Benchmark问题的最优解,且具有高鲁棒性.针对一定规模的FCTP问题,GLSA算法比Tabu启发式搜索算法具有更高的获得最优解几率.
A parallel machine batch process scheduling problem （PBPSP） integrating batching decision is investigated. The problem is converted into the fixed charge transportation problem （FCTP）. A genetic local search algorithm （GLSA） with intensification strategy of local search and escape strategy from local optimal solution is developed. The sorted edges attained by root-first search of spanning tree are used to encode spanning tree in the genetic local search algorithm. Efficient single point crossover operator appending edges to sub-tree is proposed. Network simplex method based local search is used to be the mutation of individual. To enhance the capacity of searching the global optimal solution, this paper presents an intensification strategy of local search that applies continuous random node local search to the current optimal solution and an escape strategy from local optimal solution based on random pivot mutation and random node local search. The results of computations demonstrate that the genetic local search algorithm is better than the permutation encoding genetic algorithm and the matrix encoding genetic algorithm on solution quality, and can find the optimal solution of all Benchmark problems. Moreover, the genetic local search algorithm is robust. Compared with the tabu heuristic search procecture, this algorithm can obtain more frequently the optimal solutions of the test problem instances.
出处
《软件学报》
EI
CSCD
北大核心
2006年第12期2589-2600,共12页
Journal of Software
基金
国家自然科学基金No.60573086
国家高技术研究发展计划(863)No.2003AA4Z3210
国家教育部博士点基金No.20030213027~~
关键词
间歇过程
调度
固定费用运输问题
生成树
遗传算法
局部搜索
batch process
scheduling
fixed charge transportation problem
spanning tree
genetic algorithm
local search
