Scheduling in the High-Uncertainty Heavy Traffic Regime

Rami Atar (), Eyal Castiel () and Yonatan Shadmi ()
Additional contact information
Rami Atar: Viterbi Faculty of Electrical and Computer Engineering, Technion, 3200003 Haifa, Israel
Eyal Castiel: Viterbi Faculty of Electrical and Computer Engineering, Technion, 3200003 Haifa, Israel
Yonatan Shadmi: Viterbi Faculty of Electrical and Computer Engineering, Technion, 3200003 Haifa, Israel

Mathematics of Operations Research, 2025, vol. 50, issue 1, 107-140

Abstract: We propose a model uncertainty approach to heavy traffic asymptotics that allows for a high level of uncertainty. That is, the uncertainty classes of underlying distributions accommodate disturbances that are of order 1 at the usual diffusion scale as opposed to asymptotically vanishing disturbances studied previously in relation to heavy traffic. A main advantage of the approach is that the invariance principle underlying diffusion limits makes it possible to define uncertainty classes in terms of the first two moments only. The model we consider is a single-server queue with multiple job types. The problem is formulated as a zero sum stochastic game played between the system controller, who determines scheduling and attempts to minimize an expected linear holding cost, and an adversary, who dynamically controls the service time distributions of arriving jobs and attempts to maximize the cost. The heavy traffic asymptotics of the game are fully solved. It is shown that an asymptotically optimal policy for the system controller is to prioritize according to an index rule, and for the adversary, it is to select distributions based on the system’s current workload. The workload-to-distribution feedback mapping is determined by a Hamilton–Jacobi–Bellman equation, which also characterizes the game’s limit value. Unlike in the vast majority of results in the heavy traffic theory and as a direct consequence of the diffusive size disturbances, the limiting dynamics under asymptotically optimal play are captured by a stochastic differential equation where both the drift and the diffusion coefficients may be discontinuous.

Keywords: Primary: 60K25; 93E20; 91A15; 60F17; 91A05; 68M20; heavy traffic; model uncertainty; high-uncertainty regime; stochastic game; HJB equation; drift-variance trade-off; diffusion with discontinuous coefficients (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.0100 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:50:y:2025:i:1:p:107-140

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().