|
25
- 29 de Noviembre de 2002
Montevideo,
Uruguay
Radisson
Victoria Plaza Hotel
|
|
|
CL43
|
|
BSS Priority Queue
|
Leslie
Murray
Universidad Nacional de Rosario, Facultad de Ciencas Exactas, Ingeniería y Agrimensura
leslie@eie.fceia.unr.edu.ar
|
Gerardo
Rubino
IRISA/INRIA and ENST.B
Gerardo.Rubino@irisa.fr
|
María E.
Urquhart
Universidad de la República, Facultad de Ingeniería, Dpto. de Investigación Operativa, Instituto de Computación
urquhart@fing.edu.uy
|
|
Abstract
|
In Discrete Even Simulation the whole running time is mainly determined by the tupe of data structure intended to manage the pending event set. The Bounded Sequential Searching (BSS) Priority Queue is a pending event set implementation proposal for which empirical evidence of good performance is shown. BSS implementation is stable, its algorithms are easy to program, no resize operation is ever neceessary and there's no sector devoted to the overflow. The construction mechanism and its reulting structure are as simple and clear as to let variations be attempted. Compared to the classical Implicit Hear under the Hold Model, a considerable difference in favor of BSS Priority Queue is experimentally shown. BSS main features are commented, the complexity of its associated algorithms are assessed and some implementation guidelines are given. Finally a list of open problems are current work is remarked.
|
Keywords:
Discrete Event Simulation, Scheduling, Priority Queue, Sequential Searching, Data Structure.
|
|
Volver
|
|
infoUYclei 2002
|
|