Speed Scaling Functions for Flow Time Scheduling Based on Active Job Count
Speed Scaling Functions for Flow Time Scheduling Based on Active Job Count
复制标题
基于活动作业计数的流程时间调度的速度缩放功能
DOI：
10.1007/978-3-540-87744-8_54
复制
发表时间：
2008
影响因子：
4.6
通讯作者：
Prudence W. H. Wong
中科院分区：
文献类型：
--
作者：
T. Lam;Lap;I. K. To;Prudence W. H. Wong
在动态速度缩放模型中，研究了以最小化流时间和能量消耗为目标的在线调度问题。我们设计了依赖于活动作业数量的新的速度缩放函数，取代了文献中依赖于活动作业剩余工作量的现有速度缩放函数。新的速度功能更稳定，效率也更高。它们可以支持更好的作业选择策略，以提高现有算法的竞争比[8,5]，更重要的是，消除了对额外速度的要求。这些函数进一步将自己与其他函数区分开来，因为它们可以很容易地用于非千里眼模型（在非千里眼模型中，只有在任务完成时才知道任务的大小）。作为第一步，我们研究了非透视模型中批处理作业（即具有相同释放时间的作业）的调度，并提出了最小化流时间加能量（以及加权流时间加能量）的第一个竞争算法；性能接近最优。
We study online scheduling to minimize flow time plus energy usage in the dynamic speed scaling model. We devise new speed scaling functions that depend on the number of active jobs, replacing the existing speed scaling functions in the literature that depend on the remaining work of active jobs. The new speed functions are more stable and also more efficient. They can support better job selection strategies to improve the competitive ratios of existing algorithms [8,5], and, more importantly, to remove the requirement of extra speed. These functions further distinguish themselves from others as they can readily be used in the non-clairvoyant model (where the size of a job is only known when the job finishes). As a first step, we study the scheduling of batched jobs (i.e., jobs with the same release time) in the non-clairvoyant model and present the first competitive algorithm for minimizing flow time plus energy (as well as for weighted flow time plus energy); the performance is close to optimal.