求解工件车间调度问题的一种新的邻域搜索算法

• 作者: 王磊 黄文奇
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 组合优化 NP难问题 工件车间调度 邻域搜索
• 年，卷（期）: 2005,（5）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 809-816
• 页数: 8页
• 分类号: TP18
• 字数: 8926字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2005.05.008

摘要

该文提出了一种新的求解工件车间调度(job shop scheduling)问题的邻域搜索算法.问题的目标是:在满足约束条件的前提下使得调度的makespan尽可能地小.定义了一种新的优先分配规则以生成初始解;定义了一种新的邻域结构;将邻域搜索跟单机调度结合在一起;提出了跳坑策略以跳出局部最优解并且将搜索引向有希望的方向.计算了当前国际文献中的一组共58个benchmark问题实例,算法的优度高于当前国外学者提出的两种著名的先进算法.其中对18个10工件10机器的实例,包括最著名的难解实例ft10,在可接受的时间内都找到了最优解.这些实例是当前文献中报导的所有规模为10工件10机器的实例.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王磊	华中科技大学计算机科学与技术学院计算机科学理论研究所	75	684	15.0	23.0
2	黄文奇	华中科技大学计算机科学与技术学院计算机科学理论研究所	88	1090	21.0	27.0