A general framework for handling commitment in online throughput maximization
A general framework for handling commitment in online throughput maximization
复制标题
处理在线吞吐量最大化承诺的通用框架
DOI：
10.1007/s10107-020-01469-2
复制
发表时间：
2020
影响因子：
2.7
通讯作者：
Stein, Cliff
中科院分区：
文献类型：
--
作者：
Chen, Lin;Eberle, Franziska;Megow, Nicole;Schewior, Kevin;Stein, Cliff
我们研究了一个基本的在线就业准入问题，最后期限的工作到达网上随着时间的推移，在其发布日期，任务是确定一个抢占式单服务器的时间表，最大限度地提高按时完成的工作数量。为了规避已知的不可能的结果，我们做了一个标准的松弛假设，通过这个假设，调度一个作业的可行时间窗口至少是它的处理时间的倍。我们量化的影响，不同的供应商的承诺要求在线算法的性能。我们的主要贡献是一个通用的算法框架，在线工作录取和没有承诺。没有承诺，我们的算法与竞争比是最好的可能（确定性）这个问题。对于承诺模型，我们给出了第一个非平凡性能界。如果承诺的决定必须在一个工作的松弛变得小于其大小的一小部分，我们证明了一个竞争比，为。当提供者必须在启动作业时提交时，我们的界限是。最后，我们观察到，与承诺的调度的限制，以“未加权”的吞吐量模型是必不可少的，如果工作有单独的权重，我们排除了竞争力的确定性算法。
We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-server schedule which maximizes the number of jobs that complete on time. To circumvent known impossibility results, we make a standard slackness assumption by which the feasible time window for scheduling a job is at leasttimes its processing time, for some. We quantify the impact that different provider commitment requirements have on the performance of online algorithms. Our main contribution is one universal algorithmic framework for online job admission both with and without commitments. Without commitment, our algorithm with a competitive ratio ofis the best possible (deterministic) for this problem. For commitment models, we give the first non-trivial performance bounds. If the commitment decisions must be made before a job’s slack becomes less than a-fraction of its size, we prove a competitive ratio of, for. When a provider must commit upon starting a job, our bound is. Finally, we observe that for scheduling with commitment the restriction to the “unweighted” throughput model is essential; if jobs have individual weights, we rule out competitive deterministic algorithms.
登录
查看更多内容
如何安排何时需要购买能源
DOI：
10.1007/978-3-642-15369-3_27
发表时间：
2010
期刊：
SIAM J. Comput.
影响因子：
--
作者：
K. Pruhs;C. Stein
通讯作者：
C. Stein
DOI：
10.1145/2935764.2935786
发表时间：
2016-07
期刊：
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Lin Chen;Nicole Megow;Kevin Schewior
通讯作者：
Lin Chen;Nicole Megow;Kevin Schewior
MOCA：一种用于实时系统调度的多处理器在线竞争算法
DOI：
10.1109/real.1993.393503
发表时间：
1993
期刊：
1993 Proceedings Real-Time Systems Symposium
影响因子：
--
作者：
G. Koren;D. Shasha
通讯作者：
D. Shasha
影响因子：
1.1
作者：
N. Bansal;H. Chan;K. Pruhs
通讯作者：
K. Pruhs
在线调度可并行作业以最大化吞吐量
DOI：
--
发表时间：
2018
期刊：
LATIN 2018: Theoretical Informatics
影响因子：
--
作者：
Agrawal, Kunal;Li, Jing;Lu, Kefu;Moseley, Benjamin
通讯作者：
Moseley, Benjamin