Tandem queues with partial job abandonment behave predictably in heavy traffic
Tandem Queues with Hybrid Abandonment in Heavy Traffic
Performance
Summary
Many systems like hospitals, call centers, or computers have jobs or customers that may give up waiting at certain stages but not others. This paper studies what happens when such systems are very busy, focusing on two connected queues where only the first one allows people to leave early. The authors find formulas describing how many jobs queue up in the second stage and show that the queue sizes become independent and follow simple patterns. They also show their math works well in different situations by running computer experiments.
What this means in practice
- •For hospital operations teams: Estimate patient waiting times in multi-stage care when patients may leave early at specific steps using accurate heavy-traffic queue length models.
- •For cloud infrastructure managers: Predict delays in multi-step server request handling where early request abandonment occurs only in initial processing stages.
Authors
Cameron Curtis, Izzy Grosof, Seyed Iravani
Abstract
Hybrid-abandonment systems, where jobs abandon from certain stages of service but not others, occur frequently in medical, service, and computing systems. Abandonment affects the heavy-traffic behavior of both the stages with and without abandonment. In contrast to existing heavy-traffic works that focus on cases where there is abandonment at either all stages or no stages, we focus on the heavy-traffic behavior for these hybrid-abandonment systems. We provide the first heavy-traffic characterization of the second queue length in a two-stage tandem queue with abandonment only in the first stage. We characterize the scaled mean of the second stage queue length and prove that the scaled second queue length is asymptotically exponentially distributed and asymptotically independent of the first stage queue length. We derive our results by analyzing Markovian arrival process queues with countably infinite phases. We do this by extending techniques used to analyze queues with Markov-modulated arrivals to the broader class of infinite Markovian arrival process queues. We prove asymptotic results for a more general infinite phase process condition, an infinite birth-death phase process, and the hybrid-abandonment tandem case. We also empirically demonstrate that our heavy-traffic approximations are good approximations across various system settings.