IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v51y2003i1p113-122.html
   My bibliography  Save this article

Due-Date Scheduling: Asymptotic Optimality of Generalized Longest Queue and Generalized Largest Delay Rules

Author

Listed:
  • Jan A. Van Mieghem

    (Kellogg School of Management, Northwestern University, Evanston, Illinois 60208-2009)

Abstract

Consider the following due-date scheduling problem in a multiclass, acyclic, single-station service system: Any class k job arriving at time t must be served by its due date t + D k . Equivalently, its delay (tau) k must not exceed a given delay or lead-time D k . In a stochastic system, the constraint (tau) k (le) D k must be interpreted in a probabilistic sense. Regardless of the precise probabilistic formulation, however, the associated optimal control problem is intractable with exact analysis. This article proposes a new formulation which incorporates the constraint through a sequence of convex-increasing delay cost functions. This formulation reduces the intractable optimal scheduling problem into one for which the Generalized c(mu) (G c(mu) ) scheduling rule is known to be asymptotically optimal. The G c(mu) rule simplifies here to a generalized longest queue (GLQ) or generalized largest delay (GLD) rule, which are defined as follows. Let N k be the number of class k jobs in system, (lambda) k their arrival rate, and a k the age of their oldest job in the system. GLQ and GLD are dynamic priority rules, parameterized by (theta) : GLQ( (theta) ) serves FIFO within class and prioritizes the class with highest index (theta) k N k , whereas GLD( (theta) ) uses index (theta) k (lambda) k a k .The argument is presented first intuitively, but is followed by a limit analysis that expresses the cost objective in terms of the maximal due-date violation probability. This proves that GLQ( (theta) * ) and GLD( (theta) * ), where (theta) * ,k = 1/ (lambda) k D k , asymptotically minimize the probability of maximal due-date violation in heavy traffic. Specifically, they minimize \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$\mbox{lim}\, \mbox{inf}_{n\to\infty}\mbox{Pr}\{\max_k \mbox{sup}_{s\in [0,t]}\tfrac{\tau_k(ns)}{n^{1/2}D_k}\geq x\}$\end{document} for all positive t and x , where (tau) k ( s ) is the delay of the most recent class k job that arrived before time s . GLQ with appropriate parameter (theta) (alpha) also reduces “total variability” because it asymptotically minimizes a weighted sum of (alpha)th delay moments. Properties of GLQ and GLD, including an expression for their asymptotic delay distributions, are presented.

Suggested Citation

  • Jan A. Van Mieghem, 2003. "Due-Date Scheduling: Asymptotic Optimality of Generalized Longest Queue and Generalized Largest Delay Rules," Operations Research, INFORMS, vol. 51(1), pages 113-122, February.
  • Handle: RePEc:inm:oropre:v:51:y:2003:i:1:p:113-122
    DOI: 10.1287/opre.51.1.113.12793
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.51.1.113.12793
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.51.1.113.12793?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
    ---><---

    References listed on IDEAS

    as
    1. Jan A. Van Mieghem, 2000. "Price and Service Discrimination in Queuing Systems: Incentive Compatibility of Gc\mu Scheduling," Management Science, INFORMS, vol. 46(9), pages 1249-1267, September.
    2. Paul H. Zipkin, 1995. "Performance Analysis of a Multi-Item Production-Inventory System Under Alternative Policies," Management Science, INFORMS, vol. 41(4), pages 690-703, April.
    3. Lawrence M. Wein, 1991. "Due-Date Setting and Priority Sequencing in a Multiclass M/G/1 Queue," Management Science, INFORMS, vol. 37(7), pages 834-850, July.
    4. Hayriye Ayhan & Tava Lennon Olsen, 2000. "Scheduling of Multi-Class Single-Server Queues Under Nontraditional Performance Measures," Operations Research, INFORMS, vol. 48(3), pages 482-489, June.
    5. David M. Markowitz & Lawrence M. Wein, 2001. "Heavy Traffic Analysis of Dynamic Cyclic Policies: A Unified Treatment of the Single Machine Scheduling Problem," Operations Research, INFORMS, vol. 49(2), pages 246-270, April.
    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. Avishai Mandelbaum & Petar Momčilović, 2017. "Personalized queues: the customer view, via a fluid model of serving least-patient first," Queueing Systems: Theory and Applications, Springer, vol. 87(1), pages 23-53, October.
    2. Petar Momčilović & Amir Motaei, 2018. "QED limits for many-server systems under a priority policy," Queueing Systems: Theory and Applications, Springer, vol. 90(1), pages 125-159, October.
    3. Yichuan Ding & Eric Park & Mahesh Nagarajan & Eric Grafstein, 2019. "Patient Prioritization in Emergency Department Triage Systems: An Empirical Study of the Canadian Triage and Acuity Scale (CTAS)," Manufacturing & Service Operations Management, INFORMS, vol. 21(4), pages 723-741, October.
    4. Dong Li & Kevin D. Glazebrook, 2010. "An approximate dynamic programing approach to the development of heuristics for the scheduling of impatient jobs in a clearing system," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(3), pages 225-236, April.
    5. Junfei Huang & Boaz Carmeli & Avishai Mandelbaum, 2015. "Control of Patient Flow in Emergency Departments, or Multiclass Queues with Deadlines and Feedback," Operations Research, INFORMS, vol. 63(4), pages 892-908, August.
    6. Achal Bassamboo & Ramandeep S. Randhawa & Jan A. Van Mieghem, 2012. "A Little Flexibility Is All You Need: On the Asymptotic Value of Flexible Capacity in Parallel Queuing Systems," Operations Research, INFORMS, vol. 60(6), pages 1423-1435, December.
    7. Rami Atar & Chanit Giat & Nahum Shimkin, 2010. "The c(mu)/(theta) Rule for Many-Server Queues with Abandonment," Operations Research, INFORMS, vol. 58(5), pages 1427-1439, October.
    8. Maglaras, Constantinos & Van Mieghem, Jan A., 2005. "Queueing systems with leadtime constraints: A fluid-model approach for admission and sequencing control," European Journal of Operational Research, Elsevier, vol. 167(1), pages 179-207, November.
    9. Seyed M. Iravani & Mark P. Van Oyen & Katharine T. Sims, 2005. "Structural Flexibility: A New Perspective on the Design of Manufacturing and Service Operations," Management Science, INFORMS, vol. 51(2), pages 151-166, February.
    10. Itai Gurvich & Ward Whitt, 2010. "Service-Level Differentiation in Many-Server Service Systems via Queue-Ratio Routing," Operations Research, INFORMS, vol. 58(2), pages 316-328, April.
    11. Romero-Silva, Rodrigo & Shaaban, Sabry & Marsillac, Erika & Hurtado, Margarita, 2018. "Exploiting the characteristics of serial queues to reduce the mean and variance of flow time using combined priority rules," International Journal of Production Economics, Elsevier, vol. 196(C), pages 211-225.
    12. Wyean Chan & Ger Koole & Pierre L'Ecuyer, 2014. "Dynamic Call Center Routing Policies Using Call Waiting and Agent Idle Times," Manufacturing & Service Operations Management, INFORMS, vol. 16(4), pages 544-560, 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. Weixin Shang & Liming Liu, 2011. "Promised Delivery Time and Capacity Games in Time-Based Competition," Management Science, INFORMS, vol. 57(3), pages 599-610, March.
    2. Barış Ata & Tava Lennon Olsen, 2009. "Near-Optimal Dynamic Lead-Time Quotation and Scheduling Under Convex-Concave Customer Delay Costs," Operations Research, INFORMS, vol. 57(3), pages 753-768, June.
    3. Romero-Silva, Rodrigo & Shaaban, Sabry & Marsillac, Erika & Hurtado, Margarita, 2018. "Exploiting the characteristics of serial queues to reduce the mean and variance of flow time using combined priority rules," International Journal of Production Economics, Elsevier, vol. 196(C), pages 211-225.
    4. Erica L. Plambeck, 2004. "Optimal Leadtime Differentiation via Diffusion Approximations," Operations Research, INFORMS, vol. 52(2), pages 213-228, April.
    5. René Caldentey & Lawrence M. Wein, 2006. "Revenue Management of a Make-to-Stock Queue," Operations Research, INFORMS, vol. 54(5), pages 859-875, October.
    6. Philipp Afèche & Opher Baron & Yoav Kerner, 2013. "Pricing Time-Sensitive Services Based on Realized Performance," Manufacturing & Service Operations Management, INFORMS, vol. 15(3), pages 492-506, July.
    7. Avishai Mandelbaum & Petar Momčilović, 2017. "Personalized queues: the customer view, via a fluid model of serving least-patient first," Queueing Systems: Theory and Applications, Springer, vol. 87(1), pages 23-53, October.
    8. Sami Najafi-Asadolahi & Kristin Fridgeirsdottir, 2014. "Cost-per-Click Pricing for Display Advertising," Manufacturing & Service Operations Management, INFORMS, vol. 16(4), pages 482-497, October.
    9. Ö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.
    10. Bora Kat & Zeynep Avṣar, 2011. "Using aggregate fill rate for dynamic scheduling of multi-class systems," Annals of Operations Research, Springer, vol. 182(1), pages 87-117, January.
    11. Cary Deck & Erik O Kimbrough & Steeve Mongrain, 2014. "Paying for Express Checkout: Competition and Price Discrimination in Multi-Server Queuing Systems," PLOS ONE, Public Library of Science, vol. 9(3), pages 1-13, March.
    12. Yucesan, Enver & de Groote, Xavier, 2000. "Lead times, order release mechanisms, and customer service," European Journal of Operational Research, Elsevier, vol. 120(1), pages 118-130, January.
    13. Menezes, Mozart B.C. & Jalali, Hamed & Lamas, Alejandro, 2021. "One too many: Product proliferation and the financial performance in manufacturing," International Journal of Production Economics, Elsevier, vol. 242(C).
    14. Jain, Apurva, 2007. "Value of capacity pooling in supply chains with heterogeneous customers," European Journal of Operational Research, Elsevier, vol. 177(1), pages 239-260, February.
    15. Tanja Mlinar & Philippe Chevalier, 2016. "Pooling heterogeneous products for manufacturing environments," 4OR, Springer, vol. 14(2), pages 173-200, June.
    16. Lauren Xiaoyuan Lu & Jan A. Van Mieghem & R. Canan Savaskan, 2009. "Incentives for Quality Through Endogenous Routing," Manufacturing & Service Operations Management, INFORMS, vol. 11(2), pages 254-273, July.
    17. Francis De Vericourt & Fikri Karaesmen & Yves Dallery, 2000. "Dynamic Scheduling in a Make-to-Stock System: A Partial Characterization of Optimal Policies," Operations Research, INFORMS, vol. 48(5), pages 811-819, October.
    18. Guodong (Gordon) Gao & Lorin M. Hitt, 2012. "Information Technology and Trademarks: Implications for Product Variety," Management Science, INFORMS, vol. 58(6), pages 1211-1226, June.
    19. Bar{i}c{s} Ata & Jan A. Van Mieghem, 2009. "The Value of Partial Resource Pooling: Should a Service Network Be Integrated or Product-Focused?," Management Science, INFORMS, vol. 55(1), pages 115-131, January.
    20. Yezekael Hayel & Mohamed Ouarraou & Bruno Tuffin, 2007. "Optimal Measurement-based Pricing for an M/M/1 Queue," Networks and Spatial Economics, Springer, vol. 7(2), pages 177-195, 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:inm:oropre:v:51:y:2003:i:1:p:113-122. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.