基于启发式规则的新型进化算法在流水车间调度中的应用  

An Improved Evolutionary Algorithm Based on Heuristic Rules for Flow Shop Scheduling

作　　者：牛群[1] 顾幸生[1] 

机构地区：[1]华东理工大学自动化研究所,上海200237

出　　处：《华东理工大学学报（自然科学版）》2006年第12期1472-1477,共6页Journal of East China University of Science and Technology

基　　金：国家863高技术研究发展计划(2002AA412610);国家自然科学基金项目(60274043);上海市科委重大科技攻关项目(04dz11008)

摘　　要：针对流水车间调度这一典型的NP难问题,采用了一种新型进化算法——DNA进化算法进行求解,并对算法做了改进。改进的DNA进化算法中引入了交换操作以更好地搜索解空间,并采用黄金分割率控制变异个体的数目。同时为了进一步提高搜索性能,采用一种新颖的启发式规则产生初始种群。以50个T aillard基准问题进行仿真,并与遗传算法进行了详细比较,仿真结果表明:改进的DNA进化算法具有更好的求解性能以及更高的运算效率。A novel evolutionary algorithm, DNA evolutionary algorithm, is improved to solve the problems of Flow Shop Scheduling that are well known to be NP-hard. The exchange operation is adopted to enlarge the scope of the solutions, and the golden section is utilized to control the number of the mutation individuals. Meanwhile, a new heuristic rule is proposed to improve the initial reproduction and enhance the searching efficiency. Finally, the present algorithm is tested on 50 famous tailand benchmarks. The simulation results show that the proposed algorithm is more effective compared with genetic algorithm.

关 键 词：FLOW shop调度 DNA进化算法 启发式规则 黄金分割率 

分 类 号：F273[经济管理—企业管理]