IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v38y1990i6p1052-1064.html
   My bibliography  Save this article

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

Author

Listed:
  • J. Michael Harrison

    (Stanford University, Stanford, California)

  • Lawrence M. Wein

    (Massachusetts Institute of Technology, Cambridge, Massachusetts)

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.

Suggested Citation

  • J. Michael Harrison & Lawrence M. Wein, 1990. "Scheduling Networks of Queues: Heavy Traffic Analysis of a Two-Station Closed Network," Operations Research, INFORMS, vol. 38(6), pages 1052-1064, December.
    • Handle: RePEc:inm:oropre:v:38:y:1990:i:6:p:1052-1064
    DOI: 10.1287/opre.38.6.1052
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.38.6.1052
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.38.6.1052?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Gregory Dobson & Tolga Tezcan & Vera Tilson, 2013. "Optimal Workflow Decisions for Investigators in Systems with Interruptions," Management Science, INFORMS, vol. 59(5), pages 1125-1141, May.
    2. Paul Glasserman & Yashan Wang, 1999. "Fill-Rate Bottlenecks in Production-Inventory Networks," Manufacturing & Service Operations Management, INFORMS, vol. 1(1), pages 62-76.
    3. Bertsimas, Dimitris & Paschalidis, Ioannis Ch. & Tsitsiklis, John N., 1992. "Optimization of multiclass queuing networks : polyhedral and nonlinear characterizations of achievable performance," Working papers 3509-92., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    4. C. Roger Glassey & Sridhar Seshadri & J. Shanthikumar, 1997. "Using information about machine failures to control flowlines," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 45(3), pages 455-481, October.
    5. Santiago R. Balseiro & David B. Brown & Chen Chen, 2021. "Dynamic Pricing of Relocating Resources in Large Networks," Management Science, INFORMS, vol. 67(7), pages 4075-4094, July.
    6. Lee, Heeseok, 1995. "Assignment of a job load in a distributed system: A multicriteria design method," European Journal of Operational Research, Elsevier, vol. 87(2), pages 274-283, December.
    7. van Ackere, Ann, 1996. "The management of congestion," European Journal of Operational Research, Elsevier, vol. 89(2), pages 223-225, March.
    8. Martin I. Reiman & Lawrence M. Wein, 1998. "Dynamic Scheduling of a Two-Class Queue with Setups," Operations Research, INFORMS, vol. 46(4), pages 532-547, August.
    9. Melanie Rubino & Barış Ata, 2009. "Dynamic Control of a Make-to-Order, Parallel-Server System with Cancellations," Operations Research, INFORMS, vol. 57(1), pages 94-108, February.
    10. Suresh Chand & Ting Zeng, 2001. "A Comparison of U-Line and Straight-Line Performances Under Stochastic Task Times," Manufacturing & Service Operations Management, INFORMS, vol. 3(2), pages 138-150, January.
    11. Amy R. Ward & Sunil Kumar, 2008. "Asymptotically Optimal Admission Control of a Queue with Impatient Customers," Mathematics of Operations Research, INFORMS, vol. 33(1), pages 167-202, February.
    12. Wendell G. Gilland, 2001. "Effective Sequencing Rules for Closed Manufacturing Networks," Operations Research, INFORMS, vol. 49(5), pages 759-770, October.
    13. Subba Rao, S. & Gunasekaran, A. & Goyal, S. K. & Martikainen, T., 1998. "Waiting line model applications in manufacturing," International Journal of Production Economics, Elsevier, vol. 54(1), pages 1-28, January.
    14. Hong Chen & Xinyang Shen & David D. Yao, 2002. "Brownian Approximations of Multiclass Open-Queueing Networks," Operations Research, INFORMS, vol. 50(6), pages 1032-1049, December.
    15. Dieter Armbruster & Daniel E. Marthaler & Christian Ringhofer & Karl Kempf & Tae-Chang Jo, 2006. "A Continuum Model for a Re-entrant Factory," Operations Research, INFORMS, vol. 54(5), pages 933-950, October.
    16. Ghosh, Arka P. & Weerasinghe, Ananda P., 2010. "Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic," Stochastic Processes and their Applications, Elsevier, vol. 120(11), pages 2103-2141, November.
    17. Narahari, Y. & Khan, L. M., 1998. "Asymptotic loss of priority scheduling policies in closed re-entrant lines: A computational study," European Journal of Operational Research, Elsevier, vol. 110(3), pages 585-596, November.
    18. Martin I. Reiman & Qiong Wang, 2015. "Asymptotically Optimal Inventory Control for Assemble-to-Order Systems with Identical Lead Times," Operations Research, INFORMS, vol. 63(3), pages 716-732, June.
    19. Dimitris Bertsimas & José Niño-Mora, 1999. "Optimization of Multiclass Queueing Networks with Changeover Times Via the Achievable Region Approach: Part II, The Multi-Station Case," Mathematics of Operations Research, INFORMS, vol. 24(2), pages 331-361, May.
    20. Barış Ata, 2006. "Dynamic Control of a Multiclass Queue with Thin Arrival Streams," Operations Research, INFORMS, vol. 54(5), pages 876-892, October.
    21. S. P. Sethi & H. Yan & H. Zhang & Q. Zhang, 2002. "Optimal and Hierarchical Controls in Dynamic Stochastic Manufacturing Systems: A Survey," Manufacturing & Service Operations Management, INFORMS, vol. 4(2), pages 133-170.
    22. Erica L. Plambeck, 2008. "Asymptotically Optimal Control for an Assemble-to-Order System with Capacitated Component Production and Fixed Transport Costs," Operations Research, INFORMS, vol. 56(5), pages 1158-1171, October.
    23. Barιş Ata & Deishin Lee & Erkut Sönmez, 2019. "Dynamic Volunteer Staffing in Multicrop Gleaning Operations," Operations Research, INFORMS, vol. 67(2), pages 295-314, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:38:y:1990:i:6:p:1052-1064. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.