مقاله انگلیسی سیاست مسیریابی پویا برای به حداقل رساندن زمان انتظار
Abstract
Keywords
Introduction
Literature review
Problem
Optimal static policy
Dynamic routing policies
Experiments
Fire stations case
Conclusions
CRediT authorship contribution statement
Appendix A. Proof of Proposition 1 : Binding coverage constraint
Appendix B. Proof of Proposition 2: Convexity
Appendix C. Illustrations of key routing policies
Appendix D. XRand map and the corresponding static routing map
Online Supplementary Appendix. Supplementary data
References
Abstract
Minimizing queue waiting time in multi-class multi-server systems, where the service time depends both on the job type and the server type, has wide applications in transportation systems such as emergency networks and taxi networks, service systems such as call centers, and distributed computing platforms. However, the optimal dynamic policy for this problem is not known and remains a hard open problem. In our approach, we develop a math program to model a static variant of this routing problem and use the solution from this math program to construct several novel dynamic policies. In three categories, namely, (i) policies that do not block jobs, (ii) policies that block jobs statically (i.e., blocking jobs using a predetermined blocking probability), and (ii) policies that block jobs dynamically (i.e., blocking jobs when all feasible servers are busy), we compare the performance of our policies with Fastest-Server-First (FSF), a well-known routing policy for such problems in practice and in the literature. Our experiments show that our proposed overflow dynamic routing policies outperform FSF and its extensions, FSFStaticBlock and FSFDynamicBlock. Moreover, to showcase our methodology, we apply our proposed policies to the problem of assigning fire incidents in Irvine, CA, to fire stations.
Introduction
We study the problem of minimizing expected waiting time in a multi-class multi-server queueing system, where service times are both job-type and server-type dependent. For this queueing system the service time that a job experiences depends on the routing decision, i.e., the server to which the job is routed. This endogeneity of service time, i.e., the dependency of the service time on the routing decision, complicates the routing problem. In fact, the optimal dynamic policy for this queueing system is unknown (Mehrotra et al., 2012). Nevertheless, simple greedy dynamic policies can perform reasonably well in such settings, and provide a meaningful practical benchmark. In our context, a simple greedy dynamic policy which is commonly implemented in practice is the Fastest-Server-First (FSF) policy, which always routes each arriving job to an available (i.e., not busy) server that is the fastest at handling this job type. While the FSF policy is known to be near-optimal for the single job-type special case (i.e., it is provably optimal in the Halfin–Whitt regime), we will demonstrate that its performance is suboptimal when there are multiple job types.