Interchange Arguments in Stochastic Scheduling

Abstract

Interchange arguments are applied to establish the optimality of priority list policies in three problems. First, we prove that in a multi-class tandem of two '/M/1 queues it is always optimal in the second node to serve according to the "c mu" rule, The result holds more generally if the first node is replaced by a muIti-class network consisting of '/M/1 queues with Bernoulli routing. Next, for scheduling a single server in a multi-class node with feedback, a simplified proof of Klimov's result is given. From it follows the optimality of the index rule among idling policies for general service time distributions, and among pre-emptive policies when the service time distributions are exponential. Lastly, we consider the problem of minimizing the blocking in a communication link with lossy channels and exponential holding times.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 28, 1988
Accession Number
ADA454729

Entities

People

  • Jean Walrand
  • Pantelis Tsoucas
  • Philippe Nain

Organizations

  • University of Maryland

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Availability
  • Classification
  • Contracts
  • Feedback
  • Information Operations
  • Instructions
  • Maryland
  • Monitoring
  • Scheduling (Production)
  • Security
  • Standards
  • Universities

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Mathematical Modeling and Probability Theory.
  • Operations Research