IDEAS home Printed from https://ideas.repec.org/a/spr/queues/v85y2017i3d10.1007_s11134-017-9515-4.html
   My bibliography  Save this article

A general workload conservation law with applications to queueing systems

Author

Listed:
  • Muhammad El-Taha

    (University of Southern Maine)

Abstract

In the spirit of Little’s law $$L=\lambda W$$ L = λ W and its extension $$H=\lambda G$$ H = λ G we use sample-path analysis to give a general conservation law. For queueing models the law relates the asymptotic average workload in the system to the conditional asymptotic average sojourn time and service times distribution function. This law generalizes previously obtained conservation laws for both single- and multi-server systems, and anticipating and non-anticipating scheduling disciplines. Applications to single- and multi-class queueing and other systems that illustrate the versatility of this law are given. In particular, we show that, for anticipative and non-anticipative scheduling rules, the unconditional delay in a queue is related to the covariance of service times and queueing delays.

Suggested Citation

  • Muhammad El-Taha, 2017. "A general workload conservation law with applications to queueing systems," Queueing Systems: Theory and Applications, Springer, vol. 85(3), pages 361-381, April.
    • Handle: RePEc:spr:queues:v:85:y:2017:i:3:d:10.1007_s11134-017-9515-4
    DOI: 10.1007/s11134-017-9515-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11134-017-9515-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s11134-017-9515-4?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. A. Federgruen & H. Groenevelt, 1988. "M/G/c Queueing Systems with Multiple Customer Classes: Characterization and Control of Achievable Performance Under Nonpreemptive Priority Rules," Management Science, INFORMS, vol. 34(9), pages 1121-1138, September.
    2. M. Dacre & K. Glazebrook & J. Niño‐Mora, 1999. "The achievable region approach to the optimal control of stochastic systems," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 61(4), pages 747-791.
    3. Daniel P. Heyman & Shaler Stidham, 1980. "The Relation between Customer and Time Averages in Queues," Operations Research, INFORMS, vol. 28(4), pages 983-994, August.
    4. Muhammad El-Taha, 2016. "Invariance of workload in queueing systems," Queueing Systems: Theory and Applications, Springer, vol. 83(1), pages 181-192, June.
    Full references (including those not matched with items on IDEAS)

    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. Muhammad El-Taha, 2016. "Invariance of workload in queueing systems," Queueing Systems: Theory and Applications, Springer, vol. 83(1), pages 181-192, June.
    2. Vanlerberghe, Jasper & Walraevens, Joris & Maertens, Tom & Bruneel, Herwig, 2018. "Calculation of the performance region of an easy-to-optimize alternative for Generalized Processor Sharing," European Journal of Operational Research, Elsevier, vol. 270(2), pages 625-635.
    3. Jasper Vanlerberghe & Tom Maertens & Joris Walraevens & Stijn Vuyst & Herwig Bruneel, 2016. "On the optimization of two-class work-conserving parameterized scheduling policies," 4OR, Springer, vol. 14(3), pages 281-308, September.
    4. José Niño-Mora, 2006. "Restless Bandit Marginal Productivity Indices, Diminishing Returns, and Optimal Control of Make-to-Order/Make-to-Stock M/G/1 Queues," Mathematics of Operations Research, INFORMS, vol. 31(1), pages 50-84, February.
    5. Sai Rajesh Mahabhashyam & Natarajan Gautam & Soundar R. T. Kumara, 2008. "Resource-Sharing Queueing Systems with Fluid-Flow Traffic," Operations Research, INFORMS, vol. 56(3), pages 728-744, June.
    6. Bertsimas, Dimitris., 1995. "The achievable region method in the optimal control of queueing systems : formulations, bounds and policies," Working papers 3837-95., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    7. R. T. Dunn & K. D. Glazebrook, 2004. "Discounted Multiarmed Bandit Problems on a Collection of Machines with Varying Speeds," Mathematics of Operations Research, INFORMS, vol. 29(2), pages 266-279, May.
    8. José Niño-Mora, 2000. "On certain greedoid polyhedra, partially indexable scheduling problems and extended restless bandit allocation indices," Economics Working Papers 456, Department of Economics and Business, Universitat Pompeu Fabra.
    9. Veeraruna Kavitha & Jayakrishnan Nair & Raman Kumar Sinha, 2019. "Pseudo conservation for partially fluid, partially lossy queueing systems," Annals of Operations Research, Springer, vol. 277(2), pages 255-292, June.
    10. R. Garbe & K. D. Glazebrook, 1998. "Submodular Returns and Greedy Heuristics for Queueing Scheduling Problems," Operations Research, INFORMS, vol. 46(3), pages 336-346, June.
    11. Peter Whittle, 2002. "Applied Probability in Great Britain," Operations Research, INFORMS, vol. 50(1), pages 227-239, February.
    12. José Niño-Mora, 2000. "Beyond Smith's rule: An optimal dynamic index, rule for single machine stochastic scheduling with convex holding costs," Economics Working Papers 514, Department of Economics and Business, Universitat Pompeu Fabra.
    13. Dimitris Bertsimas & Vivek F. Farias & Nikolaos Trichakis, 2012. "On the Efficiency-Fairness Trade-off," Management Science, INFORMS, vol. 58(12), pages 2234-2250, December.
    14. Bertsimas, Dimitris. & Niño-Mora, Jose., 1994. "Restless bandit, linear programming relaxations and a primal-dual heuristic," Working papers 3727-94., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    15. Ryan Palmer & Martin Utley, 2020. "On the modelling and performance measurement of service networks with heterogeneous customers," Annals of Operations Research, Springer, vol. 293(1), pages 237-268, October.
    16. Vinck, Bart & Bruneel, Herwig, 2006. "System delay versus system content for discrete-time queueing systems subject to server interruptions," European Journal of Operational Research, Elsevier, vol. 175(1), pages 362-375, November.
    17. Esther Frostig & Gideon Weiss, 2016. "Four proofs of Gittins’ multiarmed bandit theorem," Annals of Operations Research, Springer, vol. 241(1), pages 127-165, June.
    18. Masselink, Inge H.J. & van der Mijden, Thomas L.C. & Litvak, Nelly & Vanberkel, Peter T., 2012. "Preparation of chemotherapy drugs: Planning policy for reduced waiting times," Omega, Elsevier, vol. 40(2), pages 181-187, April.
    19. Wenjun Ni & Jia Shu & Miao Song & Dachuan Xu & Kaike Zhang, 2021. "A Branch-and-Price Algorithm for Facility Location with General Facility Cost Functions," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 86-104, January.
    20. John D. C. Little, 2011. "OR FORUM---Little's Law as Viewed on Its 50th Anniversary," Operations Research, INFORMS, vol. 59(3), pages 536-549, June.

    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:queues:v:85:y:2017:i:3:d:10.1007_s11134-017-9515-4. 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.