The passport control problem or how to keep a dynamic service system load balanced?

Abstract

In many real life situations (such as department stores, or passport control booths in airports) parallel queues are formed in front of control stations. Typically, some of the stations are manned while others are not. Classical queuing theory considers the configuration constant, and concentrates on the arrival process. This work explores a new line of research - the case in which the configuration is dynamic, and the customers can plan to cope with anticipated changes. Specifically, as the queues build up, management assigns additional officers to the unmanned stations. When this happens - some people move to the newly manned queues from nearby busy queues. In anticipation, people may prefer to line up in busy queues next to unmanned ones. Mathematically we discuss the problem of dynamic arrangement of the queues in a service system where at any time each server can be in either an active or an inactive mode. A balancing strategy determines how customers will be reallocated when a station becomes active. Given a balancing strategy, we seek a partition of customers to queues that minimizes the maximum wait time of a customer in each of the active stations, thereby keeping the system balanced at all times. We study two balancing strategies that we call Split and Trim. For the Split strategy we discuss a special case (the stations are ordered on a line and a single unmanned station is at one end). We show how an optimal partition can be calculated recursively. We then give partitions that approximate the minimal expected wait time within a factor of 1+O(1/N), under each of these strategies, where N is the number of stations. We obtain similar bounds (to within factor 2) for the case, where the number of active servers can be any 1 ≤ n ≤ N-1, and the balancing strategy is Trim. © 2002 Elsevier Science B.V. All rights reserved.