Optimizing Static Calendar Queues

The calendar queue is an important implementation of a priority queue which is particularly useful in discrete event simulators. In this paper we present an analysis of the static calendar queue which maintains N active events. A step of the discrete event simulator removes and processes the event with the smallest associated time and inserts a new event whose associated time is the time of the removed event plus a random increment with mean /spl mu/. We demonstrate that for the infinite bucket calendar queue the optimal bucket width is approximately /spl delta//sub opt/=/spl radic/(2b/c)/spl mu//N where b is the time to process an empty bucket and c the incremental time to process a list element. With bucket width chosen to be /spl delta//sub opt/, the expected time to process an event is approximately minimized at the constant c+/spl radic/(2bc)+d, where d is the fixed time to process an event. We show that choosing the number of buckets to be O(N) yields a calendar queue with performance equal to or almost equal to the performance of the infinite bucket calendar queue. >

Authors

• K. Bruce Erickson
• Richard E. Ladner
• Anthony LaMarca

Keywords

• Calendars
• Discrete event simulation
• Computational modeling
• Data structures
• Computer science
• Queueing analysis
• Mathematics
• Random variables
• Concurrent computing
• Department Of Computer Science
• Optimal Width
• Priority Queue
• Infinity
• Markov Chain
• Probability Density
• State Space
• Proof Of Theorem
• Independent Random Variables
• Probability 1
• Finite Support
• Invariant Distribution