Scheduling Networks of Queues: Heavy Traffic Analysis of a Two-Station Closed Network

J. Michael Harrison and Lawrence M. Wein
Additional contact information
J. Michael Harrison: Stanford University, Stanford, California
Lawrence M. Wein: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1990, vol. 38, issue 6, 1052-1064

Abstract: We consider a multiclass closed queueing network with two single-server stations. Each class requires service at a particular station, and customers change class after service according to specified probabilities. There is a general service time distribution for each class. The problem is to schedule the two servers to maximize the long-run average throughput of the network. By assuming a large customer population and nearly balanced loading of the two stations, the scheduling problem can be approximated by a dynamic control problem involving Brownian motion. A reformulation of this control problem is solved exactly and the solution is interpreted in terms of the queueing network to obtain a scheduling rule. (We conjecture, quite naturally, that the resulting scheduling rule is asymptotically optimal under heavy traffic conditions, but no attempt is made to prove that.) The scheduling rule is a static priority policy that computes an index for each class and awards higher priority at station 1 (respectively, station 2) to classes with the smaller (respectively, larger) values of this index. An analytical comparison of this rule to any other static policy is also obtained. An example is given that illustrates the procedure and demonstrates its effectiveness.

Keywords: production/scheduling: priority sequencing in a stochastic job shop; queues: Brownian models of network scheduling problems (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (24)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.38.6.1052 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:38:y:1990:i:6:p:1052-1064

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().