An official website of the United States government
Dispatching systems, where arriving jobs are immediately assigned to one of multiple queues, are ubiquitous in computer systems and service systems. A natural and practically relevant model is one in which each queue serves jobs in FCFS (First-Come First-Served) order. We consider the case where the dispatcher is size-aware, meaning it learns the size (i.e. service time) of each job as it arrives; and state-aware, meaning it always knows the amount of work (i.e. total remaining service time) at each queue. While size- and state-aware dispatching to FCFS queues has been extensively studied, little is known about optimal dispatching for the objective of minimizing mean delay. A major obstacle is that no nontrivial lower bound on mean delay is known, even in heavy traffic (i.e. the limit as load approaches capacity). This makes it difficult to prove that any given policy is optimal, or even heavy-traffic optimal. In this work, we propose the first size- and state-aware dispatching policy that provably minimizes mean delay in heavy traffic. Our policy, called CARD (Controlled Asymmetry Reduces Delay), keeps all but one of the queues short, then routes as few jobs as possible to the one long queue. We prove an upper bound on CARD's mean delay, and we prove the first nontrivial lower bound on the mean delay of any size- and state-aware dispatching policy. Both results apply to any number of servers. Our bounds match in heavy traffic, implying CARD's heavy-traffic optimality. In particular, CARD's heavy-traffic performance improves upon that of LWL (Least Work Left), SITA (Size Interval Task Assignment), and other policies from the literature whose heavy-traffic performance is known.
more »
« less
A Fluid Model of a Traffic Network with Information Feedback and Onramp Controls
Abstract Unlimited access to a motorway network can, in overloaded conditions, cause a loss of throughput. Ramp metering, by controlling access to the motorway at onramps, can help avoid this loss of throughput. The queues that form at onramps are dependent on the metering rates chosen at the onramps, and these choices affect how the capacities of different motorway sections are shared amongst competing flows. In this paper we perform an analytical study of a fluid, or differential equation, model of a linear network topology with onramp queues. The model allows for adaptive arrivals, in the sense that the rate at which external traffic enters the queue at an onramp can depend on the current perceived delay in that queue. The model also includes a ramp metering policy which uses global onramp queue length information to determine the rate at which traffic enters the motorway from each onramp. This ramp metering policy minimizes the maximum delay over all onramps and produces equal delay times over many onramps. The paper characterizes both the dynamics and the equilibrium behavior of the system under this policy. While we consider an idealized model that leaves out many practical details, an aim of the paper is to develop analytical methods that yield interesting qualitative insights and might be adapted to more general contexts. The paper can be considered as a step in developing an analytical approach towards studying more complex network topologies and incorporating other model features.
more »
« less
- PAR ID:
- 10231010
- Date Published:
- Journal Name:
- Applied Mathematics & Optimization
- ISSN:
- 0095-4616
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Optimal cordon-metering rates are obtained using Macroscopic Fundamental Diagrams in combination with flow conservation laws. A model-predictive control algorithm is also used so that time-varying metering rates are generated based on their forecasted impacts. Our scalable algorithm can do this for an arbitrary number of cordoned neighborhoods within a city. Unlike its predecessors, the proposed model accounts for the time-varying constraining effects that cordon queues impose on a neighborhood’s circulating traffic, as those queues expand and recede over time. The model does so at every time step by approximating a neighborhood’s street space occupied by cordon queues, and re-scaling the MFD to describe the state of circulating traffic that results. The model also differentiates between saturated and under-saturated cordon-metering operations. Computer simulations of an idealized network show that these enhancements can substantially improve the predictions of both, the trip completion rates in a neighborhood and the rates that vehicles cross metered cordons. Optimal metering policies generated as a result are similarly shown to do a better job in reducing the Vehicle Hours Traveled on the network. The VHT reductions stemming from the proposed model and from its predecessors differed by as much as 14%.more » « less
-
null (Ed.)Key to the effectiveness of schedule-driven approaches to real-time traffic control is an ability to accurately predict when sensed vehicles will arrive at and pass through the intersection. Prior work in schedule-driven traffic control has assumed a static vehicle arrival model. However, this static predictive model ignores the fact that the queue count and the incurred delay should vary as different partial signal timing schedules (i.e., different possible futures) are explored during the online planning process. In this paper, we propose an alternative arrival time model that incorporates queueing dynamics into this forward search process for a signal timing schedule, to more accurately capture how the intersection’s queues vary over time. As each search state is generated, an incremental queueing delay is dynamically projected for each vehicle. The resulting total queueing delay is then considered in addition to the cumulative delay caused by signal operations. We demonstrate the potential of this approach through microscopic traffic simulation of a real-world road network, showing a 10 − 15% reduction in average wait times over the schedule-driven traffic signal control system in heavy traffic scenarios.more » « less
-
This paper considers networks where user traffic is regulated through deterministic traffic profiles, e.g., token buckets, and requires hard delay bounds. The network's goal is to minimize the resources it needs to meet those bounds. The paper explores how reprofiling, i.e., proactively modifying how user traffic enters the network, can be of benefit. Reprofiling produces "smoother" flows but introduces an up-front access delay that forces tighter network delays. The paper explores this trade-off and demonstrates that, unlike what holds in the single-hop case, reprofiling can be of benefit even when "optimal" schedulers are available at each hop.more » « less
-
The shortest-remaining-processing-time (SRPT) scheduling policy has been extensively studied, for more than 50 years, in single-server queues with infinitely patient jobs. Yet, much less is known about its performance in multiserver queues. In this paper, we present the first theoretical analysis of SRPT in multiserver queues with abandonment. In particular, we consider the M/GI/s+GI queue and demonstrate that, in the many-sever overloaded regime, performance in the SRPT queue is equivalent, asymptotically in steady state, to a preemptive two-class priority queue where customers with short service times (below a threshold) are served without wait, and customers with long service times (above a threshold) eventually abandon without service. We prove that the SRPT discipline maximizes, asymptotically, the system throughput, among all scheduling disciplines. We also compare the performance of the SRPT policy to blind policies and study the effects of the patience-time and service-time distributions. This paper was accepted by Baris Ata, stochastic models & simulation.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/s00245-021-09766-8
