arrival probability: 10 % 20 % 30 % 40 % 50 % 60 % 70 % 80 % 90 % 100 % a simple heuristic: cut at 14 cut at 15 cut at 16 cut at 17 cut at 18 cut at 19 cut at 20 serve always cutting: abs. diff. prop. served: rejected:

 Click on start to begin the simulation. To get additional information to an object, click on stop and hold your mouse over the object. Click on start again to continue. There are 3 queues of car parking spaces (the grey bars in the green area), each 5 long, one behind the other. Cars arrive at random (orange bars, number = desired parking duration) and are added at the back of the queues (car #1 of a queue = blue, car #5 of a queue = red). When position 5 (the back of the queue) is full in all queues, then no more cars can park. Cars leave from the front of queues. Cars do not "shuffle up" but only move when their time comes to depart. So when a queue is full (5 cars), the rearmost car (a red dot) prevents any more vehicles being added until it and the 4 cars in front have all left. Five spaces then become free. The departure time for each car is known at the time of its arrival (corresponding to the numbers of the orange bars), the question is how to allocate the new arrival to a particular queue to optimise the use of parking spaces (to serve as much cars as possible)? Obviously, one constraint is that a car cannot be added to a queue where the one in front has a later departure time. Empirically, it seems, that minimising the difference in departure time between the first and last vehicles in any queue returns those five spaces into re-use most efficiently. But should a new arrival be added to a part filled queue or be made the head of a new queue or should it even be rejected (purple bars) because of a much too late departure time?