• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国政府科技报告 >Greedy On-Line Algorithm for the K-Track Assignment Problem
【24h】

Greedy On-Line Algorithm for the K-Track Assignment Problem

机译：K-Track分配问题的贪婪在线算法

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

摘要

Given a collection of n jobs that are represented by intervals, the authors seek a maximal feasible assignment of the jobs to k machines such that not more than c(M) intervals overlap pairwise on any machine M and that a job is only assigned to a machine if it fits into one of several prescribed time windows for that machine. The authors analyze an online version of this NP-complete problem and exhibit an algorithm that achieves at least half of the (theoretical) optimum. In a more detailed analysis, the authors bound the performance of their algorithm by an additive term that only depends on the time window structure of the machines (but not on the number of jobs). In the case where each machine M has capacity c(M) = 1, the authors bound implies that their algorithm loses at most k - 1 jobs relative to the optimum. The authors show by an explicit construction that the bound is tight for greedy on-line algorithms.

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号