Scheduling chain-structured tasks to minimize makespan and mean flow time

Jianzhong Du, Joseph Y.T. Leung, Gilbert H. Young

Research output: Contribution to journalArticlepeer-review

83 Scopus citations

Abstract

We consider the problem of scheduling a set of chains onm 〉 1 identical processors with the objectives of minimizing the makespan and the mean flow time. We show that finding a nonpreemptive schedule with the minimum makespan is strongly NP-hard for each fixedm 〉 1, answering the open question of whether this problem is strongly NP-hard for trees. We also show that finding a nonpreemptive schedule with the minimum mean flow time is strongly NP-hard for each fixedm 〉 1, improving the known strong NP-hardness results for in-trees and out-trees. Finally, we generalize the result of McNaughton, showing that preemption cannot reduce the mean weighted flow time for a set of chains. The last two results together imply that finding a preemptive schedule with the minimum mean flow time is also strongly NP-hard for each fixedm 〉 1, answering another open question on the complexity of this problem for trees.

Original languageEnglish (US)
Pages (from-to)219-236
Number of pages18
JournalInformation and Computation
Volume92
Issue number2
DOIs
StatePublished - 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Scheduling chain-structured tasks to minimize makespan and mean flow time'. Together they form a unique fingerprint.

Cite this