Title :
Utility Optimal Scheduling for General Reward States and Stability Constraint
Author :
Chaporkar, Prasanna ; Sarkar, Saswati
Author_Institution :
Department of Electrical and Systems Engineering, University of Pennsylvania. prasanna@seas.upenn.edu
Abstract :
We consider a queueing system with n parallel queues, which receives a reward for the service it provides. Our aim is to maximize the expected reward obtained per unit time (utility) while ensuring that the mean queue length in each of the queues is bounded (stability). We show that the optimal policy has counter intuitive properties because of the general reward states and stability constraint. For example, the greedy policy of serving a customer that fetches maximum reward need not be optimal. In addition, the optimal policy may belong to a class of non work-conserving policies. We obtain two different policies that attain the above optimality goal. The first policy arbitrates service randomly based on the current reward states and probabilities that depend on system statistics. The second policy arbitrates service deterministically based only on the queue lengths and the current reward states, and does not require any knowledge of the system statistics. The proposed policies are optimal in a large class of policies that includes off-line policies, which use knowledge of past, present and even future arrival and reward states in their decision processes.
Keywords :
Queueing theory; randomized algorithms; stability; utility maximization; Buffer overflow; Counting circuits; Delay; Optimal scheduling; Probability; Queueing analysis; Stability; Statistics; Systems engineering and theory; Queueing theory; randomized algorithms; stability; utility maximization;
Conference_Titel :
Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC '05. 44th IEEE Conference on
Print_ISBN :
0-7803-9567-0
DOI :
10.1109/CDC.2005.1582976