Dynamic Routing Problems with Delayed Information

Hyytiä, E., Righter, R. (2021). Dynamic Routing Problems with Delayed Information. In: Zhao, Q., Xia, L. (eds) Performance Evaluation Methodologies and Tools. VALUETOOLS 2021. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 404. Springer, Cham. https://doi.org/10.1007/978-3-030-92511-6_11

Abstract. The problem of routing jobs to parallel servers is known as the dispatching problem. A typical objective is to minimize the mean response time, which according to Little’s result is equivalent to minimizing the mean number in the system. Dynamic dispatching policies are based on information about the state of each server. In large or real-time systems, up-to-date and accurate system state may not be available to dispatcher. We consider, cases where state information at some time in the past is available, or completed jobs are acknowledged after some propagation delay, and give efficient dispatching policies based on the incomplete state information. The dynamic dispatching policies tailored to this setting are evaluated numerically.