Brief Announcement: Nested Active-Time Scheduling
Brief Announcement: Nested Active-Time Scheduling
复制标题
简短公告：嵌套活动时间调度
DOI：
10.1145/3490148.3538554
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Umboh, Seeun William
中科院分区：
文献类型：
--
作者：
Cao, Nairen;Fineman, Jeremy T.;Li, Shi;Mestre, Julián;Russell, Katina;Umboh, Seeun William
活动时间调度问题考虑的是在并行机上调度具有窗口（发布时间和最后期限）的可抢占作业的问题，该并行机在每个时间步内最多可以调度到个作业。活动时间问题的目标是最小化活动步骤的数量，即，至少有一个作业被调度的时间步长。通过这种方式，当在每个离散步骤启动机器的成本固定时，活动时间对并行调度进行建模。本文对作业窗口为层状（嵌套）的活动时间调度问题的一种特殊情况提出了一个9/5近似算法。这一结果改进了以前的最佳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 tojobs 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.