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

Dynamic Scheduling of a Two-Class Queue with Setups

Author

Listed:
  • Martin I. Reiman

    (Bell Laboratories, Lucent Technologies, Murray Hill, New Jersey)

  • Lawrence M. Wein

    (Massachusetts Institute of Technology, Cambridge, Massachusetts)

Abstract

We analyze two scheduling problems for a queueing system with a single server and two customer classes. Each class has its own renewal arrival process, general service time distribution, and holding cost rate. In the first problem, a setup cost is incurred when the server switches from one class to the other, and the objective is to minimize the long-run expected average cost of holding customers and incurring setups. The setup cost is replaced by a setup time in the second problem, where the objective is to minimize the average holding cost. By assuming that a recently derived heavy traffic principle holds not only for the exhaustive policy but for nonexhaustive policies, we approximate (under standard heavy traffic conditions) the dynamic scheduling problems by diffusion control problems. The diffusion control problem for the setup cost problem is solved exactly, and asymptotics are used to analyze the corresponding setup time problem. Computational results show that the proposed scheduling policies are within several percent of optimal over a broad range of problem parameters.

Suggested Citation

  • Martin I. Reiman & Lawrence M. Wein, 1998. "Dynamic Scheduling of a Two-Class Queue with Setups," Operations Research, INFORMS, vol. 46(4), pages 532-547, August.
    • Handle: RePEc:inm:oropre:v:46:y:1998:i:4:p:532-547
    DOI: 10.1287/opre.46.4.532
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.46.4.532
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.46.4.532?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. J. Michael Harrison & Lawrence M. Wein, 1990. "Scheduling Networks of Queues: Heavy Traffic Analysis of a Two-Station Closed Network," Operations Research, INFORMS, vol. 38(6), pages 1052-1064, December.
    2. E. G. Coffman & A. A. Puhalskii & M. I. Reiman, 1998. "Polling Systems in Heavy Traffic: A Bessel Process Limit," Mathematics of Operations Research, INFORMS, vol. 23(2), pages 257-304, May.
    3. Philippe B. Chevalier & Lawrence M. Wein, 1993. "Scheduling Networks of Queues: Heavy Traffic Analysis of a Multistation Closed Network," Operations Research, INFORMS, vol. 41(4), pages 743-758, August.
    4. Salah E. Elmaghraby, 1978. "The Economic Lot Scheduling Problem (ELSP): Review and Extensions," Management Science, INFORMS, vol. 24(6), pages 587-598, February.
    5. Lawrence M. Wein, 1990. "Optimal Control of a Two-Station Brownian Network," Mathematics of Operations Research, INFORMS, vol. 15(2), pages 215-242, May.
    6. Lawrence M. Wein, 1990. "Scheduling Networks of Queues: Heavy Traffic Analysis of a Two-Station Network with Controllable Inputs," Operations Research, INFORMS, vol. 38(6), pages 1065-1078, December.
    7. Izak Duenyas & Mark P. Van Oyen, 1996. "Heuristic Scheduling of Parallel Heterogeneous Queues with Set-Ups," Management Science, INFORMS, vol. 42(6), pages 814-829, June.
    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. Germs, Remco & Van Foreest, Nicky D., 2011. "Admission policies for the customized stochastic lot scheduling problem with strict due-dates," European Journal of Operational Research, Elsevier, vol. 213(2), pages 375-383, September.
    2. José Niño-Mora, 2008. "A Faster Index Algorithm and a Computational Study for Bandits with Switching Costs," INFORMS Journal on Computing, INFORMS, vol. 20(2), pages 255-269, May.
    3. Alexey Matveev & Varvara Feoktistova & Ksenia Bolshakova, 2016. "On Global Near Optimality of Special Periodic Protocols for Fluid Polling Systems with Setups," Journal of Optimization Theory and Applications, Springer, vol. 171(3), pages 1055-1070, December.
    4. K. D. Glazebrook & R. Minty, 2009. "A Generalized Gittins Index for a Class of Multiarmed Bandits with General Resource Requirements," Mathematics of Operations Research, INFORMS, vol. 34(1), pages 26-44, February.
    5. Sigrún Andradóttir & Hayriye Ayhan & Douglas G. Down, 2001. "Server Assignment Policies for Maximizing the Steady-State Throughput of Finite Queueing Systems," Management Science, INFORMS, vol. 47(10), pages 1421-1439, October.
    6. Tava Lennon Olsen, 1999. "A Practical Scheduling Method for Multiclass Production Systems with Setups," Management Science, INFORMS, vol. 45(1), pages 116-130, January.
    7. 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.
    8. Ramesh Arumugam & Maria Mayorga & Kevin Taaffe, 2009. "Inventory based allocation policies for flexible servers in serial systems," Annals of Operations Research, Springer, vol. 172(1), pages 1-23, November.
    9. Itai Gurvich & Jan A. Van Mieghem, 2015. "Collaboration and Multitasking in Networks: Architectures, Bottlenecks, and Capacity," Manufacturing & Service Operations Management, INFORMS, vol. 17(1), pages 16-33, February.
    10. David M. Markowitz & Martin I. Reiman & Lawrence M. Wein, 2000. "The Stochastic Economic Lot Scheduling Problem: Heavy Traffic Analysis of Dynamic Cyclic Policies," Operations Research, INFORMS, vol. 48(1), pages 136-154, February.
    11. James R. Bradley, 2004. "A Brownian Approximation of a Production-Inventory System with a Manufacturer That Subcontracts," Operations Research, INFORMS, vol. 52(5), pages 765-784, 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. Bertsimas, Dimitris & Paschalidis, Ioannis Ch. & Tsitsiklis, John N., 1992. "Optimization of multiclass queuing networks : polyhedral and nonlinear characterizations of achievable performance," Working papers 3509-92., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    2. Gregory Dobson & Tolga Tezcan & Vera Tilson, 2013. "Optimal Workflow Decisions for Investigators in Systems with Interruptions," Management Science, INFORMS, vol. 59(5), pages 1125-1141, May.
    3. Wendell G. Gilland, 2001. "Effective Sequencing Rules for Closed Manufacturing Networks," Operations Research, INFORMS, vol. 49(5), pages 759-770, October.
    4. 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.
    5. Melanie Rubino & Barış Ata, 2009. "Dynamic Control of a Make-to-Order, Parallel-Server System with Cancellations," Operations Research, INFORMS, vol. 57(1), pages 94-108, February.
    6. Narahari, Y. & Khan, L. M., 1998. "Asymptotic loss of priority scheduling policies in closed re-entrant lines: A computational study," European Journal of Operational Research, Elsevier, vol. 110(3), pages 585-596, November.
    7. Barış Ata, 2006. "Dynamic Control of a Multiclass Queue with Thin Arrival Streams," Operations Research, INFORMS, vol. 54(5), pages 876-892, October.
    8. S. P. Sethi & H. Yan & H. Zhang & Q. Zhang, 2002. "Optimal and Hierarchical Controls in Dynamic Stochastic Manufacturing Systems: A Survey," Manufacturing & Service Operations Management, INFORMS, vol. 4(2), pages 133-170.
    9. Santiago R. Balseiro & David B. Brown & Chen Chen, 2021. "Dynamic Pricing of Relocating Resources in Large Networks," Management Science, INFORMS, vol. 67(7), pages 4075-4094, July.
    10. David M. Markowitz & Martin I. Reiman & Lawrence M. Wein, 2000. "The Stochastic Economic Lot Scheduling Problem: Heavy Traffic Analysis of Dynamic Cyclic Policies," Operations Research, INFORMS, vol. 48(1), pages 136-154, February.
    11. Suresh Chand & Ting Zeng, 2001. "A Comparison of U-Line and Straight-Line Performances Under Stochastic Task Times," Manufacturing & Service Operations Management, INFORMS, vol. 3(2), pages 138-150, January.
    12. Amy R. Ward & Sunil Kumar, 2008. "Asymptotically Optimal Admission Control of a Queue with Impatient Customers," Mathematics of Operations Research, INFORMS, vol. 33(1), pages 167-202, February.
    13. Erica L. Plambeck, 2008. "Asymptotically Optimal Control for an Assemble-to-Order System with Capacitated Component Production and Fixed Transport Costs," Operations Research, INFORMS, vol. 56(5), pages 1158-1171, October.
    14. Lee, Heeseok, 1995. "Assignment of a job load in a distributed system: A multicriteria design method," European Journal of Operational Research, Elsevier, vol. 87(2), pages 274-283, December.
    15. Paul Glasserman & Yashan Wang, 1999. "Fill-Rate Bottlenecks in Production-Inventory Networks," Manufacturing & Service Operations Management, INFORMS, vol. 1(1), pages 62-76.
    16. van Ackere, Ann, 1996. "The management of congestion," European Journal of Operational Research, Elsevier, vol. 89(2), pages 223-225, March.
    17. Hong Chen & Xinyang Shen & David D. Yao, 2002. "Brownian Approximations of Multiclass Open-Queueing Networks," Operations Research, INFORMS, vol. 50(6), pages 1032-1049, December.
    18. Dieter Armbruster & Daniel E. Marthaler & Christian Ringhofer & Karl Kempf & Tae-Chang Jo, 2006. "A Continuum Model for a Re-entrant Factory," Operations Research, INFORMS, vol. 54(5), pages 933-950, October.
    19. Barιş Ata & Deishin Lee & Erkut Sönmez, 2019. "Dynamic Volunteer Staffing in Multicrop Gleaning Operations," Operations Research, INFORMS, vol. 67(2), pages 295-314, March.
    20. Ick-Hyun Nam, 2001. "Dynamic Scheduling for a Flexible Processing Network," Operations Research, INFORMS, vol. 49(2), pages 305-315, April.

    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:46:y:1998:i:4:p:532-547. 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.