A Parametrized Branch-and-Bound Strategy for Scheduling Precedence-Constrained Tasks on a Multiprocessor System

In this paper we experimentally evaluate the performance of aparametrized branch-and-bound (B&B) algorithm for schedulingreal-time tasks on a multiprocessor system. The objective of the B&Balgorithm is to minimize the maximum task lateness in the system. Weshow that a last-in-first-out (LIFO) vertex selection rule clearlyoutperforms the commonly used least-lower-bound (LLB) rule for thescheduling problem. We also present a new adaptive lower-bound costfunction that greatly improves the performance of the B&B algorithmwhen parallelism in the application cannot be fully exploited on themultiprocessor architecture. Finally, we evaluate a set of heuristicstrategies, one of which generates near-optimal results withperformance guarantees and another of which generates approximateresults without performance guarantees