IDEAS home Printed from https://ideas.repec.org/a/spr/mathme/v82y2015i3p285-315.html
   My bibliography  Save this article

Analysis of a discrete-time queue with general independent arrivals, general service demands and fixed service capacity

Author

Listed:
  • H. Bruneel
  • W. Rogiest
  • J. Walraevens
  • S. Wittevrongel

Abstract

This paper analyzes a single-server discrete-time queueing model with general independent arrivals, where the service process of the server is characterized in two steps. Specifically, the model assumes that (1) each customer represents a random, arbitrarily distributed, amount of work for the server, the service demand, and (2) the server disposes of a fixed number of work units that can be executed per slot, the service capacity. For this non-classical queueing model, we obtain explicit closed-form results for the probability generating functions (pgf’s) of the unfinished work in the system (expressed in work units) and the queueing delay of an arbitrary customer (expressed in time slots). Deriving the pgf of the number of customers in the system turns out to be hard, in general. Nevertheless, we derive this pgf explicitly in a number of special cases, i.e., either for geometrically distributed service demands, and/or for Bernoulli arrivals or geometric arrivals. The obtained results show that the tail distributions of the unfinished work, the customer delay and the system content all exhibit a geometric decay, with semi-analytic formulas for the decay rates available. Another interesting conclusion is that, for a given system load, the mean customer delay converges to constant limiting values when the service capacity per slot goes to infinity, and either the mean arrival rate or the mean service demand increases proportionally. Accurate approximative analytical expressions are available for these limiting values. Copyright Springer-Verlag Berlin Heidelberg 2015

Suggested Citation

  • H. Bruneel & W. Rogiest & J. Walraevens & S. Wittevrongel, 2015. "Analysis of a discrete-time queue with general independent arrivals, general service demands and fixed service capacity," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 82(3), pages 285-315, December.
  • Handle: RePEc:spr:mathme:v:82:y:2015:i:3:p:285-315
    DOI: 10.1007/s00186-015-0515-z
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s00186-015-0515-z
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1007/s00186-015-0515-z?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. Bruneel, Herwig, 1984. "A general model for the behaviour of infinite buffers with periodic service opportunities," European Journal of Operational Research, Elsevier, vol. 16(1), pages 98-106, April.
    2. M. L. Chaudhry & Gagandeep Singh & U. C. Gupta, 2013. "A Simple and Complete Computational Analysis of MAP/R/1 Queue Using Roots," Methodology and Computing in Applied Probability, Springer, vol. 15(3), pages 563-582, September.
    3. S. Creemers & J. Beliën & M. Lambrecht, 2012. "The optimal allocation of server time slots over different classes of customers," Post-Print hal-00800190, HAL.
    4. Maertens, Tom & Walraevens, Joris & Bruneel, Herwig, 2007. "A modified HOL priority scheduling discipline: Performance analysis," European Journal of Operational Research, Elsevier, vol. 180(3), pages 1168-1185, August.
    5. M Haughton & K P S Isotupa, 2013. "Flow control in capacity-constrained queueing systems with non-stationary arrivals," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(2), pages 283-292, February.
    6. Dieter Claeys & Koenraad Laevens & Joris Walraevens & Herwig Bruneel, 2010. "Complete characterisation of the customer delay in a queueing system with batch arrivals and batch service," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 72(1), pages 1-23, August.
    7. Creemers, Stefan & Beliën, Jeroen & Lambrecht, Marc, 2012. "The optimal allocation of server time slots over different classes of patients," European Journal of Operational Research, Elsevier, vol. 219(3), pages 508-521.
    8. Laevens, Koenraad & Bruneel, Herwig, 1995. "Delay analysis for discrete-time queueing systems with multiple randomly interrupted servers," European Journal of Operational Research, Elsevier, vol. 85(1), pages 161-177, August.
    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. Herwig Bruneel & Sabine Wittevrongel & Dieter Claeys & Joris Walraevens, 2016. "Discrete-time queues with variable service capacity: a basic model and its analysis," Annals of Operations Research, Springer, vol. 239(2), pages 359-380, April.
    2. Vink, Wouter & Kuiper, Alex & Kemper, Benjamin & Bhulai, Sandjai, 2015. "Optimal appointment scheduling in continuous time: The lag order approximation method," European Journal of Operational Research, Elsevier, vol. 240(1), pages 213-219.
    3. Wilson, Duncan T. & Hawe, Glenn I. & Coates, Graham & Crouch, Roger S., 2013. "A multi-objective combinatorial model of casualty processing in major incident response," European Journal of Operational Research, Elsevier, vol. 230(3), pages 643-655.
    4. Miao Bai & Bjorn Berg & Esra Sisikoglu Sir & Mustafa Y. Sir, 2023. "Partially partitioned templating strategies for outpatient specialty practices," Production and Operations Management, Production and Operations Management Society, vol. 32(1), pages 301-318, January.
    5. Masoomeh Zeinalnezhad & Abdoulmohammad Gholamzadeh Chofreh & Feybi Ariani Goni & Jiří Jaromír Klemeš & Emelia Sari, 2020. "Simulation and Improvement of Patients’ Workflow in Heart Clinics during COVID-19 Pandemic Using Timed Coloured Petri Nets," IJERPH, MDPI, vol. 17(22), pages 1-18, November.
    6. Michael Samudra & Carla Van Riet & Erik Demeulemeester & Brecht Cardoen & Nancy Vansteenkiste & Frank E. Rademakers, 2016. "Scheduling operating rooms: achievements, challenges and pitfalls," Journal of Scheduling, Springer, vol. 19(5), pages 493-525, October.
    7. Almehdawe, Eman & Jewkes, Beth & He, Qi-Ming, 2013. "A Markovian queueing model for ambulance offload delays," European Journal of Operational Research, Elsevier, vol. 226(3), pages 602-614.
    8. Nguyen, Thu Ba T. & Sivakumar, Appa Iyer & Graves, Stephen C., 2018. "Capacity planning with demand uncertainty for outpatient clinics," European Journal of Operational Research, Elsevier, vol. 267(1), pages 338-348.
    9. Shehadeh, Karmel S. & Cohn, Amy E.M. & Epelman, Marina A., 2019. "Analysis of models for the Stochastic Outpatient Procedure Scheduling Problem," European Journal of Operational Research, Elsevier, vol. 279(3), pages 721-731.
    10. De Vuyst, Stijn & Bruneel, Herwig & Fiems, Dieter, 2014. "Computationally efficient evaluation of appointment schedules in health care," European Journal of Operational Research, Elsevier, vol. 237(3), pages 1142-1154.
    11. Bruneel, Herwig & Mélange, Willem & Steyaert, Bart & Claeys, Dieter & Walraevens, Joris, 2012. "A two-class discrete-time queueing model with two dedicated servers and global FCFS service discipline," European Journal of Operational Research, Elsevier, vol. 223(1), pages 123-132.
    12. Ahmadi-Javid, Amir & Jalali, Zahra & Klassen, Kenneth J, 2017. "Outpatient appointment systems in healthcare: A review of optimization studies," European Journal of Operational Research, Elsevier, vol. 258(1), pages 3-34.
    13. Shuwan Zhu & Wenjuan Fan & Shanlin Yang & Jun Pei & Panos M. Pardalos, 2019. "Operating room planning and surgical case scheduling: a review of literature," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 757-805, April.
    14. Chen, Ting-Yu & Chang, Chien-Hung & Rachel Lu, Jui-fen, 2013. "The extended QUALIFLEX method for multiple criteria decision analysis based on interval type-2 fuzzy sets and applications to medical decision making," European Journal of Operational Research, Elsevier, vol. 226(3), pages 615-625.
    15. Michiel Muynck & Sabine Wittevrongel & Herwig Bruneel, 2017. "Analysis of discrete-time queues with general service demands and finite-support service capacities," Annals of Operations Research, Springer, vol. 252(1), pages 3-28, May.
    16. Deceuninck, Matthias & Fiems, Dieter & De Vuyst, Stijn, 2018. "Outpatient scheduling with unpunctual patients and no-shows," European Journal of Operational Research, Elsevier, vol. 265(1), pages 195-207.
    17. 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.
    18. Freek Verdonck & Herwig Bruneel & Sabine Wittevrongel, 2021. "Delay in a 2-State Discrete-Time Queue with Stochastic State-Period Lengths and State-Dependent Server Availability and Arrivals," Mathematics, MDPI, vol. 9(14), pages 1-17, July.
    19. Laevens, Koenraad & Bruneel, Herwig, 1995. "Delay analysis for discrete-time queueing systems with multiple randomly interrupted servers," European Journal of Operational Research, Elsevier, vol. 85(1), pages 161-177, August.
    20. Freek Verdonck & Herwig Bruneel & Sabine Wittevrongel, 2022. "Delay analysis of a discrete-time single-server queue with an occasional extra server," Annals of Operations Research, Springer, vol. 310(2), pages 551-575, 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:spr:mathme:v:82:y:2015:i:3:p:285-315. 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.