A NOTE ON SINGLE-PROCESSOR SCHEDULING WITH TIME-DEPENDENT EXECUTION TIMES

被引：27

作者：

CHEN, ZL

机构：

[1] Department of Civil Engineering and Operations Research, Princeton University, Princeton

来源：

OPERATIONS RESEARCH LETTERS | 1995年 / 17卷 / 03期

关键词：

SCHEDULING; SINGLE-PROCESSOR; DYNAMIC PROGRAMMING; POLYNOMIAL-TIME ALGORITHM;

D O I：

10.1016/0167-6377(94)00058-E

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider a single-processor scheduling model where the execution time of a task is a decreasing linear function of its starting time. The complexity of the problem of minimizing the number of late tasks remains unknown for a set of tasks with identical due dates. We present an O(n(2))-time dynamic programming algorithm for solving this problem.

引用

页码：127 / 129

页数：3