Accession Number : AD0744641

Title :   Dynamic Scheduling of a Multi-Class Queue I: Problem Formulation and Descriptive Results.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF DEPT OF OPERATIONS RESEARCH

Personal Author(s) : Harrison,J. Michael

Report Date : JUN 1972

Pagination or Media Count : 27

Abstract : The author considers an M/G/1 queue with several customer classes. It is not required that the queue be stable or even that the mean service time be finite for any class. The economic framework is linear, featuring a holding cost per unit time and fixed service reward for each class. Future costs and rewards are continuously discounted using a positive interest rate. The problem is to decide, at the completion of each service and given the state of the system, which class to admit next. The objective is to maximize expected net present value over an infinite planning horizon. The problem is formulated as a Markov renewal decision process. One very special type of scheduling rule, called a static policy, simply enforces a specified priority ranking. The return function under a static policy is explicity presented. In a subsequent paper it will be shown that there exists a static optimal policy. (Author)

Descriptors :   (*QUEUEING THEORY, SCHEDULING), STOCHASTIC PROCESSES, DECISION THEORY, THEOREMS, OPTIMIZATION

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE