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

publication date

  • December 2012

start page

  • 3431

end page

  • 3444


  • 39

International Standard Serial Number (ISSN)

  • 0305-0548

Electronic International Standard Serial Number (EISSN)

  • 1873-765X


  • 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.