CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

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

Jan Jonsson (Institutionen för datorteknik) ; Kang G. Shin
Proceedings of the 26th International Conference on Parallel Processing, Bloomingdale, Illinois, August 11–15, 1997 p. 158–165. (1997)
[Konferensbidrag, refereegranskat]

In this paper we experimentally evaluate the performance of a parametrized branch-and-bound (B&B) algorithm for scheduling real-time tasks on a multiprocessor system. The objective of the B&B algorithm is to minimize the maximum task lateness in the system. We show that a last-in-first-out (LIFO) vertex selection rule clearly outperforms the commonly used least-lower-bound (LLB) rule for the scheduling problem. We also present a new adaptive lower-bound cost function that greatly improves the performance of the B&B algorithm when parallelism in the application cannot be fully exploited on the multiprocessor architecture. Finally, we evaluate a set of heuristic strategies, one of which generates near-optimal results with performance guarantees and another of which generates approximate results without performance guarantees.

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2011-04-14. Senast ändrad 2011-04-14.
CPL Pubid: 139045


Institutioner (Chalmers)

Institutionen för datorteknik (1985-2001)


Informations- och kommunikationsteknik

Chalmers infrastruktur