Optimal scheduling in systems with delay-sensitive traffic

We consider scheduling problems where a resource must provide service to a set of M distinct customer classes. Customers belong to one of N arrival streams, where N≠M in general. In contrast to the authors´ earlier work (1992), we consider delay-sensitive customers who cannot be queued for more than n time slots, where n is fixed. Thus, upon arrival, a customer is either accepted if this constraint can be satisfied, or it is blocked. The objective then is to determine a scheduling policy that minimizes the probability that a customer is blocked. This necessitates the use of a cyclic scheduling policy, such that each class is always visited within n time slots. Thus, the problem becomes one of allocating the slots of an n-slot frame to N classes. This is a generally hard discrete optimization problem. We propose an approach which transforms it into a continuous optimization one. We develop a gradient-based algorithm and derive unbiased gradient estimators required for the online solution of the problem under two different blocking models