...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times
【24h】

The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times

机译：与时间有关的旅行推销员问题和与序列有关的设置时间的单机调度问题

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

摘要

In this paper, we consider scheduling problems on a single machine in a sequence dependent setup environment. For these problems, we introduce several integer programming formulations of varying size and strength. Computational experiments conducted on instances of 1 vertical bar s(ij)vertical bar Sigma C-j (i.e. minimizing total flow time on a single machine under sequence dependent setup times) and 1 vertical bar s(ij)vertical bar Sigma T-j (i.e. minimizing total tardiness on a single machine under sequence dependent setup times) illustrate the benefits of using stronger formulations, even though the computation of their LP relaxation is more time consuming. Incorporating these improved LP relaxation bounds, we propose an exact branch-and-bound algorithm able to solve instances of 1 vertical bar s(ij)vertical bar Sigma C-j and 1 vertical bar s(ij)vertical bar Sigma T-j having up to 50 and 45 jobs respectively.
机译：在本文中，我们考虑了在依赖序列的设置环境中在一台机器上的调度问题。对于这些问题，我们介绍了几种具有不同大小和强度的整数编程公式。在1个垂直条s（ij）垂直条Sigma Cj（即，在与序列相关的设置时间下，使一台机器上的总流动时间最小化）和1个垂直条s（ij）垂直条Sigma Tj（即，将总拖延度最小化）的实例上进行了计算实验在一台机器上在序列依赖的设置时间下）说明了使用更强大的配方的好处，即使计算它们的LP弛豫更为耗时。结合这些改进的LP松弛边界，我们提出了一种精确的分支定界算法，该算法能够求解1个垂直条s（ij）垂直条Sigma Cj和1个垂直条s（ij）垂直条Sigma Tj的实例，且最大不超过50。分别有45个职位。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号