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

Scheduling Arrivals to a Stochastic Service Delivery System Using Copositive Cones

Author

Listed:
  • Qingxia Kong

    (School of Business, Universidad Adolfo Ibáñez, Santiago, Chile)

  • Chung-Yee Lee

    (Department of Industrial Engineering and Logistics Management, Hong Kong University of Science and Technology, Hong Kong)

  • Chung-Piaw Teo

    (Department of Decision Sciences, National University of Singapore, Singapore, Republic of Singapore)

  • Zhichao Zheng

    (Department of Decision Sciences, National University of Singapore, Singapore, Republic of Singapore)

Abstract

In this paper we investigate a stochastic appointment-scheduling problem in an outpatient clinic with a single doctor. The number of patients and their sequence of arrivals are fixed, and the scheduling problem is to determine an appointment time for each patient. The service durations of the patients are stochastic, and only the mean and covariance estimates are known. We do not assume any exact distributional form of the service durations, and we solve for distributionally robust schedules that minimize the expectation of the weighted sum of patients' waiting time and the doctor's overtime. We formulate this scheduling problem as a convex conic optimization problem with a tractable semidefinite relaxation. Our model can be extended to handle additional support constraints of the service durations. Using the primal--dual optimality conditions, we prove several interesting structural properties of the optimal schedules. We develop an efficient semidefinite relaxation of the conic program and show that we can still obtain near-optimal solutions on benchmark instances in the existing literature. We apply our approach to develop a practical appointment schedule at an eye clinic that can significantly improve the efficiency of the appointment system in the clinic, compared to an existing schedule.

Suggested Citation

  • Qingxia Kong & Chung-Yee Lee & Chung-Piaw Teo & Zhichao Zheng, 2013. "Scheduling Arrivals to a Stochastic Service Delivery System Using Copositive Cones," Operations Research, INFORMS, vol. 61(3), pages 711-726, June.
    • Handle: RePEc:inm:oropre:v:61:y:2013:i:3:p:711-726
    DOI: 10.1287/opre.2013.1158
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2013.1158
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2013.1158?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. Wang, P. Patrick, 1999. "Sequencing and scheduling N customers for a stochastic server," European Journal of Operational Research, Elsevier, vol. 119(3), pages 729-738, December.
    2. Guido Kaandorp & Ger Koole, 2007. "Optimal outpatient appointment scheduling," Health Care Management Science, Springer, vol. 10(3), pages 217-229, September.
    3. Vissers, J. & Wijngaard, J., 1979. "The outpatient appointment system: Design of a simulation study," European Journal of Operational Research, Elsevier, vol. 3(6), pages 459-463, November.
    4. Chrwan-Jyh Ho & Hon-Shiang Lau, 1992. "Minimizing Total Cost in Scheduling Outpatient Appointments," Management Science, INFORMS, vol. 38(12), pages 1750-1764, December.
    5. Mehmet A. Begen & Retsef Levi & Maurice Queyranne, 2012. "Technical Note---A Sampling-Based Approach to Appointment Scheduling," Operations Research, INFORMS, vol. 60(3), pages 675-681, June.
    6. Mehmet A. Begen & Maurice Queyranne, 2011. "Appointment Scheduling with Discrete Random Durations," Mathematics of Operations Research, INFORMS, vol. 36(2), pages 240-257, May.
    7. A. Soriano, 1966. "Comparison of Two Scheduling Systems," Operations Research, INFORMS, vol. 14(3), pages 388-397, June.
    8. Brian T. Denton & Andrew J. Miller & Hari J. Balasubramanian & Todd R. Huschka, 2010. "Optimal Allocation of Surgery Blocks to Operating Rooms Under Uncertainty," Operations Research, INFORMS, vol. 58(4-part-1), pages 802-816, August.
    9. Lawrence W. Robinson & Rachel R. Chen, 2010. "A Comparison of Traditional and Open-Access Policies for Appointment Scheduling," Manufacturing & Service Operations Management, INFORMS, vol. 12(2), pages 330-346, June.
    10. P. Patrick Wang, 1993. "Static and dynamic scheduling of customer arrivals to a single‐server system," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(3), pages 345-360, April.
    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. Soltani, Mohamad & Samorani, Michele & Kolfal, Bora, 2019. "Appointment scheduling with multiple providers and stochastic service times," European Journal of Operational Research, Elsevier, vol. 277(2), pages 667-683.
    2. Ruiwei Jiang & Siqian Shen & Yiling Zhang, 2017. "Integer Programming Approaches for Appointment Scheduling with Random No-Shows and Service Durations," Operations Research, INFORMS, vol. 65(6), pages 1638-1656, December.
    3. Shenghai Zhou & Yichuan Ding & Woonghee Tim Huh & Guohua Wan, 2021. "Constant Job‐Allowance Policies for Appointment Scheduling: Performance Bounds and Numerical Analysis," Production and Operations Management, Production and Operations Management Society, vol. 30(7), pages 2211-2231, July.
    4. Shehadeh, Karmel S. & Cohn, Amy E.M. & Epelman, Marina A., 2019. "Analysis of models for the Stochastic Outpatient Procedure Scheduling Problem," European Journal of Operational Research, Elsevier, vol. 279(3), pages 721-731.
    5. Tugba Cayirli & Kum Khiong Yang & Ser Aik Quek, 2012. "A Universal Appointment Rule in the Presence of No‐Shows and Walk‐Ins," Production and Operations Management, Production and Operations Management Society, vol. 21(4), pages 682-697, July.
    6. Ho-Yin Mak & Ying Rong & Jiawei Zhang, 2014. "Sequencing Appointments for Service Systems Using Inventory Approximations," Manufacturing & Service Operations Management, INFORMS, vol. 16(2), pages 251-262, May.
    7. Pan, Xingwei & Geng, Na & Xie, Xiaolan, 2021. "Appointment scheduling and real-time sequencing strategies for patient unpunctuality," European Journal of Operational Research, Elsevier, vol. 295(1), pages 246-260.
    8. Kemper, Benjamin & Klaassen, Chris A.J. & Mandjes, Michel, 2014. "Optimized appointment scheduling," European Journal of Operational Research, Elsevier, vol. 239(1), pages 243-255.
    9. Wen-Ya Wang & Diwakar Gupta, 2011. "Adaptive Appointment Systems with Patient Preferences," Manufacturing & Service Operations Management, INFORMS, vol. 13(3), pages 373-389, July.
    10. Creemers, Stefan & Lambrecht, Marc R. & Beliën, Jeroen & Van den Broeke, Maud, 2021. "Evaluation of appointment scheduling rules: A multi-performance measurement approach," Omega, Elsevier, vol. 100(C).
    11. Pan, Xingwei & Geng, Na & Xie, Xiaolan & Wen, Jing, 2020. "Managing appointments with waiting time targets and random walk-ins," Omega, Elsevier, vol. 95(C).
    12. van Eekelen, Wouter, 2023. "Distributionally robust views on queues and related stochastic models," Other publications TiSEM 9b99fc05-9d68-48eb-ae8c-9, Tilburg University, School of Economics and Management.
    13. Paola Cappanera & Filippo Visintin & Carlo Banditori & Daniele Feo, 2019. "Evaluating the long-term effects of appointment scheduling policies in a magnetic resonance imaging setting," Flexible Services and Manufacturing Journal, Springer, vol. 31(1), pages 212-254, March.
    14. Kuiper, Alex & de Mast, Jeroen & Mandjes, Michel, 2021. "The problem of appointment scheduling in outpatient clinics: A multiple case study of clinical practice," Omega, Elsevier, vol. 98(C).
    15. Christos Zacharias & Tallys Yunes, 2020. "Multimodularity in the Stochastic Appointment Scheduling Problem with Discrete Arrival Epochs," Management Science, INFORMS, vol. 66(2), pages 744-763, February.
    16. Ahmadi-Javid, Amir & Jalali, Zahra & Klassen, Kenneth J, 2017. "Outpatient appointment systems in healthcare: A review of optimization studies," European Journal of Operational Research, Elsevier, vol. 258(1), pages 3-34.
    17. Ho-Yin Mak & Ying Rong & Jiawei Zhang, 2015. "Appointment Scheduling with Limited Distributional Information," Management Science, INFORMS, vol. 61(2), pages 316-334, February.
    18. Lawrence W. Robinson & Rachel R. Chen, 2010. "A Comparison of Traditional and Open-Access Policies for Appointment Scheduling," Manufacturing & Service Operations Management, INFORMS, vol. 12(2), pages 330-346, June.
    19. Oualid Jouini & Saif Benjaafar & Bingnan Lu & Siqiao Li & Benjamin Legros, 2022. "Appointment-driven queueing systems with non-punctual customers," Queueing Systems: Theory and Applications, Springer, vol. 101(1), pages 1-56, June.
    20. S. Ayca Erdogan & Brian Denton, 2013. "Dynamic Appointment Scheduling of a Stochastic Server with Uncertain Demand," INFORMS Journal on Computing, INFORMS, vol. 25(1), pages 116-132, February.

    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:61:y:2013:i:3:p:711-726. 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.