Preemptive Scheduling with Release Times, Deadlines, and Due Times
Preemptive Scheduling with Release Times, Deadlines, and Due Times
复制标题
预先安排发布时间、截止日期和截止时间
DOI：
--
复制
发表时间：
1982
期刊：
影响因子：
--
通讯作者：
C. Martel
中科院分区：
文献类型：
--
作者：
C. Martel
给定n个工件，每个工件都有一个释放时间、一个截止时间和一个加工要求，研究了m台均匀机器上是否存在抢占调度问题，该调度能使每个工件在其释放时间和截止时间之间的时间间隔内完成.一个O（m/sup 2/n/sup 4/+n/sup 5/）算法，该算法使用网络流技术的概括，以构建这样的时间表，每当一个存在。然后，该算法与搜索技术一起使用，以找到一个最小化最大延迟的时间表。10个参考文献。
Given n jobs, each of which has a release time, a deadline, and a processing requirement, the problem of determining whether there exists a preemptive schedule on m uniform machines which completes each job in the time interval between its release time and its deadline is examined. An o(m/sup 2/n/sup 4/+n/sup 5/) algorithm is presented which uses a generalisation of network flow techniques to construct such a schedule whenever one exists. This algorithm is then used with search techniques to find a schedule which minimises maximum lateness. 10 references.