We consider a generalized switch model, which
includes as special cases the model of
multiuser data scheduling over a wireless medium,
the input-queued cross-bar switch model and
a discrete time version of a parallel server queueing
system.
Input flows $n=1,\ldots,N$
are served in discrete time by a switch.
The switch state
follows a finite state, discrete time Markov chain.
In each state $m$, the switch chooses
a scheduling decision $k$ from a finite set $K(m)$,
which has the associated service rate vector
$(\mu_1^m(k),\ldots,\mu_N^m(k))$.
¶ We consider a heavy traffic regime,
and assume a
Resource Pooling (RP)
condition. Associated with this condition is a notion of
workload $X=\sum_n \zen Q_n$,
where
$\ze=(\ze_1,\ldots,\ze_N)$ is some fixed
nonzero vector with nonnegative components, and
$Q_1,\ldots,Q_N$ are the queue lengths.
We study the MaxWeight
discipline which always chooses a decision
$k$ maximizing $\sum_n \gamma_n [Q_n]^{\beta} \mu_n^m(k)$, that is,
\[
k \in \mathop{\arg\max}_{i} \sum_n \gamma_n [Q_n]^{\beta} \mu_n^m(i),
\]
where $\beta>0$, $\gamma_1>0,\ldots,\gamma_N>0$ are
arbitrary parameters.
We prove that
under MaxWeight scheduling and the RP condition,
in the heavy traffic limit,
the queue length process has the following properties:
(a) The vector
$(\gamma_1 Q_1^{\beta},\ldots,\gamma_N Q_N^{\beta})$
is always proportional to $\ze$ (this is "State Space Collapse"),
(b) the workload process
converges to a Reflected Brownian Motion,
(c) MaxWeight minimizes the workload
among all disciplines.
As a corollary of these properties,
MaxWeight asymptotically minimizes the holding cost rate
\[
\sum_n \gamma_n Q_{n}^{\beta+1}
\]
at all times, and cumulative cost (with this rate) over
finite intervals.