Scheduling policies using marked/phantom slot algorithms

Scheduling policies using marked/phantom slot algorithms

0.00 Avg rating0 Votes
Article ID: iaor19971623
Country: United States
Volume: 20
Issue: 1/2
Start Page Number: 207
End Page Number: 254
Publication Date: Sep 1995
Journal: Queueing Systems
Authors: ,
Keywords: perturbation analysis
Abstract:

The authors address the problem of scheduling M customer classes in a single-server system, with customers arriving in one of N arrival streams, as it arises in scheduling transmissions in packet radio networks. In general, NℝM and a customer from some stream may join one of several classes. The authors consider a slotted time model where at each scheduling epoch the server (channel) is assigned to a particular class (transmission set) and can serve multiple customers (packets) simultaneously, one from every arrival stream (network node) that can belong to this class. The assginment is based on a random polling policy: the current time slot is allocated to the ith class with probability θi. The present objective is to determine the optimal probabilities by adjusting them on line so as to optimize some overall performance measure. The authors present an approach based on perturbation analysis techniques, 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. The algorithms determine the effect of removing/adding service slots to an existing schedule on the mean customer waiting times by directly observing the system. The optimal slot assignment probabilities are then used to design a deterministic scheduling policy based on the Golden Ratio policy. Finally, several numerical results based on a simple optimization algorithm are included.

Reviews

Required fields are marked *. Your email address will not be published.