Multiprocessor scheduling algorithm with communication time

This paper proposes an algorithm for multiprocessor scheduling which is needed to realize efficient parallel processing. In the traditional multiprocessor scheduling algorithms the time required for data communication was neglected to decrease the complexity of combinatorial computation. In this paper, using a scheduling algorithm which incorporates elements of communication time into a suboptimal algorithm, divided tasks are assigned onto a multiprocessor system. The characteristics of this algorithm are two-fold: first, since the time required for data communication between processors as a parameter is taken into consideration, scheduling conforming to practical systems is possible; second, since it is based on a suboptimal algorithm, it shortens the time required for scheduling. Furthermore, as examples of applications of this algorithm, it is described how it is applied to inverse kinematics and inverse dynamics problems.