Marked/phantom slot algorithms for a class of scheduling problems

The problem of scheduling M customer classes in a single-server system, with customers arriving in one of N arrival streams is addressed. In general, N ≠ M and a customer from some stream may join one of several classes. The authors consider a slotted time model in which at each scheduling epoch the server is assigned to a particular class and can serve multiple customers simultaneously, one from every arrival stream that can belong to this class. The assignment is based on a random polling policy, i.e., the current time slot is allocated to the ith class with probability θ_i. The objective is to determine the optimal probabilities by adjusting them online so as to optimise some overall performance measure. An approach is presented based on perturbation analysis techniques for discrete event dynamic systems, where all customer arrival processes can be arbitrary, and no information about them is required. The basis of this approach is the development of two sensitivity estimators leading to a marked slot and a phantom slot algorithm. Numerical results based on a simple optimization algorithm are included