一种受限于给定最大延误上界的单目标启发式算法  

A Single-Objective Heuristic Algorithm Subjected to a Given Maximum Tardiness Upper Bound

作　　者：池淑珍[1] 周春光[1] 张长胜[1] 杨草原[1] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012

出　　处：《吉林大学学报（理学版）》2010年第5期805-810,共6页Journal of Jilin University:Science Edition

基　　金：国家自然科学基金(批准号:60673099;60873146);国家高技术研究发展计划863项目基金(批准号:2009AA02Z307;2007AA04Z114)

摘　　要：基于有效求解在未超过给定的最大延误上界这一约束条件下最小化总完工时间的置换流水车间调度问题,提出一种新的迭代贪心启发式算法IG_CZ,通过结合全局和局部优化策略获得最优解或近似最优解.并在Taillard基准测试集上对不同规模的问题进行算法性能测试,实验结果表明,IG_CZ算法不仅简单、易于实现,而且求解能力及解的质量优于对比的其他算法。In order to solve the permutation flowshop problem to minimize makespan subjected to a given maximum tardiness upper bound effectively,we presented a new iterated greedy heuristic algorithm IG_CZ by combining global and local optimization to obtain optimal solution or near-optimum solution.Finally,IG_CZ was tested on different scale benchmarks based on Taillard standard test sets.The result shows that IG_CZ is simple,implemented easily,and the solution quality and the ability to gain solution of IG_CZ precede other compared algorithms.

关 键 词：流水车间调度 迭代贪心 完工时间 最大延误 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]