Complexity of scheduling tasks with time-dependent execution times

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

Research output: Contribution to journalArticle

84 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 languageEnglish (US)
Pages (from-to)315-320
Number of pages6
JournalInformation Processing Letters
Volume48
Issue number6
DOIs
StatePublished - Dec 20 1993

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Signal Processing
  • Computer Science Applications

Keywords

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

Cite this