| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | 求解工件车间调度问题的一种新的邻域搜索算法 |
| 作者 | 王磊 黄文奇 |
| 作者单位 | (华中科技大学计算机科学与技术学院计算机科学理论研究所 武汉 430074 ) |
| 发表年份 | 2005 |
| 发表月份 | 5期(809—816) |
| 文章摘要 | 摘要 该文提出了一种新的求解工件车间调度(job shop scheduling)问题的邻域搜索算法.问题的目标是：在满足约束条件的前提下使得调度的makespan尽可能地小.定义了一种新的优先分配规则以生成初始解；定义了一种新的邻域结构；将邻域搜索跟单机调度结合在一起；提出了跳坑策略以跳出局部最优解并且将搜索引向有希望的方向.计算了当前国际文献中的一组共58个benchmark问题实例，算法的优度高于当前国外学者提出的两种著名的先进算法.其中对18个10工件10机器的实例，包括最著名的难解实例ft10，在可接受的时间内都找到了最优解.这些实例是当前文献中报导的所有规模为10工件10机器的实例. 关键词 组合优化；NP难问题；工件车间调度；邻域搜索 中图法分类号 TP18 |