TY - JOUR
T1 - A parallel optimization algorithm for minimum execution‐time multiprocessor scheduling problem
AU - Kasahara, Hironori
AU - Itoh, Atsusi
AU - Tanaka, Hisamitsu
AU - Itoh, Keisuke
PY - 1992
Y1 - 1992
N2 - 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. 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/m by PDF/IHS using m 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/m.
AB - 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. 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/m by PDF/IHS using m 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/m.
KW - NP‐hard practical algorithm
KW - Scheduling
KW - branch and bound
KW - multiprocessor super‐linear speedup
KW - parallel search
UR - http://www.scopus.com/inward/record.url?scp=0027003621&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0027003621&partnerID=8YFLogxK
U2 - 10.1002/scj.4690231305
DO - 10.1002/scj.4690231305
M3 - Article
AN - SCOPUS:0027003621
SN - 0882-1666
VL - 23
SP - 54
EP - 65
JO - Systems and Computers in Japan
JF - Systems and Computers in Japan
IS - 13
ER -