|
Article Excerpt
1. Introduction
"To queue or not to queue?" as pointed out by (Larson 1987, p. 904), is a question we face every day. When we encounter a queue we often make a quick estimate of the expected waiting time and decide whether to join the queue based on the amount of time we are willing to wait. If we can see the queue, a good way to estimate the waiting time is to count the number of people ahead of us. However, there are effectively "invisible" queues in which we are unable to see all of the waiting people. One example is a ticket queue, where numbered tickets are issued to customers at arrival and the number being served is broadcast on a display panel. In a ticket queue, no physical queue is formed; a customer can only see his own ticket number and the number being served on display. Hence, a quick estimate of the waiting time would have to be based on the difference between the two numbers. Assuming service is performed in increasing order of ticket number, a large difference would imply a long waiting time. In many situations, customers may balk (not join the queue) when they see too large a difference. In this paper, we study performance evaluation and improvement of such ticket queues.
Ticket queues of a primitive type, such as the take-a-number system we frequently encounter in bakery shops, meat counters, and pharmacies, have been used for many years as a means to maintain service order. Advanced ticket-queue technology, developed and commercialized in recent years, is a computerized system for managing the flow of people and related information during the full cycle of customer service. A leading ticket-queue technology provider is Q-MATIC, a Swedish company established in 1981. More than 30,000 installations of its key product, Customer Flow Management, have been sold worldwide. Ticket-queue technology has seen widespread use in financial institutions, government agencies, health care organizations, and retail stores. In the United States, clients of Q-MATIC include the Departments of Motor Vehicles (DMV) in 42 different states, with hundreds of installations. A case study of Q-MATIC implemented in the Nevada DMV is available at http://www.qmatic-us.com. When visiting the DMV, a customer takes a ticket from a self-service counter and then proceeds to a waiting area. The ticket prints out a letter and number combination indicating the service type and service order of the customer. A display panel flashes the ticket number and indicates the counter where customers are served. Similar ticket queues are found in many government offices in Singapore. A good example is the Immigration Department, which processes different types of visa applications for visitors. All of the services are provided at different counters located in the same hall, and each service type has its own numbers. Many commercial service organizations also deploy ticket queue technology to manage their customers' queue flows. For example, in China's big cities, many central bank offices use the technology to manage large crowds of customers that are difficult to keep in order with physical queues.
An interesting feature of almost all of the ticket queues we have observed is that the ticket number is hidden until the ticket is issued to a customer. While such a design initially puzzled us, we came to realize that it has the advantage of recording complete information of customer arrivals, including any balking customers.
Larson (1987) and Katz et al. (1991) argue that customers' attitudes toward queueing can be strongly influenced by many attributes other than the waiting time, such as the waiting environment and social justice. Katz et al. (1991) demonstrate, via several case studies, that a change in the queueing environment, such as installing a news board or a TV set in the waiting area, makes the waiting experience a positive one and tends to increase customer satisfaction. They also show that customers may become infuriated if they experience social injustice, especially when the first-in, first-out (FIFO) service rule is violated. In both regards, the ticket-queue arrangement provides a better waiting experience to customers. Compared to the physical queueing arrangement, the ticket queue liberates people from physical discomfort and mental boredom of standing in crowded queues, and gives them freedom to make more productive use of the waiting time. It makes the premises more tidy and relaxing, especially when several different queues are formed at the same location. A ticket queue also protects customers' privacy and security and reduces their anxiety level, which is an acute concern in service systems such as banks and hospitals. Finally, because the ticket number represents a customer's logical position in line, the ticket queue prevents cutting to the front of the line and thereby promotes customer equity.
Ticket queues can also add value to business. They create a more relaxed atmosphere for agents and allow them to serve clients more effectively. Ticket queues collect complete information on the demand pattern, abandonment behavior, and agents' performance, thus enabling real-time decisions on customer routing and staff allocation. This information can be combined with Customer Relationship Management (CRM) to generate more sales; for example, some pharmacies use a voice-video system to announce the number through the service area so that customers may shop while waiting for their numbers to be called.
Despite the numerous apparent advantages of a ticket queue over a traditional physical queue, it has a drawback that can significantly impede its service performance. In the ticket-queue system, information on physical queuing is lost, i.e., only the difference between the customer's ticket number and the number served is observed, but not the actual number of customers ahead of him. We call the number difference the ticket position to differentiate it from the queueing position. In some ticket-queue applications, customers are naive and impatient (as most of us are) and perceive the ticket position as the actual queueing position, ignoring the possibility that some customers before them may have already abandoned the queue. This may lead them to overestimate their waiting time based on the ticket position and abandon the queue if it is larger than their waiting tolerance limit. Even when some more sophisticated customers recognize that the ticket position is upwardly biased compared to the queueing position due to abandonment, it may be difficult for them to obtain a quick estimate of the queueing position. Consequently, the ticket queue can lead to a much higher customer balking rate compared to the physical queue, leading to poor service from the customer's perspective. It can also result in underutilization of service capacity, which represents a loss of productivity from the business perspective.
We observe that the analysis of a ticket queue in which patient customers do not balk at arrival nor renege while waiting would be identical to that of a physical queue. This situation may occur when only one type of service is provided and joining customers gather around the waiting area thereby making the queue visible. In this paper, we are concerned with ticket queues in which the physical queue is effectively invisible and a customer's queueing position can only be inferred from his ticket position. Specifically, we are interested in the following issues: (1) how to accurately predict the performance of a ticket queue in the presence of partial information (i.e., balking rate and expected delay time); (2) the consequences if both customers and management perceive the ticket queue to be the physical queue, as many apparently do; (3) the conditions under which a customer's biased estimate of his anticipated delay should be a concern to management; and (4) how much the balking rate can be improved by offering customers more accurate information on their anticipated delay.
To facilitate our analysis, we consider a simple, single-server ticket queue in which the customers arrive according to a Poisson process and their service times are independently and identically distributed (i.i.d.) exponential random variables. We assume for simplicity's sake that a customer will balk if his ticket position were greater than or equal to a threshold K, but that he will not renege while waiting. This threshold type of balking has been shown to be individually optimal for some queueing situations. For example, Naor (1969) proves that, in an M/M/1 queue, if arriving customers want to maximize an expected net gain, they should follow a threshold type of joining rule. Whitt (1999) contends that an arriving customer who observes the state of the system should be able to decide immediately whether to abandon the queue; once the customer has joined, she should be much more likely to remain until she is served.
We first formulate a Markov chain model for the ticket queue, which is too complex to yield a closed-form solution of the steady-state distribution, except for small K-values. Therefore, we develop a solution procedure consisting of two steps. In the first step, we aggregate the states of the Markov chain and reduce the infinite state space to a finite one. The resulting Markov chain has the structure of a quasi-birth-and-death (QBD) process that admits a matrix product form solution of the steady-state distribution. In the second step, we disaggregate the aggregated states into individual states and obtain their steady-state probabilities. After obtaining the steady-state distribution, we are able to evaluate key performance measures of the ticket queue: in particular, the customer's balking probability and his expected waiting time for a given ticket position.
Unfortunately, this solution procedure requires exponentially increasing time and memory space as the value of K increases. Specifically, the cardinality of the state space is O(K[2.sup.K-1]) after state aggregation. Therefore, we are forced to develop a heuristic solution to facilitate efficient computation of the ticket queue for large K values. This heuristic is based on our observation through extensive simulations that, most often, balking customers appear in a consecutive sequence at the end of the queue and are cleared in one instant. In other words, the intermixing of joining and balking customers rarely occurs. Thus, instead of analyzing the ticket queue as it is, we analyze a queue in which all balking customers can be identified and moved to the end of the queue, or, equivalently, all joining customers are implicitly given higher priority of service. This queue has a much-reduced cardinality of the state space at O([K.sup.2]), which represents, for example, a state reduction by a factor of 29,000 when K = 20, as compared to the original ticket queue. We develop a polynomial time algorithm to compute the steady-state distribution, which is then compared to the exact solution when possible and to the simulation results otherwise. This verifies our approximation to be efficient, accurate, and robust. We also discover through numerical computations and simulations that, when the customer's ticket position increases linearly in balking limit K, his queueing position also increases almost linearly in K. We are unable to obtain the exact relationship between the two quantities as K increases, but it has the potential to greatly simplify the implementation of our proposed improvement to the ticket queue.
We then investigate the qualitative and quantitative relationships between the ticket and physical queues that have the same balking limit, assuming customers are naive and take the ticket position to be the actual queueing position. In effect, we compare the ticket queue to an M/M/1/K queue. This comparison is aimed at addressing the following question: What is the consequence if both management and customers treat the ticket queue as the physical queue? Perceiving the two systems as the same implies that management will use the physical queue performance to estimate the ticket-queue performance, and customers will treat the ticket position as the queueing position. Although our comparison is based on the simplifying assumption that all customers use the naive balking rule, it makes it possible to compare the two systems qualitatively and numerically, which is valuable in obtaining important managerial insights.
We show that, compared with the physical queue, the ticket queue has a stochastically smaller number of joining customers and a higher balking probability. This result implies that, even though the ticket queue is actually less crowded (in the stochastic sense) than the physical queue by head count, it appears busier than the latter by ticket...
|
