• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>BioTechnology: An Indian Journal >Study of RLT-enhanced and lifted formulations for the job-shop scheduling problem
【24h】

Study of RLT-enhanced and lifted formulations for the job-shop scheduling problem

机译：关于车间作业调度问题的RLT增强和提升公式的研究

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper, we propose novel continuous nonconvex as well as lifted discrete formulations of the notoriously challenging class of job-shop scheduling problems with the objective of minimizing the maximum completion time. In particular, we develop an RLT-enhanced continuous nonconvex model for the job-shop problem based on a quadratic formulation of the job sequencing constraints on machines. The tight linear programming relaxation that is induced by this formulation is then embedded in a globally convergent branch-and-bound algorithm. Furthermore, we design another novel formulation for the job-shop scheduling problem that possesses a tight continuous relaxation, where the non-overlapping job sequencing constraints onmachines are modeled via a lifted asymmetric traveling salesman problem(ATSP) construct, and specific sets of valid inequalities and RLT-based enhancements are incorporated to further tighten the resulting mathematical program.
机译：在本文中，我们提出了新颖的连续非凸以及提出的具有挑战性的一类作业车间调度问题的离散公式，目的是最大程度地减少最大完成时间。特别是，我们基于机器上作业排序约束的二次公式，为作业车间问题开发了RLT增强的连续非凸模型。然后，将由该公式引起的紧密线性规划松弛嵌入到全局收敛的分支定界算法中。此外，我们为作业车间调度问题设计了另一种新颖的公式，该公式具有紧密的连续松弛，其中机器上的非重叠作业排序约束是通过解除非对称旅行商问题（ATSP）构造和有效不等式的特定集合来建模的以及基于RLT的增强功能，可以进一步收紧所得的数学程序。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号