• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Automated Planning and Scheduling(ICAPS 2006); 2006; >Exploiting the Power of Local Search in a Branch and Bound Algorithm for Job Shop Scheduling
【24h】

Exploiting the Power of Local Search in a Branch and Bound Algorithm for Job Shop Scheduling

机译：利用分支定界算法进行车间调度的本地搜索功能

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper presents three techniques for using an iterated local search algorithm to improve the performance of a state-of-the-art branch and bound algorithm for job shop scheduling. We use iterated local search to obtain (ⅰ) sharpened upper bounds, (ⅱ) an improved branch-ordering heuristic, and (ⅲ) and improved variable-selection heuristic. On randomly-generated instances, our hybrid of iterated local search and branch and bound outperforms either algorithm in isolation by more than an order of magnitude, where performance is measured by the median amount of time required to find a globally optimal schedule. We also demonstrate performance gains on benchmark instances from the OR library.
机译：本文介绍了三种使用迭代本地搜索算法来提高最新的分支定界算法的性能的技术，这些算法适用于作业车间调度。我们使用迭代局部搜索来获得（ⅰ）尖锐的上限，（ⅱ）改进的分支顺序启发式算法，和（ⅲ）以及改进的变量选择启发式算法。在随机生成的实例上，我们的迭代本地搜索和分支与绑定的混合在隔离度方面优于任一算法，其数量级要高于找到全局最佳计划所需的时间中位数。我们还展示了OR库中基准实例的性能提升。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号