An exact method for minimizing the makespan of an application processed ona master slave bus oriented multiprocessor system

The aim of this paper is to present a branch and bound method for minimizin g the makespan of an application processed on a master slave bus oriented m ultiprocessor system. It is supposed that the application can be split into several independent tasks, however, only one task is sent to each processo r. It is assumed that there are one master and several slaves. Some structu ral properties of the optimal schedules are studied in the more general cas e where more than one task can be sent to one processor. An exact method is described and the computational results are reported. (C) 1999 Elsevier Sc ience B.V. All rights reserved.