IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v238y2016i1p69-9710.1007-s10479-015-2000-8.html
   My bibliography  Save this article

Analysis of a discrete-time queue with time-limited overtake priority

Author

Listed:
  • Sofian Clercq
  • Bart Steyaert
  • Sabine Wittevrongel
  • Herwig Bruneel

Abstract

In this paper, we investigate a single-server discrete-time queueing system subject to two independent batch Bernoulli arrival processes, each supplying the queue with different customer classes. The two classes of customers have different priority levels in the queue, and different service-time distributions. The studied priority mechanism is time-limited, i.e., customers of the high-priority class cannot overtake customers of lower priority if the latter arrived at least N slots earlier than the former. The parameter N makes the mechanism versatile, spanning a bridge between absolute (fixed) priority and slot-bound priority (see De Clercq et al. in Math Probl Eng. doi: 10.1155/2012/425630 , 2012 ). The time-limited overtake priority mechanism maintains levels of fairness that are unattainable by a pure absolute priority mechanism, and offers more service differentiation than the slot-bound priority alternative studied earlier. By using a censoring argument, we obtain expressions for the steady-state probability generating functions of the delays of both customer classes, as well as the steady-state joint probability generating function of the system content, by using a censoring argument. Copyright Springer Science+Business Media New York 2016

Suggested Citation

  • Sofian Clercq & Bart Steyaert & Sabine Wittevrongel & Herwig Bruneel, 2016. "Analysis of a discrete-time queue with time-limited overtake priority," Annals of Operations Research, Springer, vol. 238(1), pages 69-97, March.
    • Handle: RePEc:spr:annopr:v:238:y:2016:i:1:p:69-97:10.1007/s10479-015-2000-8
    DOI: 10.1007/s10479-015-2000-8
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-015-2000-8
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-015-2000-8?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. 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.
    2. Torben Meisling, 1958. "Discrete-Time Queuing Theory," Operations Research, INFORMS, vol. 6(1), pages 96-105, February.
    3. Sofian De Clercq & Koenraad Laevens & Bart Steyaert & Herwig Bruneel, 2013. "A multi-class discrete-time queueing system under the FCFS service discipline," Annals of Operations Research, Springer, vol. 202(1), pages 59-73, January.
    4. Janiak, Adam & Janiak, Władysław A. & Krysiak, Tomasz & Kwiatkowski, Tomasz, 2015. "A survey on scheduling problems with due windows," European Journal of Operational Research, Elsevier, vol. 242(2), pages 347-357.
    5. Herwig Bruneel & Dieter Fiems & Joris Walraevens & Sabine Wittevrongel, 2014. "Queueing models for the analysis of communication systems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 22(2), pages 421-448, July.
    6. Henry M. Goldberg, 1977. "Analysis of the Earliest Due Date Scheduling Rule in Queueing Systems," Mathematics of Operations Research, INFORMS, vol. 2(2), pages 145-154, May.
    7. Herwig Bruneel & Dieter Fiems & Joris Walraevens & Sabine Wittevrongel, 2014. "Rejoinder on: Queueing models for the analysis of communication systems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 22(2), pages 460-468, July.
    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. Sofian Clercq & Bart Steyaert & Sabine Wittevrongel & Herwig Bruneel, 2016. "Analysis of a discrete-time queue with time-limited overtake priority," Annals of Operations Research, Springer, vol. 238(1), pages 69-97, March.
    2. 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.
    3. Onno Boxma, 2014. "Comments on: Queueing models for the analysis of communication systems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 22(2), pages 449-453, July.
    4. Öner-Közen, Miray & Minner, Stefan, 2017. "Impact of priority sequencing decisions on on-time probability and expected tardiness of orders in make-to-order production systems with external due-dates," European Journal of Operational Research, Elsevier, vol. 263(2), pages 524-539.
    5. Rong-Rong Mao & Yi-Chun Wang & Dan-Yang Lv & Ji-Bo Wang & Yuan-Yuan Lu, 2023. "Delivery Times Scheduling with Deterioration Effects in Due Window Assignment Environments," Mathematics, MDPI, vol. 11(18), pages 1-18, September.
    6. Dujuan Wang & Yunqiang Yin & T.C.E. Cheng, 2017. "A bicriterion approach to common flow allowances due window assignment and scheduling with controllable processing times," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(1), pages 41-63, February.
    7. Feng Li & Zhi-Long Chen & Zhi-Long Chen, 2017. "Integrated Production, Inventory and Delivery Problems: Complexity and Algorithms," INFORMS Journal on Computing, INFORMS, vol. 29(2), pages 232-250, May.
    8. Gary Chang & Chung-Chieh Lee, 2015. "Priority Queues with Fractional Service for Tiered Delay QoS," Future Internet, MDPI, vol. 8(1), pages 1-15, December.
    9. Yunqiang Yin & Du-Juan Wang & T C E Cheng & Chin-Chia Wu, 2016. "Bi-criterion single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 67(9), pages 1169-1183, September.
    10. I. Atencia & A. Pechinkin, 2013. "A discrete-time queueing system with optional LCFS discipline," Annals of Operations Research, Springer, vol. 202(1), pages 3-17, January.
    11. Yi-Chun Wang & Si-Han Wang & Ji-Bo Wang, 2023. "Resource Allocation Scheduling with Position-Dependent Weights and Generalized Earliness–Tardiness Cost," Mathematics, MDPI, vol. 11(1), pages 1-11, January.
    12. I. Atencia, 2015. "A discrete-time queueing system with server breakdowns and changes in the repair times," Annals of Operations Research, Springer, vol. 235(1), pages 37-49, December.
    13. Yongjiang Guo & Xiyang Hou & Yunan Liu, 2021. "A functional law of the iterated logarithm for multi-class queues with batch arrivals," Annals of Operations Research, Springer, vol. 300(1), pages 51-77, May.
    14. Zhongyi Jiang & Fangfang Chen & Xiandong Zhang, 2017. "Single-machine scheduling with times-based and job-dependent learning effect," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(7), pages 809-815, July.
    15. Baruch Mor, 2019. "Minmax scheduling problems with common due-date and completion time penalty," Journal of Combinatorial Optimization, Springer, vol. 38(1), pages 50-71, July.
    16. Xinyu Sun & Xin-Na Geng & Tao Liu, 2020. "Due-window assignment scheduling in the proportionate flow shop setting," Annals of Operations Research, Springer, vol. 292(1), pages 113-131, September.
    17. Shabtay, Dvir & Mosheiov, Gur & Oron, Daniel, 2022. "Single machine scheduling with common assignable due date/due window to minimize total weighted early and late work," European Journal of Operational Research, Elsevier, vol. 303(1), pages 66-77.
    18. Mor, Baruch & Mosheiov, Gur, 2016. "Minsum and minmax scheduling on a proportionate flowshop with common flow-allowance," European Journal of Operational Research, Elsevier, vol. 254(2), pages 360-370.
    19. Na Li & David A. Stanford & Peter Taylor & Ilze Ziedins, 2017. "Nonlinear Accumulating Priority Queues with Equivalent Linear Proxies," Operations Research, INFORMS, vol. 65(6), pages 1712-1721, December.
    20. Moshe Haviv & Liron Ravner, 2016. "Strategic bidding in an accumulating priority queue: equilibrium analysis," Annals of Operations Research, Springer, vol. 244(2), pages 505-523, September.

    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:238:y:2016:i:1:p:69-97:10.1007/s10479-015-2000-8. 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.