A parallel optimization algorithm for minimum execution‐time multiprocessor scheduling problem

DOI

Search this article

Description

<jats:title>Abstract</jats:title><jats:p>This paper proposes a parallel optimization algorithm PDF/IHS for the minimum execution‐time multiprocessor scheduling problem which is a strong NP‐hard optimization problem. PDF/IHS is a parallelization and efficient implementation of the only practical optimization algorithm DF/IHS among those which have been proposed for this scheduling problem. In PDF/IHS, processors perform depth‐first search in parallel on a heuristically generated search tree in such a way that it is searched hierarchically from the left‐ and right‐hand sides.</jats:p><jats:p>The effectiveness of PDF/IHS has been verified by simulation and practical parallel processing on Alliant FX4. As a result, it has been recognized that most of the problems which required a long time by DF/IHS can be solved approximately in time 1/<jats:italic>m</jats:italic> by PDF/IHS using <jats:italic>m</jats:italic> processors. Moreover, even for a problem which required a very long time or could not be solved in a practical time by DF/IHS, it has been verified that PDF/IHS can give solutions in time less than 1/<jats:italic>m</jats:italic>.</jats:p>

Journal

Details 詳細情報について

Report a problem

Back to top