We address the problem of scheduling M customer classes in a single-se
rver system, with customers arriving in one of N arrival streams, as i
t arises in scheduling transmissions in packet radio networks. In gene
ral, N not equal M and a customer from some stream may join one of sev
eral classes. We consider a slotted time model where at each schedulin
g epoch the server (channel) is assigned to a particular class (transm
ission set) and can serve multiple customers (packets) simultaneously,
one from every arrival stream (network node) that can belong to this
class. The assignment is based on a random polling policy: the current
time slot is allocated to the ith class with probability theta(i). Ou
r objective is to determine the optimal probabilities by adjusting the
m on line so as to optimize some overall performance measure. We prese
nt an approach based on perturbation analysis techniques, where all cu
stomer arrival processes can be arbitrary, and no information about th
em is required. The basis of this approach is the development of two s
ensitivity estimators leading to a marked slot and a phantom slot algo
rithm. The algorithms determine the effect of removing/adding service
slots to an existing schedule on the mean customer waiting times by di
rectly observing the system. The optimal slot assignment probabilities
are then used to design a deterministic scheduling policy based on th
e Golden Ratio policy. Finally, several numerical results based on a s
imple optimization algorithm are included.