• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Automated Planning and Scheduling(ICAPS 2006); 2006; >Tractable Optimal Competitive Scheduling
【24h】

Tractable Optimal Competitive Scheduling

机译：可牵引最优竞争调度

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

摘要

In this paper we describe the problem of Optimal Competitive Scheduling, which consists of activities that compete for a shared resource. The objective is to choose a subset of activities to schedule, sequence them, and decide how much time they are allowed, in such a way that temporal and resource constraints are satisfied and overall schedule quality is maximized. While most such problems are NP-complete, very restricted versions of this problem are known to be tractable. In this work we describe tractable variations on this problem that correspond to realistic scheduling problems. The first class of tractable OCS problems arises due to limitations on the objective function that permit casting the problem as a Linear Program; with one additional assumption on activity feasibility windows, we identify a problem class where an optimal activity ordering can be found in polynomial time. The second class arises by reformulation of the problem as a Valued Constraint Satisfaction Problem and exploiting known results on tractability. We describe implementations of special-purpose algorithms designed to solve tractable OCS problems, and identify different solver performance characteristics based on properties of the problem instances.
机译：在本文中，我们描述了最佳竞争性调度的问题，该问题由竞争共享资源的活动组成。目的是选择活动的一个子集，以安排时间，对它们进行排序并确定允许的时间，这样可以满足时间和资源上的限制，并使总体计划质量最大化。尽管大多数此类问题都是NP完全的，但已知该问题的非常受限制的版本很容易解决。在这项工作中，我们描述了这个问题上的可解决的变化，这些变化与现实的调度问题相对应。第一类可处理的OCS问题是由于对目标函数的限制而产生的，因此可以将该问题转换为线性程序。在活动可行性窗口的另一假设下，我们确定了一个可以在多项式时间内找到最佳活动顺序的问题类别。第二类是通过将问题重新表述为“重要约束满足问题”并利用已知的易处理性结果而产生的。我们描述了旨在解决棘手的OCS问题的专用算法的实现，并根据问题实例的属性标识了不同的求解器性能特征。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号