| 摘要: |
| 研究了一类集成分批的并行机间歇过程调度问题(parallel machine batch process scheduling problem,简称PBPSP),将此问题转化为固定费用运输问题(6xed charge transportation problem,简称FCTP)后,提出了具有集中邻域搜索机制和局部最优逃逸机制的遗传局部搜索算法(genetic local search algorithm,简称GLSA).GLSA算法用先根遍历边排列模式编码生成树解,具有高效的子树补充式单点交叉操作.将基于网络单纯型方法的邻域搜索作为变异算子,并提出了连续随机节点邻域搜索的集中邻域搜索策略以及随机旋转变异与全局邻域搜索相结合的局部最优逃逸策略,极大地强化了遗传局部搜索算法的全局寻优能力.实验表明:GLSA算法获得的解质量优于基于排列编码的遗传算法和基于矩阵编码的遗传算法,得到了所有Benchmark问题的最优解,且具有高鲁棒性.针对一定规模的FCTP问题,GLSA算法比Tabu启发式搜索算法具有更高的获得最优解几率. |
| 关键词: 间歇过程 调度 固定费用运输问题 生成树 遗传算法 局部搜索 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant No.60573086 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2003AA4Z3210 (国家高技术研究发展计划(863)); the National Research Foundation for the Doctor |
|
| A Genetic Local Search Algorithm for the Parallel Machine Batch Process Scheduling Problem |
|
XU Xiao-Fei,ZHAN De-Chen,XU Xiao-Fei
|
| Abstract: |
| 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 procedure, this algorithm can obtain more frequently the optimal solutions of the test problem instances. |
| Key words: batch process scheduling fixed charge transportation problem spanning tree genetic algorithm local search |
