Efficient Multiprocessor Scheduling Based on Bidirectional Complement Hypothesis and Building Block Hypothesis
Takaya ARITA, Hiromitsu TAKAGI and Masahiro SOWA
Joint Symposium on Parallel Processing 1993 (JSPP '93), pp. 283-290, 1993
abstract
The problem of multiprocessor scheduling is stated as finding a schedule for a general task graph to be executed on multiprocessor systems so that the schedule length can be minimized. This problem is known to be NP-complete and methods based on heuristic search have been proposed. This paper proposes a scheduling method which attains an efficient parallel search based on the building block hypothesis in a framework of genetic algorithms. Good solutions can be expected even in the first population because generation of the first population is based on the bidirectional complement hypothesis in this method. This paper also shows that a better schedule for the problem of the robot inverse dynamics computations can be generated by this method than one by a branch and bound type scheduler.
