摘要
修复约束满足算法(修复法)是在完整初始解的基础上不断对变量进行修复,最终得到可行解.对此,提出一种求解flow shop排序问题的改进修复法(IRCS_WT),通过采用新的变量表达方式,设计了一种以启发式优化规则为指导的变量选择算法(LWT),并采用一种变量互换算法(LTEE)保证算法的全局搜索性能.将新算法应用于31个标准算例,与传统算法及遗传算法的优化结果进行比较,结果表明在相同运算时间下改进算法具有明显的优越性.
Repair-based constraint satisfaction method is one of the two main categories of constraint satisfaction （CS） algorithms. It starts with an arbitrary completed solution, and then resolves conflicts by local repair. An improved repair-based constraint satisfaction （IRCS_WT） method for flow shop scheduling is proposed. In IRCS_WT, a heuristic rule of largest weighted tardiness priority （LWT） is proposed for variables ordering procedure, and a new heuristic of largest tardy and early variables exchanging （LTEE） is designed to escape from local optima. Computational experiments of 31 flow shop scheduling problems are conducted to compare the IRCS_WT with other two heuristic methods, extended NEH and filtered beam search （FBS）, as well as genetic algorithm （GA）. The results show that IRCS_WT significantly outperforms the competitors with the same running time.
出处
《控制与决策》
EI
CSCD
北大核心
2008年第8期850-856,共7页
Control and Decision
基金
国家自然科学基金项目(70771003,70521001)
新世纪优秀人才支持计划项目(NCT040175)
关键词
约束满足
修复法
FLOW
shop排序问题
加权总延误
Constraint satisfaction
Repair-based method
Flow shop scheduling
Total weighted tardiness
