Task Scheduling with Restricted Preemptions
Task Scheduling with Restricted Preemptions
复制标题
具有限制抢占的任务调度
DOI：
10.1007/3-540-56891-3_37
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
Reiner Hirschberg
中科院分区：
文献类型：
--
作者：
K. Ecker;Reiner Hirschberg
在分时系统和多处理操作系统中的一个基本问题是为给定的一组任务找到一个最优调度。在本文中，我们分析了一般抢占式调度问题的限制版本的复杂性。我们引入了一个调度模型，保证抢占的任务后，只有合理的一部分任务已被处理。结果表明，这个问题一般是NP难的，但可以找到非常好的近似算法，特殊情况下可以在多项式时间内精确求解。
One of the basic problems in time sharing systems and multiprocessing operating systems is to find an optimal schedule for a given set of tasks. In this paper we analyze the complexity of a restricted version of the general preemptive scheduling problem. We introduce a scheduling model that guarantees that preemption of a task is only possible after a reasonable part of the task has been processed. It turns out that this problem isNP-hard in general, but very good approximation algorithms can be found and special cases can be solved exactly in polynomial time.