...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>RAIRO Operation Research >Polyhedral Reformulation Of A Scheduling Problem And Related Theoretical Results
【24h】

Polyhedral Reformulation Of A Scheduling Problem And Related Theoretical Results

机译：调度问题的多面体重构及相关理论结果

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

摘要

We deal here with a scheduling problem GPPCSP (Generalized Parallelism and Preemption Constrained Scheduling Problem) which is an extension of both the well-known Resource Constrained Scheduling Problem and the Scheduling Problem, with Disjunctive Constraints. We first propose a reformulation of GPPCSP: according to it, solving GPPCSP means finding a vertex of the Feasible Vertex Subset of an Antichain Polyhedron. Next, we state several theoretical results related to this reformulation process and to structural properties of this specific Feasible Vertex Subset (connectivity, ...). We end by focusing on the preemptive case of GPPCSP and by identifying specific instances of GPPCSP which are such that any vertex of the related Antichain Polyhedron may be projected on its related Feasible Vertex Subset without any deterioration of the makespan. For such an instance, the GPPCSP problem may be solved in a simple way through linear programming.
机译：我们在这里处理调度问题GPPCSP（广义并行和先占约束调度问题），它是众所周知的资源约束调度问题和调度问题的扩展，具有析取约束。我们首先提出一种重新定义GPPCSP的方式：据此，求解GPPCSP意味着找到反链多面体的可行顶点子集的顶点。接下来，我们陈述与该重新制定过程以及该特定可行顶点子集的结构特性（连接性，...）有关的一些理论结果。最后，我们着重讨论GPPCSP的先占情况，并确定GPPCSP的特定实例，以使相关的反链多面体的任何顶点都可以投射到其相关的可行顶点子集上，而不会使构建时间变差。对于这种情况，可以通过线性编程以简单的方式解决GPPCSP问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号