DocumentCode :
2407607
Title :
Marked/phantom slot algorithms for a class of scheduling problems
Author :
Cassandras, Christos G. ; Julka, Vibhor
Author_Institution :
Dept. of Electr. & Comput. Eng., Massachusetts Univ., Amherst, MA, USA
fYear :
1992
fDate :
1992
Firstpage :
3215
Abstract :
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, NM 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
Keywords :
probability; queueing theory; random processes; scheduling; customer arrival processes; discrete event dynamic systems; marked slot algorithm; optimal probabilities; optimization algorithm; perturbation analysis techniques; phantom slot algorithm; probability; random polling policy; scheduling problems; single-server system; slotted time model; Imaging phantoms; Information analysis; Interference constraints; Laboratories; Network servers; Packet radio networks; Processor scheduling; Radio broadcasting; Scheduling algorithm; Switches;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Decision and Control, 1992., Proceedings of the 31st IEEE Conference on
Conference_Location :
Tucson, AZ
Print_ISBN :
0-7803-0872-7
Type :
conf
DOI :
10.1109/CDC.1992.371235
Filename :
371235
Link To Document :
بازگشت