Complexity of scheduling tasks with time-dependent execution times

Kevin I.J. Ho; Joseph Y.T. Leung; W. D. Wei

doi:10.1016/0020-0190(93)90175-9

Complexity of scheduling tasks with time-dependent execution times

Kevin I.J. Ho, Joseph Y.T. Leung, W. D. Wei

Research output: Contribution to journal › Article › peer-review

94 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	315-320
Number of pages	6
Journal	Information Processing Letters
Volume	48
Issue number	6
DOIs	https://doi.org/10.1016/0020-0190(93)90175-9
State	Published - Dec 20 1993
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

Algorithms
Deadline
Feasible schedule
NP-complete
Nonpreemptive schedule
Polynomial-time algorithm
Release time
Single processor

Access to Document

10.1016/0020-0190(93)90175-9

Cite this

@article{61ce755520a049c9b73d32cf85b89eaf,

title = "Complexity of scheduling tasks with time-dependent execution times",

abstract = "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.",

keywords = "Algorithms, Deadline, Feasible schedule, NP-complete, Nonpreemptive schedule, Polynomial-time algorithm, Release time, Single processor",

author = "Ho, {Kevin I.J.} and Leung, {Joseph Y.T.} and Wei, {W. D.}",

note = "Funding Information: * Research supported in part by the ONR grant N00014-91-J-1383 and in part by a grant from Texas Instruments, Inc. * * Corresponding author. ** * On leave from Department of Mathematics, University, Chengdu, 610064, China.",

year = "1993",

month = dec,

day = "20",

doi = "10.1016/0020-0190(93)90175-9",

language = "English (US)",

volume = "48",

pages = "315--320",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - Complexity of scheduling tasks with time-dependent execution times

AU - Ho, Kevin I.J.

AU - Leung, Joseph Y.T.

AU - Wei, W. D.

N1 - Funding Information: * Research supported in part by the ONR grant N00014-91-J-1383 and in part by a grant from Texas Instruments, Inc. * * Corresponding author. ** * On leave from Department of Mathematics, University, Chengdu, 610064, China.

PY - 1993/12/20

Y1 - 1993/12/20

N2 - 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.

AB - 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.

KW - Algorithms

KW - Deadline

KW - Feasible schedule

KW - NP-complete

KW - Nonpreemptive schedule

KW - Polynomial-time algorithm

KW - Release time

KW - Single processor

UR - http://www.scopus.com/inward/record.url?scp=0027885153&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027885153&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(93)90175-9

DO - 10.1016/0020-0190(93)90175-9

M3 - Article

AN - SCOPUS:0027885153

SN - 0020-0190

VL - 48

SP - 315

EP - 320

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

Complexity of scheduling tasks with time-dependent execution times

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this