论文标题
嵌套的活动时间安排
Nested Active-Time Scheduling
论文作者
论文摘要
活动时间安排问题考虑了在平行机器上使用Windows（发布时间和截止日期）安排可享有的作业的问题，该机器可以在每个时间段期间安排高达$ G $的作业。积极时间问题的目标是最大程度地减少活动步骤的数量，即至少安排了一项工作的时间段。通过这种方式，当每个离散步骤打开机器的固定成本时，主动时间模型并行计划。 本文提出了一种9/5- approximation算法，用于现场安排问题的特殊情况，其中作业窗口为层层（嵌套）。对于一般情况，此结果改善了以前的最佳2-焦点。
The active-time scheduling problem considers the problem of scheduling preemptible jobs with windows (release times and deadlines) on a parallel machine that can schedule up to $g$ jobs during each timestep. The goal in the active-time problem is to minimize the number of active steps, i.e., timesteps in which at least one job is scheduled. In this way, the active time models parallel scheduling when there is a fixed cost for turning the machine on at each discrete step. This paper presents a 9/5-approximation algorithm for a special case of the active-time scheduling problem in which job windows are laminar (nested). This result improves on the previous best 2-approximation for the general case.
