IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v171y2016i3d10.1007_s10957-016-0923-0.html
   My bibliography  Save this article

On Global Near Optimality of Special Periodic Protocols for Fluid Polling Systems with Setups

Author

Listed:
  • Alexey Matveev

    (Saint Petersburg State University)

  • Varvara Feoktistova

    (Saint Petersburg State University)

  • Ksenia Bolshakova

    (Saint Petersburg State University)

Abstract

We consider a generic deterministic time-invariant fluid model of a polling system, where several buffers (queues) of infinite sizes receive constant rate inflows of jobs from outside the system and share a common source of service (a finite capacity server). The server can serve at most one buffer at a time and has to switch among buffers from time to time; any switch consumes a nonzero switch-over period. With respect to the long-run maximal scaled work in progress (wip) performance metric, near optimality of periodic scheduling and service protocols is established: The optimum can be furnished by such a protocol up to as small error as desired. To prove this, a special class of protocols is introduced, which prescribe to serve any buffer at the maximal rate until its size reduces to a pre-specified percent of its size at the beginning of the visit. It is also shown that the exhaustive policy is optimal for any buffer whose service at the maximal rate implies reduction in the scaled wip.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:joptap:v:171:y:2016:i:3:d:10.1007_s10957-016-0923-0
    DOI: 10.1007/s10957-016-0923-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-016-0923-0
    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/s10957-016-0923-0?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. 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.
    2. Wei-Min Lan & Tava Lennon Olsen, 2006. "Multiproduct Systems with Both Setup Times and Costs: Fluid Bounds and Schedules," Operations Research, INFORMS, vol. 54(3), pages 505-522, June.
    3. Aytug, Haldun & Lawley, Mark A. & McKay, Kenneth & Mohan, Shantha & Uzsoy, Reha, 2005. "Executing production schedules in the face of uncertainties: A review and some future directions," European Journal of Operational Research, Elsevier, vol. 161(1), pages 86-110, February.
    4. 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.
    5. 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. Vladimir Vishnevsky & Olga Semenova, 2021. "Polling Systems and Their Application to Telecommunication Networks," Mathematics, MDPI, vol. 9(2), pages 1-30, January.

    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. 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.
    2. Tava Lennon Olsen, 1999. "A Practical Scheduling Method for Multiclass Production Systems with Setups," Management Science, INFORMS, vol. 45(1), pages 116-130, January.
    3. 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.
    4. Wei-Min Lan & Tava Lennon Olsen, 2006. "Multiproduct Systems with Both Setup Times and Costs: Fluid Bounds and Schedules," Operations Research, INFORMS, vol. 54(3), pages 505-522, June.
    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. Faicel Hnaien & Taha Arbaoui, 2023. "Minimizing the makespan for the two-machine flow shop scheduling problem with random breakdown," Annals of Operations Research, Springer, vol. 328(2), pages 1437-1460, September.
    7. Lamas, Patricio & Goycoolea, Marcos & Pagnoncelli, Bernardo & Newman, Alexandra, 2024. "A target-time-windows technique for project scheduling under uncertainty," European Journal of Operational Research, Elsevier, vol. 314(2), pages 792-806.
    8. Awi Federgruen & Ziv Katalan, 1998. "Determining Production Schedules Under Base-Stock Policies in Single Facility Multi-Item Production Systems," Operations Research, INFORMS, vol. 46(6), pages 883-898, December.
    9. Kangzhou Wang & Shouchang Chen & Zhibin Jiang & Weihua Zhou & Na Geng, 2021. "Capacity Allocation of an Integrated Production and Service System," Production and Operations Management, Production and Operations Management Society, vol. 30(8), pages 2765-2781, August.
    10. Boysen, Nils & Briskorn, Dirk & Schwerdfeger, Stefan, 2019. "Matching supply and demand in a sharing economy: Classification, computational complexity, and application," European Journal of Operational Research, Elsevier, vol. 278(2), pages 578-595.
    11. Han, Xiao-le & Lu, Zhi-qiang & Xi, Li-feng, 2010. "A proactive approach for simultaneous berth and quay crane scheduling problem with stochastic arrival and handling time," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1327-1340, December.
    12. Kampf, M. & Kochel, P., 2006. "Simulation-based sequencing and lot size optimisation for a production-and-inventory system with multiple items," International Journal of Production Economics, Elsevier, vol. 104(1), pages 191-200, November.
    13. 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.
    14. Subhashish Samaddar & Thomas Whalen, 2008. "Improving Performance in Cyclic Production Systems by Using Forced Variable Idle Setup Time," Manufacturing & Service Operations Management, INFORMS, vol. 10(2), pages 173-180, August.
    15. Gang Xuan & Win-Chin Lin & Shuenn-Ren Cheng & Wei-Lun Shen & Po-An Pan & Chih-Ling Kuo & Chin-Chia Wu, 2022. "A Robust Single-Machine Scheduling Problem with Two Job Parameter Scenarios," Mathematics, MDPI, vol. 10(13), pages 1-17, June.
    16. Otis B. Jennings, 2008. "Heavy-Traffic Limits of Queueing Networks with Polling Stations: Brownian Motion in a Wedge," Mathematics of Operations Research, INFORMS, vol. 33(1), pages 12-35, February.
    17. Narjes Sabeghi & Hamed Reza Tareghian, 2020. "Using the generalized maximum covering location model to control a project’s progress," Computational Management Science, Springer, vol. 17(1), pages 1-21, January.
    18. Amir Mokhtari & Jane M. Van Doren, 2019. "An Agent‐Based Model for Pathogen Persistence and Cross‐Contamination Dynamics in a Food Facility," Risk Analysis, John Wiley & Sons, vol. 39(5), pages 992-1021, May.
    19. Black, Gary W. & McKay, Kenneth N. & Morton, Thomas E., 2006. "Aversion scheduling in the presence of risky jobs," European Journal of Operational Research, Elsevier, vol. 175(1), pages 338-361, November.
    20. Lopez de Haro, Santiago & Gershwin, Stanley B. & Rosenfield, Donald B., 2009. "Schedule evaluation in unstable manufacturing environments," International Journal of Production Economics, Elsevier, vol. 121(1), pages 183-194, 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:joptap:v:171:y:2016:i:3:d:10.1007_s10957-016-0923-0. 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.