Optimal multiprocessor task scheduling using dominance and equivalence relations

Hong Chich Chou, Chung-Ping Chung*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

We propose an optimization scheme for unit-execution-time task scheduling on multiprocessors. In this scheme, dominance, semi-dominance, equivalence and semi-equivalence relations between tasks are first defined. The solution tree technique is adopted to keep track of the unfinished sub-schedules. We prove that when certain conditions are satisfied, a sub-schedule need not be explored further, since it cannot lead to a schedule better than some others. An algorithm that avoids generating such non-optimal schedules is presented. Then we conduct experiments to show the promise of our scheme in reducing solution space. Another advantage of this scheme is its extensibility. This scheme can easily be applied to other scheduling problems by simply adding additional constraints to the original definitions of the dominance, semi-dominance, equivalence and semi-equivalence relations.

Original languageEnglish
Pages (from-to)463-475
Number of pages13
JournalComputers and Operations Research
Volume21
Issue number4
DOIs
StatePublished - 1 Jan 1994

Fingerprint Dive into the research topics of 'Optimal multiprocessor task scheduling using dominance and equivalence relations'. Together they form a unique fingerprint.

Cite this