Admission and routing of soft real-time jobs to multiclusters: Design and comparison of index policies

Motivated by time-sensitive e-service applications, we consider the design of effective policies in a Markovian model for the dynamic control of both admission and routing of a single class of real-time transactions to multiple heterogeneous clusters of web servers, each having its own queue and server pool. Transactions come with response-time deadlines, staying until completion if the latter are missed. Per job rejection and deadline-miss penalties are incurred. Since computing an optimal policy is intractable, we aim to design near optimal heuristic policies that are tractable for large-scale systems. Four policies are developed: the static optimal Bernoulli-splitting (BS) policy, and three index policies, based respectively on individually optimal (IO) actions, one-step policy improvement (PI), and restless bandit (RB) indexation. A computational study demonstrates that PI is the best of such policies, being consistently near optimal. In the pure-routing case, both the PI and RB policies are nearly optimal.