MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic (Q1431548)

The following discrete-time service system with switching is considered. \(N\) inflows, each having its own queue, are served by a switch whose states are governed by a finite-state Markov chain. If \(m\) is the current switch state, a scheduling decision \(k\) has to be chosen from a finite set \(K(m)\). Then \(\mu_n^m(k)\) customers of flow \(n\), \(n=1,\ldots,N\), are served and depart after one time unit. A MaxWeight scheduling discipline always chooses a decision \(k\) that maximizes \(\sum_n \gamma_n(Q_n)^\beta \mu_n^m(k)\), where \(Q_1,\ldots, Q_N\) are the queue lengths and \(\beta, \gamma_1,\ldots, \gamma_N\) are positive constants. This system is studied under heavy traffic, assuming a so-called resource pooling condition with which there is associated a workload function \(\sum_n \zeta_n Q_n\), where \(\zeta =(\zeta_1,\ldots,\zeta_N)\) is a certain nonzero vector. It is shown that the workload process converges to a reflected Brownian motion, that the vector \((\zeta_1 (Q_1)^\beta,\ldots,\zeta_N (Q_N)^\beta)\) becomes proportional to \(\zeta\) and that MaxWeight asymptotically minimizes the workload under all disciplines. It follows that MaxWeight asymptotically minimizes the holding cost rate \(\sum_n \gamma_n(Q_n)^{\beta +1}\) at all times.