IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v238y2016i1d10.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.

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:d:10.1007_s10479-015-2000-8
    DOI: 10.1007/s10479-015-2000-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-015-2000-8
    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/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. 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.
    2. 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.
    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. 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.
    5. Torben Meisling, 1958. "Discrete-Time Queuing Theory," Operations Research, INFORMS, vol. 6(1), pages 96-105, February.
    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. 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.
    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. Herwig Bruneel & Arnaud Devos, 2024. "Explicit Solutions for Coupled Parallel Queues," Mathematics, MDPI, vol. 12(15), pages 1-31, July.
    6. 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.
    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. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. Nils Boysen & Stefan Fedtke & Felix Weidinger, 2017. "Truck Scheduling in the Postal Service Industry," Transportation Science, INFORMS, vol. 51(2), pages 723-736, May.
    14. Baruch Mor & Gur Mosheiov, 2021. "Minmax due-date assignment on a two-machine flowshop," Annals of Operations Research, Springer, vol. 305(1), pages 191-209, October.
    15. Alexander Seitz & Martin Grunow, 2017. "Increasing accuracy and robustness of order promises," International Journal of Production Research, Taylor & Francis Journals, vol. 55(3), pages 656-670, February.
    16. Thu-Ba T. Nguyen & Appa Iyer Sivakumar & Stephen C. Graves, 2017. "Scheduling rules to achieve lead-time targets in outpatient appointment systems," Health Care Management Science, Springer, vol. 20(4), pages 578-589, December.
    17. Wu, Yu-Bin & Wan, Long & Wang, Xiao-Yuan, 2015. "Study on due-window assignment scheduling based on common flow allowance," International Journal of Production Economics, Elsevier, vol. 165(C), pages 155-157.
    18. Koulamas, Christos & Kyparisis, George J., 2023. "A classification of dynamic programming formulations for offline deterministic single-machine scheduling problems," European Journal of Operational Research, Elsevier, vol. 305(3), pages 999-1017.
    19. Yantong Li & Jean-François Côté & Leandro Callegari-Coelho & Peng Wu, 2022. "Novel Formulations and Logic-Based Benders Decomposition for the Integrated Parallel Machine Scheduling and Location Problem," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1048-1069, March.
    20. 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.

    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:d: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.