IDEAS home Printed from https://ideas.repec.org/p/upf/upfgen/276.html
   My bibliography  Save this paper

On the throughput-WIP trade-off in queueing systems, diminishing returns and the threshold property: A linear programming approach

Author

Listed:
  • José Niño-Mora

Abstract

We present a new unifying framework for investigating throughput-WIP (Work-in-Process) optimal control problems in queueing systems, based on reformulating them as linear programming (LP) problems with special structure: We show that if a throughput-WIP performance pair in a stochastic system satisfies the Threshold Property we introduce in this paper, then we can reformulate the problem of optimizing a linear objective of throughput-WIP performance as a (semi-infinite) LP problem over a polygon with special structure (a threshold polygon). The strong structural properties of such polygones explain the optimality of threshold policies for optimizing linear performance objectives: their vertices correspond to the performance pairs of threshold policies. We analyze in this framework the versatile input-output queueing intensity control model introduced by Chen and Yao (1990), obtaining a variety of new results, including (a) an exact reformulation of the control problem as an LP problem over a threshold polygon; (b) an analytical characterization of the Min WIP function (giving the minimum WIP level required to attain a target throughput level); (c) an LP Value Decomposition Theorem that relates the objective value under an arbitrary policy with that of a given threshold policy (thus revealing the LP interpretation of Chen and Yao's optimality conditions); (d) diminishing returns and invariance properties of throughput-WIP performance, which underlie threshold optimality; (e) a unified treatment of the time-discounted and time-average cases.

Suggested Citation

  • José Niño-Mora, 1998. "On the throughput-WIP trade-off in queueing systems, diminishing returns and the threshold property: A linear programming approach," Economics Working Papers 276, Department of Economics and Business, Universitat Pompeu Fabra.
    • Handle: RePEc:upf:upfgen:276
    as

    Download full text from publisher

    File URL: https://econ-papers.upf.edu/papers/276.pdf
    File Function: Whole Paper
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Paul Glasserman & David D. Yao, 1994. "Monotone Optimal Control of Permutable GSMPs," Mathematics of Operations Research, INFORMS, vol. 19(2), pages 449-476, May.
    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. Kim, Eungab, 2005. "Optimal inventory replenishment policy for a queueing system with finite waiting room capacity," European Journal of Operational Research, Elsevier, vol. 161(1), pages 256-274, February.
    2. Kim, Eungab, 2004. "Stochastic vendor managed replenishment with demand dependent shipment," European Journal of Operational Research, Elsevier, vol. 152(3), pages 723-744, February.
    3. Albert Y. Ha, 1997. "Stock‐rationing policy for a make‐to‐stock production system with two priority classes and backordering," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(5), pages 457-472, August.
    4. Zhuang, Weifen & Li, Michael Z.F., 2012. "Monotone optimal control for a class of Markov decision processes," European Journal of Operational Research, Elsevier, vol. 217(2), pages 342-350.
    5. Boray Huang & Seyed M. R. Iravani, 2008. "Technical Note---A Make-to-Stock System with Multiple Customer Classes and Batch Ordering," Operations Research, INFORMS, vol. 56(5), pages 1312-1320, October.
    6. Eungab Kim & Kaphoon Lee & Suk-Ho Kang, 2006. "Optimal purchasing policy in a two-component assembly system with different purchasing contracts for each component," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 63(2), pages 301-327, May.
    7. Song-Hee Kim & Carri W. Chan & Marcelo Olivares & Gabriel Escobar, 2015. "ICU Admission Control: An Empirical Study of Capacity Allocation and Its Implication for Patient Outcomes," Management Science, INFORMS, vol. 61(1), pages 19-38, January.
    8. Xin Chen & Menglong Li, 2021. "Discrete Convex Analysis and Its Applications in Operations: A Survey," Production and Operations Management, Production and Operations Management Society, vol. 30(6), pages 1904-1926, June.
    9. Scott Carr & Izak Duenyas, 2000. "Optimal Admission Control and Sequencing in a Make-to-Stock/Make-to-Order Production System," Operations Research, INFORMS, vol. 48(5), pages 709-720, October.
    10. Qing Li & Peiwen Yu, 2014. "Multimodularity and Its Applications in Three Stochastic Dynamic Inventory Problems," Manufacturing & Service Operations Management, INFORMS, vol. 16(3), pages 455-463, July.
    11. Tong Wang & Xiting Gong & Sean X. Zhou, 2017. "Dynamic Inventory Management with Total Minimum Order Commitments and Two Supply Options," Operations Research, INFORMS, vol. 65(5), pages 1285-1302, October.
    12. Ang, Marcus & Song, Jing-Sheng & Wang, Mingzheng & Zhang, Hanqin, 2013. "On properties of discrete (r, q) and (s, T) inventory systems," European Journal of Operational Research, Elsevier, vol. 229(1), pages 95-105.
    13. Eitan Altman & Bruno Gaujal & Arie Hordijk, 2000. "Multimodularity, Convexity, and Optimization Properties," Mathematics of Operations Research, INFORMS, vol. 25(2), pages 324-347, May.

    More about this item

    Keywords

    Throughput-WIP (Work-in-Process) optimal queueing control; threshold optimality; achievable performance region;
    All these keywords.

    JEL classification:

    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis
    • C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques
    • M11 - Business Administration and Business Economics; Marketing; Accounting; Personnel Economics - - Business Administration - - - Production Management

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:upf:upfgen:276. 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: the person in charge (email available below). General contact details of provider: http://www.econ.upf.edu/ .

    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.