The authors consider M transmitting stations sending packets to a single receiver over a slotted time-multiplexed link. For each phase consisting of T consecutive slots, the receiver dynamically allocates these slots among the M transmitters. The present objective is to characteize policies that minimize the long-term average of the total number of messages awaiting service at the M transmitters. The authors establish necessary and sufficient conditions on the arrival processes at the transmitters for the existence of finite cost time-average policies; it is not enough that the average arrival rate is strictly less than the slot capacity. They construct a pure strategy that attains a finite average cost under these conditions. This in turn leads to the existence of an optimal time-average pure policy for each phase length T, and to upper and lower bounds on the cost this policy achieves. Furthermore, the authors show that such an optimal time-average policy has the same properties as those of optimal discounted policies investigated by them in a previous paper. Finally, the authors prove that in the absence of costs accrued by messages within the phase, there exists a policy such that the time-average cost tends toward zero as the phase length T⇒•.
