Multiclass Queue Scheduling Under Slowdown: An Approximate Dynamic Programming Approach
Jing Dong, Berk Görgülü, Vahid Sarhangian · 2025
Read Multiclass Queue Scheduling Under Slowdown: An Approximate Dynamic Programming Approach by Jing Dong, Berk Görgülü, Vahid Sarhangian (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-10523.txt.
Introduction
Jing Dong, Berk Görgülü, and Vahid Sarhangian wrote this research paper, published in 2025. It tackles scheduling in service queues where waiting itself makes service slower, a pattern seen in health care when patients who wait longer need more care.
The paper studies systems with several customer classes and several servers, where each class suffers differently from waiting. Finding the best order to serve people is hard. The authors build a simulation-based method that learns near-best policies. It shapes the policy with classifiers, compares outcomes by a pairing trick, and samples the states that matter most. In tests, the learned policies beat standard benchmarks. A case study on scheduling rehab admissions shows the approach in action, and the results expose a trade-off between quick wins now and avoiding costly pile-ups later.
Catalog record
| CREATOR | Jing Dong, Berk Görgülü, Vahid Sarhangian |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 121 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-10523
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multiclass Queue Scheduling Under Slowdown: An Approximate Dynamic Programming Approach Jing Dong, Berk Görgülü, Vahid Sarhangian Abstract In many service systems, especially those in healthcare, customer waiting times can result in increased service requirements. Such service slowdowns can significantly impact system performance. Therefore, it is important to properly account for their impact when designing scheduling policies. Scheduling under wait-dependent service times is challenging, especially when multiple customer classes are heterogeneously affected by waiting. In this work, we study scheduling policies in multiclass, multiserver queues with wait-dependent service slowdowns. We propose a simulation-based Approximate Dynamic Programming (ADP) algorithm to find close-to-optimal scheduling policies. The ADP algorithm (i) represents the policy using classifiers based on the index policy structure, (ii) leverages a coupling method to estimate the differences of the relative value functions directly, and (iii) uses adaptive sampling for efficient state-space exploration. Through extensive numerical experiments, we illustrate that the ADP algorithm generates close-to-optimal policies that outperform well-known benchmarks. We also provide insights into the structure of the optimal policy, which reveals an important trade-off between instantaneous cost reduction and preventing the system from reaching high-cost equilibria. Lastly, we conduct a case study on scheduling admissions into rehabilitation care to illustrate the effectiveness of the ADP algorithm in practice. keywords multiclass queue, service slowdown, approximate dynamic programming, variance reduction † † runningtitle: Multiclass Queue Scheduling Under Slowdown † † authors: Decision, Risk, and Operations, Columbia Business School, [email protected] DeGroote School of Business, McMaster University, [email protected] Department of Mechanical and Industrial Engineering, University of Toronto, [email protected] † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: 1 Introduction In the queueing literature, customers’ service requirements are typically assumed to be independent of their waiting times. However, in many service systems, service times can be longer when the system is experiencing higher congestion. Such service slowdowns are particularly common in healthcare settings. For example, Huang et al. (2010) identify an association between long delays in admission to the emergency department (ED) and prolonged inpatient length-of-stay (LOS). Chan et al. (2017) find that longer waiting times in admission to the Intensive Care Unit (ICU) can lead to longer ICU LOS. Görgülü et al. (2023) find that delays in transitioning from acute to rehabilitation care can result in longer rehabilitation LOS. These empirical studies also find that delays can have heterogeneous impacts on different types of patients. Service slowdowns due to delays can significantly impact system performance and result in extended periods of high congestion and poor quality of service. Therefore, it is important to properly account for their impact when determining staffing and scheduling policies. Scheduling under wait-dependent service times is challenging, especially when there are multiple customer classes ( Shi et al. 2024 ) . Existing works mainly focus on performance analysis of single-class queues ( Dong et al. 2015 , Wu et al. 2019 , D’Auria et al. 2022 ), or scheduling in clearing systems (with no future arrivals) ( Shi et al. 2024 , Alidaee and Womer 1999 ) . Moreover, simple scheduling policies such as the c\mu -rule ( Van Mieghem 1995 ) , which perform well in the absence of slowdown, could perform very poorly when delays lead to increased service requirements. In this paper, we propose a simulation-based Approximate Dynamic Programming (ADP) algorithm to find well-performing scheduling policies for multiclass multiserver queues with wait-dependent service slowdown. We start by considering a class of Markovian systems with preemption where the service rate is a function of the number of customers in the system. Our algorithmic development leverages specific structural properties of the problem through three main components: (i) a classifier to characterize the index policy structure; (ii) a coupling construction to estimate the value function differences directly; and (iii) an adaptive sampling algorithm for efficient state-space exploration. We conduct extensive numerical experiments and illustrate that our proposed algorithm finds near-optimal policies, outperforms other benchmarks, and scales well for large problem instances. We further propose a heuristic to connect systems with wait-dependent service times to the proposed Markovian system with state-dependent service rates. This allows us to extend the policy derived from the Markovian system to systems with wait-dependent service times. In addition, we propose an extension of our ADP algorithm to systems where preemption is not allowed. We illustrate the effectiveness of these extensions in a case study on scheduling admissions to rehabilitation care. The case study is based on the empirical finding that admission delays have heterogeneous adverse effects on rehabilitation length-of-stay (service times) and other outcomes for different categories of patients. Our main contributions can be summarized as follows. 1. We investigate scheduling policies for multiclass queues with class-dependent service slowdown. A notable phenomenon that can arise in systems experiencing service slowdown is meta-stability. We characterize the equilibrium points of the fluid model of the Markovian system with state-dependent service slowdown and show that it could have multiple stable equilibria, including some associated with long queues. Our results demonstrate that scheduling in systems prone to meta-stability requires carefully balancing the tradeoffs between the instantaneous cost reduction rate and avoiding entrapment in “bad” equilibria. 2. We proposed a simulation-based ADP algorithm to solve the scheduling problem. The algorithm incorporates several innovative methods to reduce computational time. These methods are more broadly applicable to other complex queueing control problem. Notably, by exploiting the specific structure of the problem, we propose a coupling method that directly estimates the value function differences, which bypasses some of the challenges in relative value function estimation. Compared to existing methods, the proposed coupling results in a significant reduction in simulation lengths as well as the variance of the estimates (up to 93%) which collectively reduce computational cost. 3. We provide insights into the structure of the optimal policy for scheduling queues with class-dependent service slowdowns. In contrast to simple queuing systems, where the optimal policy focuses on myopically maximizing the instantaneous rate of reducing the holding cost, in the presence of slowdown, the optimal policy aims to also prevent the system from being stuck at the high-cost equilibria, hence balancing two objectives. Therefore, the optimal policy is affected by the change in system load generated by the increased slowdown or changes in the arrival rates. 4. We conduct a case study on scheduling admissions to rehabilitation care using real data. In this setting, rehabilitation length-of-stays are affected heterogeneously by admission delays for Neuro/MSK and Medicine patients. We find that the ADP policy provides a 2.5 days reduction in average waiting times compared to historical averages. This respectively translates to, on average, 2.17 and 4.93 increase in discharge Functional Independence Measure (FIM) (a standard metric for measuring rehabilitation outcomes taking values between 18 and 126) for Neuro/MSK and Medicine patients, respectively. Furthermore, compared to a naive first-come-first-served (FCFS) policy, using the ADP policy results in 10.76 days reduction in average waiting times and respectively 25.40 and 16.74 point increases in the discharge FIM scores for Neuro/MSK and Medicine patients. The rest of the paper is organized as follows. Section 2 discusses the related literature. Section 3 describes the main model and its connection to the wait-time dependent model. Section 4 presents our simulation-based ADP algorithm, and Section