Scheduling tree-structured tasks with restricted execution times

Jianzhong Du, Joseph Leung

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

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
Volume28
Issue number4
DOIs
StatePublished - Jul 29 1988

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics

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

Cite this