COMPLEXITY OF SCHEDULING TASKS WITH TIME-DEPENDENT EXECUTION TIMES

被引：92

作者：

HO, KIJ ^{[1
]}

LEUNG, JYT ^{[1
]}

WEI, WD ^{[1
]}

机构：

[1] UNIV NEBRASKA LINCOLN,DEPT COMP SCI & ENGN,LINCOLN,NE 68588

来源：

INFORMATION PROCESSING LETTERS | 1993年 / 48卷 / 06期

关键词：

NP-COMPLETE; ALGORITHMS; POLYNOMIAL-TIME ALGORITHM; NONPREEMPTIVE SCHEDULE; RELEASE TIME; DEADLINE; FEASIBLE SCHEDULE; SINGLE PROCESSOR;

D O I：

10.1016/0020-0190(93)90175-9

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A new model of task system in which the execution time of a task depends on its starting time is considered. It is shown that the feasibility problem on a single processor is NP-complete for a set of tasks with identical release times and two distinct deadlines. An O(n log n)-time algorithm is given for a set of tasks with identical release times and deadlines. These two results give a sharp boundary delineating the complexity of the problem.

引用

页码：315 / 320

页数：6