Dynamic Scheduling of a Multi-Class Queue: Discount Optimality.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1974
- Accession Number
- AD0783016
Entities
People
- J. Michael Harrison
Organizations
- Stanford University