Cost-Oblivious Reallocation for Scheduling and Planning
Cost-Oblivious Reallocation for Scheduling and Planning
复制标题
用于调度和规划的成本无关的重新分配
DOI：
10.1145/2755573.2755589
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Gilbert
中科院分区：
文献类型：
--
作者：
M.E. Bender;M. Farach-Colton;S.P. Fekete;J. Fineman;S. Gilbert
在重新分配调度程序问题中，作业可能会随着时间的推移从系统中插入和删除。与传统的在线调度问题不同，在传统的在线调度问题中，作业的安排是不可变的，在重新分配问题中，调度可以调整，但需要付出一些代价。目标是保持近似最优的调度，同时最小化更改调度的重新分配成本。本文针对分配作业顶级（相同）服务器的问题给出了重新分配调度器，以便将完成时间总和最小化到最优常数因子内，长度 w 作业的摊销重新分配成本为 O(f(w)log3logΔ)，其中 Delta 是最长作业的长度，f() 是重新分配成本函数。我们的算法是成本无关的，这意味着该算法不是由 f() 参数化的，但它实现了任何 subadditivef() 的限制。每当f()是强次可加性时，重新分配成本变为O(f(w))。为了实现具有低重新分配成本的重新分配调度器，我们设计了ak游标稀疏表。该数据结构在数组中存储一组动态元素，并且结构中的插入和删除受到限制。该数据结构实现了插入和删除的摊余成本为O(log3k)，同时还保证数组的任何前缀都具有恒定的密度。请注意，此界限不依赖于元素数量 n，因此此数据结构（受限于 tok<<ncursors）优于一般稀疏表的 Ω(log2n) 下限。
In a reallocating-scheduler problem, jobs may be inserted and deleted from the system over time. Unlike in traditional online scheduling problems, where a job's placement is immutable, in reallocation problems the schedule may be adjusted, but at some cost. The goal is to maintain an approximately optimal schedule while also minimizing thereallocation costfor changing the schedule.This paper gives a reallocating scheduler for the problem of assigning jobs top(identical) servers so as to minimize the sum of completion times to within a constant factor of optimal, with an amortized reallocation cost for a length-wjob ofO(f(w)log3logΔ), where Delta is the length of the longest job andf() is the reallocation-cost function. Our algorithm is cost oblivious, meaning that the algorithm is not parameterized byf(), yet it achieves this bound for any subadditivef(). Wheneverf() is strongly subadditive, the reallocation cost becomesO(f(w)).To realize a reallocating scheduler with low reallocation cost, we design ak-cursor sparse table. This data structure stores a dynamic set of elements in an array, with insertions and deletions restricted tokcursors in the structure. The data structure achieves an amortized cost ofO(log3k) for insertions and deletions, while also guaranteeing that any prefix of the array has constant density. Observe that this bound does not depend on n, the number of elements, and hence this data structure, restricted tok<<ncursors, beats the lower bound of Ω(log2n) for general sparse tables.
登录
查看更多内容
重新调度以最大程度地减少数量不断变化的相同处理器的完工时间
DOI：
10.1002/nav.3800330414
发表时间：
1986
期刊：
Naval Research Logistics Quarterly
影响因子：
--
作者：
C. Tovey
通讯作者：
C. Tovey
规范密度控制
影响因子：
0.5
作者：
A. Itai;Irit Katriel
通讯作者：
Irit Katriel
重新优化的复杂性和近似
影响因子：
1.1
作者：
B. Escoffier;V. Bonifaci;G. Ausiello
通讯作者：
G. Ausiello
为本地修改的输入实例重用最佳 TSP 解决方案
DOI：
10.1007/978-0-387-34735-6_21
发表时间：
2006
期刊：
Naval Research Logistics Quarterly
影响因子：
--
作者：
Hans;L. Forlizzi;J. Hromkovic;Joachim Kneis;Joachim Kupke;Guido Proietti;P. Widmayer
通讯作者：
P. Widmayer
用于机器覆盖和包装的稳健 PTAS
DOI：
--
发表时间：
2010
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
M. Skutella;José Verschae
通讯作者：
José Verschae