Dequeuing events during discrete event simulation

Question

I have a question regarding the dequeue mechanism during discrete event simulation.

Most of the implementations use some kind of priority queue which can be used to quickly retrieve the event with the earliest timestamp. What happens when such an event cannot be scheduled because, say, it needs a resource to be able to run.

There may be another event in the queue whose timestamp is greater than the timestamp of the event that is blocked on a resource.

For example, let us assume we are modelling a grocery-store with separate checkout lines and a cashier per line. A shopper entering a checkout line is an event. We enqueue this event based on the time the shopper entered the checkout line. However, the order in which our simulation should execute two such events in not necessarily the time order in which they entered the checkout line because the cashiers might free up in a different order.

In such a scenario how does using a priority queue solely based on timestamp --- and independent of resource availability --- work out?

Answer 1

You need a queue for each cashier, or at least a count of waiting customers if customer identity is not important in your simulation ( e.g. I would join a queue of three people with one item each over a queue with one person with a full trolley, so just a queue length may not capture the information needed to incorporate that heuristic ).

When a customer joins the queue, the number of queuing customers is incremented or the customer is pushed onto the cashier's queue.

When the cashier is ready to serve, the first customer is popped of the cashier's queue. So the customer service event is dependent not on the time the customer arrives, but when the cashier is ready.

These queues or counters are independent of the scheduling mechanism for events - the events scheduled manipulate these queues, they aren't dependent on them for scheduling.

Answer 2

As Pete Kirkham pointed out, it's important to be aware that the lines (queues) that customers wait in are completely separate things from the priority queue that's used to determine event ordering.

In discrete-event simulation an event is a point in time at which the system state changes. When an event occurs you figure out what to do next based on the state. Joining the line of customers is an event, but so is becoming eligible for service. Once a customer becomes eligible for service, the logic of that event has to check whether service is possible or not. If so, schedule a new event for when the service will end. If there are resource constraints, then nothing gets scheduled and that customer is on hold. However, at some point in the future the required resource will become available. That's an event too, and that event's logic should check to see if there are customers on hold due to lack of the resource. If not, there's no need to schedule anything, but if so, you can now schedule the actual service for the customer. You can see that customer delays in the queue will increase with resource constraints.

For a much fuller explanation of how discrete-event simulations work, please look at this introductory tutorial paper.