具有最大总加权满意度的单机调度问题的dynasearch算法

• 作者: 冯大光 唐立新
• 来源期刊: 管理科学学报
• 学科: 工学
• 关键词: 调度 满意程度 VLNS (very large scale neighborhood search) dynasearch 迭代局域搜索
• 年，卷（期）: 2006,（4）
• 所属期刊栏目: 论文
• 页码范围: 40-50,57
• 页数: 12页
• 分类号: TP29
• 字数: 9071字
• 语种: 中文
• DOI: 10.3321/j.issn:1007-9807.2006.04.006

摘要

研究了总加权满意程度最大化的单机调度问题.对最优解的性质进行分析和证明,提出该类问题的统治规则.提出该问题新的基于dynasearch 邻域的迭代局域搜索算法(ILS).算法主要特点:1)dynasearch 是基于多摄动的思想,即一次可以做多个相互独立的交换(或插入);2)用动态规划获得最优dynasearch移动;3)ILS采用随机kick 策略对局部最优解进行摄动,然后继续迭代.实现了该问题的两种dynaearch算法;把两种dynasearch算法与统治规则相结合;在进行kick时引入误差限制.实验表明:嵌入统治规则的算法优于没有统治规则的算法;基于dynasearch交换的ILS 优于基于dynasearch插入的ILS;dynaearch算法要优于以交换为邻域的多初始点改进算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐立新	东北大学物流优化与控制研究所	106	2154	24.0	41.0
2	冯大光	东北大学教育部流程工业实验室	12	53	4.0	6.0