改进的Great Deluge算法求解流水车间调度  

An Advanced Great Deluge Algorithm for Flow Shop Scheduling

作　　者：刘通[1] 严洪森[2] 李金坚[1] 

机构地区：[1]东南大学复杂工程系统测量与控制教育部重点实验室,江苏南京210096 [2]东南大学自动化学院,江苏南京210096

出　　处：《计算机技术与发展》2010年第1期143-146,171,共5页Computer Technology and Development

基　　金：国家863计划资助项目(2007AA04Z112);国家自然科学基金资助项目(50875046)

摘　　要：Great deluge algorithm(GDA)是由Threshold accepting algorithm(TAA)演变而来的一种新的巨集启发式算法,它的实现只需要一个参数的设定。目前,GDA在车间调度优化方面的应用还很少,文中对其改进后将其应用于解决流水车间调度问题,并通过实例仿真对其优化效果进行了评价。文中先将算法按原有形式实现,但优化效果不佳;后对算法提出改进策略:即将算法中唯一参数的值设为与优化过程中出现的一个差值成正比例变化(原算法中设为一个定值),并在此基础上对算法加入最优方案保存策略,实例的仿真结果表明,这一改进有效地克服了原算法求解该问题时出现的"过早收敛"现象,大大提高了算法的全局满意度,对解决该类问题有很好的效果,而在加入最优方案保存策略后,算法对该问题的优化效果得到进一步提高。As a new heuristic method for large-scale combinatorial optimization,great deluge algorithm（GDA） can be traced back to threshold accepting algorithm（TAA）,and its implementation needs only one parameter.So far,GDA has found few applications in the field of workshop scheduling.Improve on it and apply it to solving flow shop scheduling problems.Through simulation examples the evaluation is given on its optimization effect.The algorithm is firstly implemented in its original form,but unfavorable results are obtained.Then, an effective improvement is put forward on it： let the value of the only parameter in the algorithm be direct proportional to one difference appearing in the process of optimization （ the parameter is set a constant in the original implementation of the algorithm）. And on the basis of this, the strategy of tonserving the optimal allocation is adopted in tbe algorithm. The simulation results indicate that, this improvement can effectively overcome the shortcoming of ＂premature convergence＂ the original algorithm emerges while solving this problem, and therefore it greatly enbances the global satisfaction of the algorithm and is very suitable for solving this problem. And with the strategy of conserving the optimal allocation, the algorithm can solve this problem further better.

关 键 词：巨集启发式算法 流水车间 正比例 过早收敛 全局满意度 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]