Article ID: | iaor20001497 |
Country: | Netherlands |
Volume: | 94 |
Issue: | 1/3 |
Start Page Number: | 51 |
End Page Number: | 76 |
Publication Date: | May 1999 |
Journal: | Discrete Applied Mathematics |
Authors: | Carlier J., Boufflet J.P. |
Keywords: | programming: branch and bound |
The aim of this paper is to present a branch and bound method for minimizing the makespan of an application processed on a master slave bus oriented multiprocessor system. It is supposed that the application can be split into several independent tasks, however, only one task is sent to each processor. It is assumed that there are one master and several slaves. Some structural properties of the optimal schedules are studied in the more general case where more than one task can be sent to one processor. An exact method is described and the computational results are reported.