Search for: All records

Problem definition: We study scheduling multi-class impatient customers in parallel server queueing systems. At the time of arrival, customers are identified as being one of many classes, and the class represents the service and patience time distributions as well as cost characteristics. From the system’s perspective, customers of the same class at time of arrival get differentiated on their residual patience time as they wait in queue. We leverage this property and propose two novel and easy-to-implement multi-class scheduling policies. Academic/practical relevance: Scheduling multi-class impatient customers is an important and challenging topic, especially when customers’ patience times are nonexponential. In these contexts, even for customers of the same class, processing them under the first-come, first-served (FCFS) policy is suboptimal. This is because, at time of arrival, the system only knows the overall patience distribution from which a customer’s patience value is drawn, and as time elapses, the estimate of the customer’s residual patience time can be further updated. For nonexponential patience distributions, such an update indeed reveals additional information, and using this information to implement within-class prioritization can lead to additional benefits relative to the FCFS policy. Methodology: We use fluid approximations to analyze the multi-class scheduling problem with ideas borrowed from convex optimization. These approximations are known to perform well for large systems, and we use simulations to validate our proposed policies for small systems. Results: We propose a multi-class time-in-queue policy that prioritizes both across customer classes and within each class using a simple rule and further show that most of the gains of such a policy can be achieved by deviating from within-class FCFS for at most one customer class. In addition, for systems with exponential patience times, our policy reduces to a simple priority-based policy, which we prove is asymptotically optimal for Markovian systems with an optimality gap that does not grow with system scale. Managerial implications: Our work provides managers ways of improving quality of service to manage parallel server queueing systems. We propose easy-to-implement policies that perform well relative to reasonable benchmarks. Our work also adds to the academic literature on multi-class queueing systems by demonstrating the joint benefits of cross- and within-class prioritization. Funding: A. Bassamboo received financial support from the National Science Foundation [Grant CMMI 2006350]. C. (A.) Wu received financial support from the Hong Kong General Research Fund [Early Career Scheme, Project 26206419]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2023.1190 . 

As empirically observed in restaurants, call centers, and intensive care units, service times needed by customers are often related to the delay they experience in queue. Two forms of dependence mechanisms in service systems with customer abandonment immediately come to mind: First, the service requirement of a customer may evolve while waiting in queue, in which case the service time of each customer is endogenously determined by the system’s dynamics. Second, customers may arrive (exogenously) to the system with a service and patience time that are stochastically dependent, so that the service-time distribution of the customers that end up in service is different than that of the entire customer population. We refer to the former type of dependence as endogenous and to the latter as exogenous. Because either dependence mechanism can have significant impacts on a system’s performance, it should be identified and taken into consideration for performance-evaluation and decision-making purposes. However, identifying the source of dependence from observed data is hard because both the service times and patience times are censored due to customer abandonment. Further, even if the dependence is known to be exogenous, there remains the difficult problem of fitting a joint service-patience times distribution to the censored data. We address these two problems and provide a solution to the corresponding statistical challenges by proving that both problems can be avoided. We show that, for any exogenous dependence, there exists a corresponding endogenous dependence, such that the queuing dynamics under either dependence have the same law. We also prove that there exist endogenous dependencies for which no equivalent exogenous dependence exists. Therefore, the endogenous dependence can be considered as a generalization of the exogenous dependence. As a result, if dependence is observed in data, one can always consider the system as having an endogenous dependence, regardless of the true underlying dependence mechanism. Because estimating the structure of an endogenous dependence is substantially easier than estimating a joint service-patience distribution from censored data, our approach facilitates statistical estimations considerably. Funding: C. A. Wu received financial support from the Hong Kong Research Grant Council [Early Career Scheme, Project 26206419]. A. Bassamboo and O. Perry received partial financial support from the National Science Foundation [Grant CMMI 2006350].