A note on scheduling equal-length jobs to maximize throughput

被引：31

作者：

Chrobak, M ^{[1
]}

Dürr, C

Jawor, W

Kowalik, L

Kurowski, M

机构：

[1] Univ Calif Riverside, Dept Comp Sci, Riverside, CA 92521 USA

[2] Univ Paris 11, Rech Informat Lab, F-91405 Orsay, France

[3] Uniwersytet Warszawski, Inst Informat, PL-02097 Warsaw, Poland

来源：

JOURNAL OF SCHEDULING | 2006年 / 9卷 / 01期

基金：

美国国家科学基金会;

关键词：

Artificial Intelligence;

D O I：

10.1007/s10951-006-5595-4

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

An approach for scheduling of a problem using a polynomial-time algorithm technique, was described. The elegant feasibility algorithm of Carlier is based on dynamic programming and it processes jobs from left to right on the time-axis. The objective of the algorithm is to find a non-preemptive schedule that maximizes the number of jobs completed by their deadlines. Computing the minimum time to complete k jobs reduces the running time, as the size of the dynamic programming table and the time needed to compute a single entry are both reduced.

引用

页码：71 / 73

页数：3