  We investigate the scheduling of a common resource between several concurrent
users when the feasible transmission rate of each user varies randomly over
time. Time is slotted and users arrive and depart upon service completion. This
may model for example the flow-level behavior of end-users in a narrowband HDR
wireless channel (CDMA 1xEV-DO). As performance criteria we consider the
stability of the system and the mean delay experienced by the users. Given the
complexity of the problem we investigate the fluid-scaled system, which allows
to obtain important results and insights for the original system: (1) We
characterize for a large class of scheduling policies the stability conditions
and identify a set of maximum stable policies, giving in each time slot
preference to users being in their best possible channel condition. We find in
particular that many opportunistic scheduling policies like Score-Based,
Proportionally Best or Potential Improvement are stable under the maximum
stability conditions, whereas the opportunistic scheduler Relative-Best or the
cmu-rule are not. (2) We show that choosing the right tie-breaking rule is
crucial for the performance (e.g. average delay) as perceived by a user. We
prove that a policy is asymptotically optimal if it is maximum stable and the
tie-breaking rule gives priority to the user with the highest departure
probability. We will refer to such tie-breaking rule as myopic. (3) We derive
the growth rates of the number of users in the system in overload settings
under various policies, which give additional insights on the performance. (4)
We conclude that simple priority-index policies with the myopic tie-breaking
rule, are stable and asymptotically optimal. All our findings are validated
with extensive numerical experiments.
