Scheduling tree-structured tasks with restricted execution times

Jianzhong Du, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


In this article we show that scheduling a tree-structured task system with two execution times in order to minimize the schedule length is strongly NP-hard for an arbitrary number of processors. If the execution times are powers of some integer r>1, then the problem is NP-hard even for two processors.

Original languageEnglish (US)
Pages (from-to)183-188
Number of pages6
JournalInformation Processing Letters
Issue number4
StatePublished - Jul 29 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


  • NP-completeness
  • NP-hardness
  • multiprocessor scheduling
  • schedule length
  • tree-structured task system


Dive into the research topics of 'Scheduling tree-structured tasks with restricted execution times'. Together they form a unique fingerprint.

Cite this