IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v170y2009i1p233-24910.1007-s10479-008-0443-x.html
   My bibliography  Save this article

Near optimal control of queueing networks over a finite time horizon

Author

Listed:
  • Yoni Nazarathy
  • Gideon Weiss

Abstract

We propose a method for the control of multi-class queueing networks over a finite time horizon. We approximate the multi-class queueing network by a fluid network and formulate a fluid optimization problem which we solve as a separated continuous linear program. The optimal fluid solution partitions the time horizon to intervals in which constant fluid flow rates are maintained. We then use a policy by which the queueing network tracks the fluid solution. To that end we model the deviations between the queuing and the fluid network in each of the intervals by a multi-class queueing network with some infinite virtual queues. We then keep these deviations stable by an adaptation of a maximum pressure policy. We show that this method is asymptotically optimal when the number of items that is processed and the processing speed increase. We illustrate these results through a simple example of a three stage re-entrant line. Copyright Springer Science+Business Media, LLC 2009

Suggested Citation

  • Yoni Nazarathy & Gideon Weiss, 2009. "Near optimal control of queueing networks over a finite time horizon," Annals of Operations Research, Springer, vol. 170(1), pages 233-249, September.
    • Handle: RePEc:spr:annopr:v:170:y:2009:i:1:p:233-249:10.1007/s10479-008-0443-x
    DOI: 10.1007/s10479-008-0443-x
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-008-0443-x
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-008-0443-x?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Lawrence M. Wein, 1992. "Scheduling Networks of Queues: Heavy Traffic Analysis of a Multistation Network with Controllable Inputs," Operations Research, INFORMS, vol. 40(3-supplem), pages 312-334, June.
    2. J. G. Dai & Wuqin Lin, 2005. "Maximum Pressure Policies in Stochastic Processing Networks," Operations Research, INFORMS, vol. 53(2), pages 197-218, April.
    3. Hong Chen & David D. Yao, 1993. "Dynamic Scheduling of a Multiclass Fluid Network," Operations Research, INFORMS, vol. 41(6), pages 1104-1115, December.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Liron Ravner & Yoni Nazarathy, 2017. "Scheduling for a processor sharing system with linear slowdown," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 86(1), pages 71-102, August.
    2. Mohammad Mehdi Nasrabadi & Mohammad Ali Yaghoobi & Mashaallah Mashinchi, 2010. "Solution algorithms for a class of continuous linear programs with fuzzy valued objective functions," Fuzzy Information and Engineering, Springer, vol. 2(1), pages 5-26, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. J. G. Dai & Wuqin Lin, 2005. "Maximum Pressure Policies in Stochastic Processing Networks," Operations Research, INFORMS, vol. 53(2), pages 197-218, April.
    2. Sigrún Andradóttir & Hayriye Ayhan & Douglas G. Down, 2007. "Compensating for Failures with Flexible Servers," Operations Research, INFORMS, vol. 55(4), pages 753-768, August.
    3. Land, Martin & Gaalman, Gerard, 1996. "Workload control concepts in job shops A critical assessment," International Journal of Production Economics, Elsevier, vol. 46(1), pages 535-548, December.
    4. Vijay Mehrotra & Kevin Ross & Geoff Ryder & Yong-Pin Zhou, 2012. "Routing to Manage Resolution and Waiting Time in Call Centers with Heterogeneous Servers," Manufacturing & Service Operations Management, INFORMS, vol. 14(1), pages 66-81, January.
    5. Kilinc, Derya & Saghafian, Soroush & Traub, Stephen, 2016. "Dynamic Assignment of Patients to Primary and Secondary Inpatient Units: Is Patience a Virtue?," Working Paper Series rwp17-010, Harvard University, John F. Kennedy School of Government.
    6. Noa Zychlinski, 2023. "Applications of fluid models in service operations management," Queueing Systems: Theory and Applications, Springer, vol. 103(1), pages 161-185, February.
    7. Cong Shi & Yehua Wei & Yuan Zhong, 2019. "Process Flexibility for Multiperiod Production Systems," Operations Research, INFORMS, vol. 67(5), pages 1300-1320, September.
    8. Lambrecht, Marc R. & Vandaele, Nico J., 1996. "A general approximation for the single product lot sizing model with queueing delays," European Journal of Operational Research, Elsevier, vol. 95(1), pages 73-88, November.
    9. Sigrún Andradóttir & Hayriye Ayhan & Douglas G. Down, 2022. "Synchronous resource allocation: modeling, capacity, and optimization," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(4), pages 1287-1310, December.
    10. Mihalis G. Markakis & Eytan Modiano & John N. Tsitsiklis, 2018. "Delay Analysis of the Max-Weight Policy Under Heavy-Tailed Traffic via Fluid Approximations," Mathematics of Operations Research, INFORMS, vol. 43(2), pages 460-493, May.
    11. J. G. Dai & Gideon Weiss, 2002. "A Fluid Heuristic for Minimizing Makespan in Job Shops," Operations Research, INFORMS, vol. 50(4), pages 692-707, August.
    12. Maglaras, Constantinos & Van Mieghem, Jan A., 2005. "Queueing systems with leadtime constraints: A fluid-model approach for admission and sequencing control," European Journal of Operational Research, Elsevier, vol. 167(1), pages 179-207, November.
    13. repec:dgr:rugsom:95a42 is not listed on IDEAS
    14. Kathryn E. Caggiano & John A. Muckstadt & James A. Rappold, 2006. "Integrated Real-Time Capacity and Inventory Allocation for Reparable Service Parts in a Two-Echelon Supply System," Manufacturing & Service Operations Management, INFORMS, vol. 8(3), pages 292-319, August.
    15. Junfei Huang & Boaz Carmeli & Avishai Mandelbaum, 2015. "Control of Patient Flow in Emergency Departments, or Multiclass Queues with Deadlines and Feedback," Operations Research, INFORMS, vol. 63(4), pages 892-908, August.
    16. Maury Bramson & Bernardo D’Auria & Neil Walton, 2017. "Proportional Switching in First-in, First-out Networks," Operations Research, INFORMS, vol. 65(2), pages 496-513, April.
    17. Milind Dawande & Zhichao Feng & Ganesh Janakiraman, 2021. "On the Structure of Bottlenecks in Processes," Management Science, INFORMS, vol. 67(6), pages 3853-3870, June.
    18. Ick-Hyun Nam, 2001. "Dynamic Scheduling for a Flexible Processing Network," Operations Research, INFORMS, vol. 49(2), pages 305-315, April.
    19. Constantinos Maglaras, 2006. "Revenue Management for a Multiclass Single-Server Queue via a Fluid Model Analysis," Operations Research, INFORMS, vol. 54(5), pages 914-932, October.
    20. Li, Hui & Liu, Liming, 2006. "Production control in a two-stage system," European Journal of Operational Research, Elsevier, vol. 174(2), pages 887-904, October.
    21. Jinsheng Chen & Jing Dong & Pengyi Shi, 2020. "A survey on skill-based routing with applications to service operations management," Queueing Systems: Theory and Applications, Springer, vol. 96(1), pages 53-82, October.

    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:spr:annopr:v:170:y:2009:i:1:p:233-249:10.1007/s10479-008-0443-x. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.