Runhan Xie
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Runhan Xie has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Isaac Grosof
Northwestern University, Evanston, Illinois, USA
3 shared publications - Ziv Scully
School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
3 shared publications - Elene Anton
LIUPPA, University of Pau and the Pays de l’Adour (UPPA), Anglet, France
1 shared publication - Kristen Gardner
Department of Computer Science, Amherst College, Amherst, USA
1 shared publication - Rhonda Righter
Department of Industrial Engineering and Operations Research, University of California, Berkeley, USA
1 shared publication
Latest Publications
- Open Access
- 2 June 2025
- Published by Springer Nature in Queueing Systems
- Vol. 109 (2) , 1-20
Insensitivity for Matching Systems
We study matching queues motivated by applications in ride-sharing platforms, where items (e.g., drivers and riders) arrive over time and are matched based on a compatibility graph. Our model generalizes classical compatibility queueing models and queue-based ride-sharing models by allowing exogenous driver arrivals, queues for both drivers and riders, and arbitrary bipartite compatibility structures. We provide sufficient conditions under which the stationary distribution exhibits insensitivity to 1) service-time (drive-time) distributions and 2) the matching policies of drivers and riders, respectively. Using tools from Kelly networks and order-independent queues, we provide simple and unified proofs of insensitivity to service-time distributions and to matching policies for a broad class of models. Our policy insensitivity result requires a finite buffer; we demonstrate through counterexamples that such insensitivity may fail when the buffer is infinite. Our results also shed light on insensitivity in related redundancy systems, offering new insights into their stationary behavior.
- 2 June 2025
- Published by Springer Nature in Queueing Systems
- Vol. 109 (2) , 1-20
Open AccessInsensitivity for Matching Systems
We study matching queues motivated by applications in ride-sharing platforms, where items (e.g., drivers and riders) arrive over time and are matched based on a compatibility graph. Our model generalizes classical compatibility queueing models and queue-based ride-sharing models by allowing exogenous driver arrivals, queues for both drivers and riders, and arbitrary bipartite compatibility structures. We provide sufficient conditions under which the stationary distribution exhibits insensitivity to 1) service-time (drive-time) distributions and 2) the matching policies of drivers and riders, respectively. Using tools from Kelly networks and order-independent queues, we provide simple and unified proofs of insensitivity to service-time distributions and to matching policies for a broad class of models. Our policy insensitivity result requires a finite buffer; we demonstrate through counterexamples that such insensitivity may fail when the buffer is infinite. Our results also shed light on insensitivity in related redundancy systems, offering new insights into their stationary behavior.
- Open Access
- 11 June 2024
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 52 (1) , 7-8
Heavy-Traffic Optimal Size- and State-Aware Dispatching
We study the problem of dispatching jobs to multiple FCFS (First-Come, First-Served) queues. 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. In this work, we propose the first size- and state-aware dispatching policy, called CARD (Controlled Asymmetry Reduces Delay), that provably minimizes mean delay in heavy traffic. This work summarizes our full paper.
- 11 June 2024
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 52 (1) , 7-8
Open AccessHeavy-Traffic Optimal Size- and State-Aware Dispatching
We study the problem of dispatching jobs to multiple FCFS (First-Come, First-Served) queues. 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. In this work, we propose the first size- and state-aware dispatching policy, called CARD (Controlled Asymmetry Reduces Delay), that provably minimizes mean delay in heavy traffic. This work summarizes our full paper.
- Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 7-8
Heavy-Traffic Optimal Size- and State-Aware Dispatching
We study the problem of dispatching jobs to multiple FCFS (First-Come, First-Served) queues. 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. In this work, we propose the first size- and state-aware dispatching policy, called CARD (Controlled Asymmetry Reduces Delay), that provably minimizes mean delay in heavy traffic. This work summarizes our full paper.
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 7-8
Open AccessHeavy-Traffic Optimal Size- and State-Aware Dispatching
We study the problem of dispatching jobs to multiple FCFS (First-Come, First-Served) queues. 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. In this work, we propose the first size- and state-aware dispatching policy, called CARD (Controlled Asymmetry Reduces Delay), that provably minimizes mean delay in heavy traffic. This work summarizes our full paper.
- Open Access
- 16 February 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Measurement and Analysis of Computing Systems
- Vol. 8 (1) , 1-36
Heavy-Traffic Optimal Size- and State-Aware Dispatching
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.
- 16 February 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Measurement and Analysis of Computing Systems
- Vol. 8 (1) , 1-36
Open AccessHeavy-Traffic Optimal Size- and State-Aware Dispatching
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.