• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Euro-Par Parallel Processing Conference; 20050830-0902; Lisbon(PT) >On-Line Bicriteria Interval Scheduling
【24h】

On-Line Bicriteria Interval Scheduling

机译：在线双标准间隔调度

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

摘要

We consider the problem of scheduling a sequence of intervals revealed on-line one by one in the order of their release dates on a set of k identical machines. Each interval i is associated with a processing time p_i and a pair of arbitrary weights (w_i~A, w_i~B) and may be scheduled on one of the k identical machines or rejected. The objective is to determine a valid schedule maximizing the sum of the weights of the scheduled intervals for each coordinate. We first propose a generic on-line algorithm based on the combination of two monocriteria on-line algorithms and we prove that it gives rise to a pair of competitive ratios that are function of the competitive ratios of the monocriteria algorithms in the input. We apply this technique to the special case where w_i~A = 1 and w_i~B = p_i for every interval and as a corollary we obtain a pair of constant competitive ratios.
机译：我们考虑的问题是，在k台相同的机器上安排按其发布日期的顺序逐个显示的间隔序列。每个间隔i与处理时间p_i和一对任意权重（w_i_A，w_i_B）相关联，并且可以被安排在k个相同机器之一上或被拒绝。目的是确定一个有效的计划表，以使每个坐标的计划间隔的权重之和最大化。我们首先基于两个单一准则在线算法的组合提出了一种通用的联机算法，并且证明了它产生了一对竞争比率，该竞争比率是输入中单一准则算法的竞争比率的函数。我们将这种技术应用于特殊情况，其中每个间隔w_i〜A = 1且w_i〜B = p_i，并且作为推论，我们获得了一对恒定的竞争比率。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号