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