Scheduling Networks of Queues: Heavy Traffic Analysis of a Multistation Network with Controllable Inputs

Lawrence M. Wein
Additional contact information
Lawrence M. Wein: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1992, vol. 40, issue 3-supplement-2, S312-S334

Abstract: Motivated by a factory scheduling problem, we consider the problem of input control (subject to a specified input mix) and priority sequencing in a multistation, multiclass queueing network with general service time distributions and a general routing structure. The objective is to minimize the long-run expected average number of customers in the system subject to a constraint on the long-run expected average output rate. Under balanced heavy loading conditions, this scheduling problem can be approximated by a control problem involving Brownian motion. Linear programming is used to reduce the workload formulation of this control problem to a constrained singular control problem for a multidimensional Brownian motion. The finite difference approximation method is then used to find a linear programming solution to the latter problem. The solution is interpreted in terms of the original queueing system to obtain an effective scheduling policy. The priority sequencing policy is based on dynamic reduced costs from a linear program, and the workload regulating input policy releases a customer into the system whenever the workload process enters a particular region. An example is provided 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: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.3.S312 (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:40:y:1992:i:3-supplement-2:p:s312-s334

Access Statistics for this article

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