Scheduling Arrivals to a Stochastic Service Delivery System Using Copositive Cones

Qingxia Kong (), Chung-Yee Lee (), Chung-Piaw Teo () and Zhichao Zheng ()
Additional contact information
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

Operations Research, 2013, vol. 61, issue 3, 711-726

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.

Keywords: appointment scheduling; copositive programming; semidefinite programming; network flow (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (52)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2013.1158 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:3:p:711-726

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().