COMPLEXITY OF SCHEDULING TASKS WITH TIME-DEPENDENT EXECUTION TIMES

Authors
HO KIJ LEUNG JYT WEI WD
Citation
Kij. Ho et al., COMPLEXITY OF SCHEDULING TASKS WITH TIME-DEPENDENT EXECUTION TIMES, Information processing letters, 48(6), 1993, pp. 315-320
Citations number
7
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
48
Issue
6
Year of publication
1993
Pages
315 - 320
Database
ISI
SICI code
0020-0190(1993)48:6<315:COSTWT>2.0.ZU;2-4
Abstract
A new model of task system in which the execution time of a task depen ds on its starting time is considered. It is shown that the feasibilit y 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)-tim e algorithm is given for a set of tasks with identical release times a nd deadlines. These two results give a sharp boundary delineating the complexity of the problem.