Accession Number : AD0783016

Title :   Dynamic Scheduling of a Multi-Class Queue: Discount Optimality.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF DEPT OF OPERATIONS RESEARCH

Personal Author(s) : Harrison,J. Michael

Report Date : MAR 1974

Pagination or Media Count : 33

Abstract : The author considers a single server queueing system with several classes of customers who arrive according to independent Poisson processes. The service time distributions are arbitrary, and a linear cost structure is assumed. The problem is to decide, at the completion of each service and given the state of system, which class (if any) to admit next into service. The objective is to maximize the expected net present value of service rewards received minus holding costs incurred over an infinite planning horizon, the interest rate being positive. One very special type of scheduling rule, called a modified static policy, simply enforces a (non-preemptive) priority ranking except that certain classes are never served. It is shown that there is a modified static policy which is optimal, and a simple algorithm for its computation is presented. (Modified author abstract)

Descriptors :   *Queueing theory, *Scheduling, Dynamic programming, Stochastic processes, Distribution functions, Theorems

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE