Optimal insertion of customers with waiting time targets. (English) Zbl 1458.90371
Summary: The insertion of randomly-arriving high-priority customers (HCs) into existing queues leads to longer waiting time of regular or scheduled customers. However, given their different levels of priority, not all HCs need to be served immediately. To reduce the waiting time for regular customers without affecting the service quality for HCs, this paper addresses the optimal insertion problem of HCs by considering their waiting time targets assigned based on their levels of priority. A finite-horizon Markov decision process model is proposed to minimize the total waiting cost incurred by both regular customers and HCs. The marginal waiting penalty is constant for regular customers and non-decreasing for HCs. Several properties are observed: the optimal control policy is proved to be a state-dependent threshold policy; the marginal effect of each state variable on the optimal action is bounded by 1; and, in some meaningful cases, the threshold proves to be state-independent. Based on these properties, several heuristic policies are proposed to solve large-size problems. Numerical experiments are performed to validate the structure of the optimal control policies and compare the performances of the heuristic policies. These results imply that the optimal control policy significantly outperforms the traditional HC-first policy. The best heuristic policy, characterized by a threshold policy derived through policy iteration, performs within 0.44% of an optimal policy for most cases, which offers insights into the near-optimal control for large-size problems.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C40 | Markov and semi-Markov decision processes |
Keywords:
real-time scheduling; priority customers; Markov decision process; waiting time target; heuristic policiesReferences:
| [1] | Ahmadi-Javid, A.; Jalali, Z.; Klassen, K. J., Outpatient appointment systems in healthcare: a review of optimization studies, Eur. J. Oper. Res., 258, 1, 3-34 (2016) · Zbl 1380.90106 |
| [2] | Ayvaz, N.; Huh, W. T., Allocation of hospital capacity to multiple types of patients, J. Revenue Pricing Manage., 9, 5, 386-398 (2010) |
| [3] | Cardoen, B.; Demeulemeester, E.; Belien, J., Operating room planning and scheduling: a literature review, Eur. J. Oper. Res., 201, 3, 921-932 (2010) · Zbl 1175.90160 |
| [4] | Cayirli, T.; Veral, E., Outpatient scheduling in health care: a review of literature, Prod. Operations Manage., 12, 4, 519-549 (2003) |
| [5] | Christ, M.; Grossmann, F.; Winter, D.; Bingisser, R.; Platz, E., Modern triage in the emergency department, Deutsches Rzteblatt International, 107, 50, 892-898 (2010) |
| [6] | Dugas, A. F.; Kirsch, T. D.; Toerper, M.; Korley, F.; Yenokyan, G.; France, D.; Hager, D.; Levin, S., An electronic emergency triage system to improve patient distribution by critical outcomes, J. Emerg. Med., 50, 6, 910-918 (2016) |
| [7] | Farrohknia, N.; Castrn, M.; Ehrenberg, A.; Lind, L.; Oredsson, S.; Jonsson, H.; Asplund, K.; Goransson, K. E., Emergency department triage scales and their components: a systematic review of the scientific evidence, Scandinavian J. Trauma Resuscitation Emergency Med., 19, 1, 1-13 (2011) |
| [8] | Geng, N.; Xie, X., Optimal dynamic outpatient scheduling for a diagnostic facility with two waiting time targets, IEEE Trans. Autom. Control, 61, 12, 3725-3739 (2016) · Zbl 1359.90042 |
| [9] | Gentile, S.; Vignally, P.; Durand, A. C.; Gainotti, S.; Sambuc, R.; Gerbeaux, P., Nonurgent patients in the emergency department? a french formula to prevent misuse, Bmc Health Services Res., 10, 1, 1-6 (2010) |
| [10] | Gerchak, Y.; Gupta, D.; Henig, M., Reservation planning for elective surgery under uncertain demand for emergency surgery, Manage. Sci., 42, 3, 321-334 (1996) · Zbl 0884.90106 |
| [11] | Gocgun, Y.; Bresnahan, B. W.; Ghate, A.; Gunn, M. L., A markov decision process approach to multi-category patient scheduling in a diagnostic facility, Artif. Intell. Med., 53, 2, 73-81 (2011) |
| [12] | Gocgun, Y.; Puterman, M. L., Dynamic scheduling with due dates and time windows: an application to chemotherapy patient appointment booking, Health Care Manage. Sci., 17, 1, 60-76 (2014) |
| [13] | Green, L. V.; Savin, S.; Wang, B., Managing patient service in a diagnostic medical facility, Operat.. Res., 54, 1, 11-25 (2006) · Zbl 1167.90562 |
| [14] | Gupta, D.; Denton, B., Appointment scheduling in health care: challenges and opportunities, IIE Trans., 40, 9, 800-819 (2008) |
| [15] | Huang, J.; Carmeli, B.; Mandelbaum, A., Control of patient flow in emergency departments, or multiclass queues with deadlines and feedback, Operat. Res., 63, 4, 892-908 (2015) · Zbl 1329.90038 |
| [16] | Huh, W. T.; Liu, N.; Vananh, T., Multiresource allocation scheduling in dynamic environments, Manuf. Service Operat. Manage., 15, 2, 280-291 (2013) |
| [17] | Kolisch, R.; Sickinger, S., Providing radiology health care services to stochastic demand of different customer classes, OR Spectrum, 30, 2, 375-395 (2008) · Zbl 1170.90403 |
| [18] | Kortbeek, N.; Zonderland, M. E.; Braaksma, A.; Vliegen, I. M.H.; Boucherie, R. J.; Litvak, N.; Hans, E. W., Designing cyclic appointment schedules for outpatient clinics with scheduled and unscheduled patient arrivals, Performance Eval., 80, C, 5-26 (2014) |
| [19] | Leo, G.; Lodi, A.; Tubertini, P.; Martino, M. D., Emergency department management in lazio, italy, Omega, 58, 128-138 (2016) |
| [20] | Li, Q.; Yu, P., Multimodularity and its applications in three stochastic dynamic inventory problems, Manuf. Service Operat. Manage., 16, 3, 455-463 (2014) |
| [21] | Magerlein, J. M.; Martin, J. B., Surgical demand scheduling: a review, Health Serv. Res., 13, 4, 418-433 (1978) |
| [22] | Min, D.; Yih, Y., Managing a patient waiting list with time-dependent priority and adverse events, RAIRO - Operat. Res., 48, 1, 53-74 (2014) · Zbl 1288.90121 |
| [23] | Murota, K., 2003. Discrete Convex Analysis: Monographs on Discrete Mathematics and Applications 10. Society for Industrial and Applied Mathematics. · Zbl 1029.90055 |
| [24] | Patrick, J.; Puterman, M. L.; Queyranne, M., Dynamic multipriority patient scheduling for a diagnostic resource, Operat. Res., 56, 6, 1507-1525 (2008) · Zbl 1167.90675 |
| [25] | Powell, W. B., Approximate Dynamic Programming: Solving the Curses of Dimensionality (2011), John Wiley & Sons: John Wiley & Sons Princeton, New Jersey · Zbl 1242.90002 |
| [26] | Qiu, Y.; Song, J.; Liu, Z., Real time access control of patient service in the pediatrics department, (IEEE International Conference on Automation Science and Engineering (2015)), 734-739 |
| [27] | Schutz, H.; Kolisch, R., Approximate dynamic programming for capacity allocation in the service industry, Eur. J. Oper. Res., 218, 1, 239-250 (2012) · Zbl 1244.90238 |
| [28] | Topkis, D. M., Supermodularity and Complementarity (1998), Princeton University Press: Princeton University Press Princeton, New Jersey |
| [29] | Van Mieghem, J. A., Dynamic scheduling with convex delay costs: the generalized c \(\mu\) rule, Ann. Appl. Prob., 5, 3, 809-833 (1995) · Zbl 0843.90047 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
