...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Scheduling split intervals with non-uniform demands
【24h】

Scheduling split intervals with non-uniform demands

机译：调度具有非均匀需求的分割间隔

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

摘要

We study the problem of maximizing the throughput of jobs wherein each job consists of multiple tasks. Consider a system offering a capacity of one unit. We are given a set of jobs, each consisting of a sequence of r tasks. Each task is associated with a demand and an interval where it should be scheduled. Each job has a profit associated with it. The objective is to select a subset of jobs having the maximum profit such that at any point of time the cumulative demand of the selected jobs does not exceed the system capacity. Prior work has presented O(r)-approximation algorithm for two special cases: (i) unit demands - all tasks have a demand of one unit; (ii) uniform demands - for any job, all its constituent tasks have the same demand. We study the general setting wherein the tasks of a job can have nonuniform demands. We present an O(r)-approximation for the case where all the tasks have demands at most 1/2. The prior algorithms are based on the fractional local ratio technique, which we do not know how to generalize for the setting of non-uniform demands. Instead, we devise an algorithm based on the randomized rounding strategy. Our approach also provides alternative simpler algorithms for the unit and uniform demand settings. We next extend the algorithms to the more generic scenario wherein each task is associated with a processing time and a window consisting of release time and deadline, and design pseudo-polynomial time O(r)-approximation procedures. (C) 2020 Elsevier B.V. All rights reserved.
机译：我们研究了最大化作业吞吐量的问题，其中每个作业由多个任务组成。考虑一个提供一个单位容量的系统。我们得到了一组作业，每个作业由一系列r任务组成。每个任务都与一个需求和一个应该安排的时间间隔相关联。每项工作都有与之相关的利润。目标是选择利润最大的工作子集，以便在任何时间点，所选工作的累积需求不超过系统容量。先前的工作针对两种特殊情况提出了O（r）-近似算法：（i）单元需求-所有任务都有一个单元的需求；（ii）统一要求——对于任何工作，其所有组成任务都有相同的要求。我们研究工作任务可能具有不均匀需求的一般环境。对于所有任务的需求最多为1/2的情况，我们给出了一个O（r）-近似。先前的算法是基于分数局部比率技术，我们不知道如何将其推广到非均匀需求的设置。相反，我们设计了一种基于随机取整策略的算法。我们的方法还为单位和统一需求设置提供了其他更简单的算法。接下来，我们将算法扩展到更一般的场景，其中每个任务都与一个处理时间和一个由发布时间和截止日期组成的窗口相关联，并设计伪多项式时间O（r）-近似过程。（C） 2020爱思唯尔B.V.版权所有。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号