IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v235y2014i1p149-158.html
   My bibliography  Save this article

Class clustering destroys delay differentiation in priority queues

Author

Listed:
  • Bruneel, Herwig
  • Maertens, Tom
  • Walraevens, Joris

Abstract

This paper considers a discrete-time priority queueing model with one server and two types (classes) of customers. Class-1 customers have absolute (service) priority over class-2 customers. New customer batches enter the system at the rate of one batch per slot, according to a general independent arrival process, i.e., the batch sizes (total numbers of arrivals) during consecutive time slots are i.i.d. random variables with arbitrary distribution. All customers entering the system during the same time slot (i.e., belonging to the same arrival batch) are of the same type, but customer types may change from slot to slot, i.e., from batch to batch. Specifically, the types of consecutive customer batches are correlated in a Markovian way, i.e., the probability that any batch of customers has type 1 or 2, respectively, depends on the type of the previous customer batch that has entered the system. Such an arrival model allows to vary not only the relative loads of both customer types in the arrival stream, but also the amount of correlation between the types of consecutive arrival batches. The results reveal that the amount of delay differentiation between the two customer classes that can be achieved by the priority mechanism strongly depends on the amount of such interclass correlation (or, class clustering) in the arrival stream. We believe that this phenomenon has been largely overlooked in the priority-scheduling literature.

Suggested Citation

  • Bruneel, Herwig & Maertens, Tom & Walraevens, Joris, 2014. "Class clustering destroys delay differentiation in priority queues," European Journal of Operational Research, Elsevier, vol. 235(1), pages 149-158.
  • Handle: RePEc:eee:ejores:v:235:y:2014:i:1:p:149-158
    DOI: 10.1016/j.ejor.2013.12.005
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221713009806
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2013.12.005?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. 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.
    2. Peixia Gao & Sabine Wittevrongel & Joris Walraevens & Herwig Bruneel, 2008. "Analytic study of multiserver buffers with two-state Markovian arrivals and constant service times of multiple slots," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 67(2), pages 269-284, April.
    3. Tom Maertens & Joris Walraevens & Herwig Bruneel, 2008. "Performance comparison of several priority schemes with priority jumps," Annals of Operations Research, Springer, vol. 162(1), pages 109-125, September.
    4. Evin Uzun Jacobson & Nilay Tanık Argon & Serhan Ziya, 2012. "Priority Assignment in Emergency Response," Operations Research, INFORMS, vol. 60(4), pages 813-832, August.
    5. Walraevens, Joris & Steyaert, Bart & Bruneel, Herwig, 2004. "Performance analysis of a GI-Geo-1 buffer with a preemptive resume priority scheduling discipline," European Journal of Operational Research, Elsevier, vol. 157(1), pages 130-151, August.
    6. Feng, Wei & Umemura, Masataka, 2009. "Analysis of a finite buffer model with two servers and two nonpreemptive priority classes," European Journal of Operational Research, Elsevier, vol. 192(1), pages 151-172, January.
    7. I. J. B. F. Adan & A. Sleptchenko & G. J. Van Houtum, 2009. "Reducing Costs Of Spare Parts Supply Systems Via Static Priorities," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 26(04), pages 559-585.
    8. Walraevens, Joris & Fiems, Dieter & Wittevrongel, Sabine & Bruneel, Herwig, 2009. "Calculation of output characteristics of a priority queue through a busy period analysis," European Journal of Operational Research, Elsevier, vol. 198(3), pages 891-898, November.
    9. Steve Drekic & Winfried Grassmann, 2002. "An Eigenvalue Approach to Analyzing a Finite Source Priority Queueing Model," Annals of Operations Research, Springer, vol. 112(1), pages 139-152, April.
    10. Hong Chen & Hanqin Zhang, 2000. "Stability of Multiclass Queueing Networks Under Priority Service Disciplines," Operations Research, INFORMS, vol. 48(1), pages 26-37, February.
    11. Pakes, Anthony G. & Phatarfod, R. M., 1978. "The limiting distribution for the infinitely deep dam with a Markovian input," Stochastic Processes and their Applications, Elsevier, vol. 8(2), pages 199-209, 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. Herwig Bruneel & Tom Maertens & Bart Steyaert & Dieter Claeys & Dieter Fiems & Joris Walraevens, 2018. "Analysis of a two-class single-server discrete-time FCFS queue: the effect of interclass correlation," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(3), pages 403-436, October.

    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 & Tom Maertens & Bart Steyaert & Dieter Claeys & Dieter Fiems & Joris Walraevens, 2018. "Analysis of a two-class single-server discrete-time FCFS queue: the effect of interclass correlation," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(3), pages 403-436, October.
    2. Chou, Chang-Chi & Chiang, Wen-Chu & Chen, Albert Y., 2022. "Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    3. Emmett J. Lodree & Nezih Altay & Robert A. Cook, 2019. "Staff assignment policies for a mass casualty event queuing network," Annals of Operations Research, Springer, vol. 283(1), pages 411-442, December.
    4. Haque, Lani & Armstrong, Michael J., 2007. "A survey of the machine interference problem," European Journal of Operational Research, Elsevier, vol. 179(2), pages 469-482, June.
    5. Sung, Inkyung & Lee, Taesik, 2016. "Optimal allocation of emergency medical resources in a mass casualty incident: Patient prioritization by column generation," European Journal of Operational Research, Elsevier, vol. 252(2), pages 623-634.
    6. van der Heijden, M.C. & Alvarez, E.M. & Schutten, J.M.J., 2013. "Inventory reduction in spare part networks by selective throughput time reduction," International Journal of Production Economics, Elsevier, vol. 143(2), pages 509-517.
    7. Winfried K. Grassmann & Steve Drekic, 2008. "Multiple Eigenvalues in Spectral Analysis for Solving QBD Processes," Methodology and Computing in Applied Probability, Springer, vol. 10(1), pages 73-83, March.
    8. Herwig Bruneel & Arnaud Devos, 2024. "Explicit Solutions for Coupled Parallel Queues," Mathematics, MDPI, vol. 12(15), pages 1-31, July.
    9. Ashley Childers & Maria Mayorga & Kevin Taaffe, 2014. "Prioritization strategies for patient evacuations," Health Care Management Science, Springer, vol. 17(1), pages 77-87, March.
    10. Zhongzhen Yang & Liquan Guo & Zaili Yang, 2019. "Emergency logistics for wildfire suppression based on forecasted disaster evolution," Annals of Operations Research, Springer, vol. 283(1), pages 917-937, December.
    11. Driessen, M.A. & van Houtum, G.J. & Zijm, W.H.M. & Rustenburg, W.D., 2020. "Capacity assignment in repair shops with high material uncertainty," International Journal of Production Economics, Elsevier, vol. 221(C).
    12. Dong Li & Li Ding & Stephen Connor, 2020. "When to Switch? Index Policies for Resource Scheduling in Emergency Response," Production and Operations Management, Production and Operations Management Society, vol. 29(2), pages 241-262, February.
    13. Doroudi, Sherwin & Avgerinos, Thanassis & Harchol-Balter, Mor, 2021. "To clean or not to clean: Malware removal strategies for servers under load," European Journal of Operational Research, Elsevier, vol. 292(2), pages 596-609.
    14. Carlo Drago & Matteo Ruggeri, 2019. "Setting research priorities in the field of emergency management: which piece of information are you willing to pay more?," Quality & Quantity: International Journal of Methodology, Springer, vol. 53(4), pages 2103-2115, July.
    15. Li Zhu & Yeming Gong & Yishui Xu & Jun Gu, 2019. "Emergency relief routing models for injured victims considering equity and priority," Annals of Operations Research, Springer, vol. 283(1), pages 1573-1606, December.
    16. Yu Wang & Yu Zhang & Minglong Zhou & Jiafu Tang, 2023. "Feature‐driven robust surgery scheduling," Production and Operations Management, Production and Operations Management Society, vol. 32(6), pages 1921-1938, June.
    17. 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.
    18. Levner, Eugene & Perlman, Yael & Cheng, T.C.E. & Levner, Ilya, 2011. "A network approach to modeling the multi-echelon spare-part inventory system with backorders and interval-valued demand," International Journal of Production Economics, Elsevier, vol. 132(1), pages 43-51, July.
    19. Eugene Furman & Adam Diamant & Murat Kristal, 2021. "Customer Acquisition and Retention: A Fluid Approach for Staffing," Production and Operations Management, Production and Operations Management Society, vol. 30(11), pages 4236-4257, November.
    20. Lee, Hyun-Rok & Lee, Taesik, 2021. "Multi-agent reinforcement learning algorithm to solve a partially-observable multi-agent problem in disaster response," European Journal of Operational Research, Elsevier, vol. 291(1), pages 296-308.

    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:eee:ejores:v:235:y:2014:i:1:p:149-158. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.