差异工件平行机批调度问题的SAGA  

Minimizing makespan on parallel batching machines with non-identical job sizes using SAGA

作　　者：舒锋[1] 陈华平[1] 杜冰[1] 李小林[1] 操张进[1] 

机构地区：[1]中国科学技术大学管理学院,合肥230026

出　　处：《计算机应用研究》2010年第12期4526-4529,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(70821001);国家博士点基金资助项目(200803580024)

摘　　要：为了求解差异工件平行机批调度问题,提出了一种模拟退火遗传算法(simulated annealing genetic algo-rithm,SAGA)。将模拟退火算法(simulated annealing,SA)的状态转移操作引入基于最优保留的遗传算法(geneticalgorithm,GA)中,作为局部搜索算子,以避免算法陷入局部最优,也有效地发挥了SA和GA在局部搜索与全局搜索能力方面的优势。为了解决GA迭代后期适应函数难以区分一些适应度接近的个体这个问题,SAGA分两阶段标定适应函数,在进化后期采用了一个加速适应函数。同时,将缺点较多的单切点交叉方式改换为效果更好的双切点交叉方式。实验结果表明,与以往文献中的GA、BFLPT(best-fit longest processing time)和FFLPT(first-fit longest processing time)启发式规则等相比,SAGA是有效的。This paper proposed a SAGA to minimize makespan on parallel batch processing machines with non-identical job sizes. Introduced the state transition operation in SA to improve local search in the GA based on an elitist selection strategy. By combining the advantages of both algorithms,SAGA was able to strike a balance between local search and global search,and wouldn＇t fall into local optimum. In addition,to solve the problem that GA was unable to effectively distinguish chromosomes with similar fitness values in the later iterations,this paper defined the fitness function in two stages. The fitness function in the second stage could accelerate the convergence of the algorithm. Further defined the crossover operator using more effective two-point crossover instead of single-point crossover. The experimental results show that the proposed SAGA outperforms FFLPT,BFLPT and traditional GA addressed in the previous work.

关 键 词：调度 批处理机 模拟退火遗传算法 组合优化 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]