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 μ. We demonstrate that for the infinite bucket calendar queue the optimal bucket width is approximately δ_opt=√(2b/c)μ/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 δ_opt, the expected time to process an event is approximately minimized at the constant c+√(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