论文标题
平衡流动时间和能耗
Balancing Flow Time and Energy Consumption
论文作者
论文摘要
在本文中，我们研究了以下批处理计划模型：找到一个时间表，该时间表可以最大程度地减少$ n $统一长度工作的总流动时间，并使用发行时间和截止日期，其中该机器仅在最多$ k $同步的大小$ b $的$ k $同步批处理中积极处理工作。此类批处理计划模型的先前工作仅考虑了可行性，而无需考虑时间表的流动时间。但是，从调度程序的角度最小化成本的算法（例如，使处理器的活动时间最小化的算法都可能导致总流动时间为任意高\ cite {changgabowkhuller}的时间表。从客户的角度来看，此类时间表并不有价值。作为回应，我们的工作提供了动态程序，这些程序可以最大程度地减少受主动时间限制的流动时间。我们的主要贡献集中在有愉快的期限的工作上；对于此类工作实例，我们引入了动态程序，以实现单位工作的o $（b \ cdot k \ cdot n）$的运行时间和o $（b \ cdot k \ cdot n^5）$用于统一长度工作。这些结果改善了我们对Baptiste对不同的，经典的动态编程方法的修改。虽然修改后的DP在截止日期不可限制时可以工作，但此解决方案更昂贵，而运行时$ O（b \ cdot k^2 \ cdot n^7）$ \ cite {baptiste00}。
In this paper, we study the following batch scheduling model: find a schedule that minimizes total flow time for $n$ uniform length jobs, with release times and deadlines, where the machine is only actively processing jobs in at most $k$ synchronized batches of size at most $B$. Prior work on such batch scheduling models has considered only feasibility with no regard to the flow time of the schedule. However, algorithms that minimize the cost from the scheduler's perspective -- such as ones that minimize the active time of the processor -- can result in schedules where the total flow time is arbitrarily high \cite{ChangGabowKhuller}. Such schedules are not valuable from the perspective of the client. In response, our work provides dynamic programs which minimize flow time subject to active time constraints. Our main contribution focuses on jobs with agreeable deadlines; for such job instances, we introduce dynamic programs that achieve runtimes of O$(B \cdot k \cdot n)$ for unit jobs and O$(B \cdot k \cdot n^5)$ for uniform length jobs. These results improve upon our modification of a different, classical dynamic programming approach by Baptiste. While the modified DP works when deadlines are non-agreeable, this solution is more expensive, with runtime $O(B \cdot k^2 \cdot n^7)$ \cite{Baptiste00}.
