New Benchmarks for Static Task Scheduling on Homogeneous Multiprocessor Systems with Communication Delays
Tatjana Davidovi, Kneza Mihaila · 2003
Scheduling tasks on multiprocessor systems is a very active research area with numerous papers addressing the many different variants of the problem. Yet, there appears to be a lack of adequate benchmark problem instances. In this paper, we propose a large set of benchmark graphs for the Multiprocessor Scheduling Problem with Communication Delays. The proposed benchmark problems have known optimal solutions and cover a broad spectrum of characteristics: multiprocessor architecture, number of processors, number of tasks, density of inter-task communications links. We use these benchmark problem instances to analyze the performance of several constructive heuristics and may thus emphasize the dependency of constructive heuristic solutions on different problem parameters related to both task graph characteristics and multiprocessor architecture.