An efficient centralized master echocardiography schedule in a distributed hospital/clinic network

Document Type : Research Paper


1 Faculty of Industrial and Systems Engineering,Tarbiat Modares University, Tehran, Iran.

2 MD, FSCAI, Associated Professor, Interventional Cardiologist, Department of Cardiology, Tehran Heart Centre, Tehran University of Medical Sciences, Tehran, Iran.


Appointment scheduling systems are applied in a broad variety of healthcare environments to reduce costs and increase quality of services. This study is concerned with the problem of appointment scheduling in a distributed multi-hospital network of echocardiography departments. In this paper, a centralized master schedule is presented to maximize profit margin through maximizing the number of performed echoes and minimizing overtime. Developing such a schedule requires handling shift scheduling and capacity allocation problems simultaneously. Based on real-world settings, a mixed integer linear programming model is proposed for the research problem. Since this model requires a large amount of time and memory to provide good solutions, and fails to find feasible solutions for most of the test problems, two metaheuristics are proposed with different approaches. The first one is combined variable neighborhood search with simulated annealing (VNS-SA) and the second one is hybrid particle swarm optimization (HPSO). Also two lower bounding techniques based on patients’ assignment ( ) and specialists’ assignment ( ) are presented. Then the efficiency of the proposed model and algorithms is evaluated using a set of practical-sized test problems. The results showed that VNS-SA is capable of providing high quality solutions in reasonable amount of time for all test problems and outperforms HPSO. Furthermore, the superiority of  over  and the lower bound provided by the mathematical model was shown from both the quality and computational time points of view. Finally, some managerial notes and suggestions for extension are presented.


Main Subjects

about Tehran Heart Center. (2017).   Retrieved from
Ahmadi-Javid, A., Jalali, Z., & Klassen, K. J. (2017). Outpatient appointment systems in healthcare: A review of optimization studies. European Journal of Operational Research, 258(1), 3-34.
Aringhieri, R., Landa, P., Soriano, P., Tànfani, E., & Testi, A. (2015). A two-level metaheuristic for the operating room scheduling and assignment problem. Computers & Operations Research, 54, 21-34.
Bailey, N. T. (1952). A study of queues and appointment systems in hospital out-patient departments, with special reference to waiting-times. Journal of the Royal Statistical Society. Series B (Methodological), 185-199.
Bakker, M., & Tsui, K.-L. (2017). Dynamic resource allocation for efficient patient scheduling: a data-driven approach. Journal of Systems Science and Systems Engineering, 26(4), 448-462.
Bakshi, S. (2013). Business process re-engineering a cardiology department. World hospitals and health services: the official journal of the International Hospital Federation, 50(2), 40-45.
Bettinelli, A., Cacchiani, V., & Malaguti, E. (2017). A branch-and-bound algorithm for the knapsack problem with conflict graph. INFORMS Journal on Computing, 29(3), 457-473.
Brech, C.-H., Ernst, A., & Kolisch, R. (2019). Scheduling medical residents’ training at university hospitals. European Journal of Operational Research, 274(1), 253-266.
Cabell, C. H., Trichon, B. H., Velazquez, E. J., Dumesnil, J. G., Anstrom, K. J., Ryan, T., Miller, A. B., Belkin, R. N., Cropp, A. B., & O'connor, C. M. (2004). Importance of echocardiography in patients with severe nonischemic heart failure: the second Prospective Randomized Amlodipine Survival Evaluation (PRAISE-2) echocardiographic study. American heart journal, 147(1), 151-157.
Castro, E., & Petrovic, S. (2012). Combined mathematical programming and heuristics for a radiotherapy pre-treatment scheduling problem. Journal of Scheduling, 15(3), 333-346.
Cayirli, T., & Veral, E. (2003). Outpatient scheduling in health care: a review of literature. Production and operations management, 12(4), 519-549.
Gandhi, R. (2013). Increasing the Daily Throughput of Echocardiogram Patients using Discrete Event Simulation. (Master of Health Science), University of Toronto.  
Geronimo, R. (2017). Improving Stress Echocardiogram Access for Patients with Low-Risk Chest Pain in the Emergency Department Clinical Decision Unit. (Master's thesis), University of San Francisco.  
Hamid, M., Barzinpour, F., Hamid, M., & Mirzamohammadi, S. (2018). A multi-objective mathematical model for nurse scheduling problem with hybrid DEA and augmented ε-constraint method: A case study. Journal of Industrial and Systems Engineering, 11(Special issue: 14th International Industrial Engineering Conference), 98-108.
Hamid, M., Nasiri, M. M., Werner, F., Sheikhahmadi, F., & Zhalechian, M. (2019). Operating room scheduling by considering the decision-making styles of surgical team members: a comprehensive approach. Computers & Operations Research, 108, 166-181.
Heath, S. (2017). Centralized Appointment Scheduling Aids Patient Experience.   Retrieved from
Hong, Y.-C., Cohn, A., Epelman, M. A., & Alpert, A. (2018). Creating resident shift schedules under multiple objectives by generating and evaluating the Pareto frontier. Operations Research for Health Care,. doi:
Hulshof, P. J., Kortbeek, N., Boucherie, R. J., Hans, E. W., & Bakker, P. J. (2012). Taxonomic classification of planning decisions in health care: a structured review of the state of the art in OR/MS. Health systems, 1(2), 129-175.
Katsi, V. K., Vrachatis, D. A., Politi, A., Papageorgiou, M., Koumoulidis, A., Vlasseros, I., Vavuranakis, M., Tousoulis, D., Stefanadis, C., & Kallikazaros, I. (2014). Cardiac echo-lab productivity in times of economic austerity. SpringerPlus, 3(1), 703.
Kennedy, j., & Eberhart, R. (1995). Particle swarm optimization. Paper presented at the Proceeding IEEE Inter Conference on Neural Networks, Perth, Australia, Piscat-away.
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simmulated annealing. science, 220(4598), 671-680.
Klassen, K. J., & Yoogalingam, R. (2019). Appointment scheduling in multi-stage outpatient clinics. Health Care Management Science, 22(2), 229-244.
LaGanga, L. R., & Lawrence, S. R. (2012). Appointment overbooking in health care clinics to improve patient service and clinic performance. Production and operations management, 21(5), 874-888.
Munt, B., O’Neill, B., Koilpillai, C., Gin, K., Jue, J., & Honos, G. (2006). Treating the right patient at the right time: Access to echocardiography in Canada. Canadian Journal of Cardiology, 22(12), 1029-1033.
Murray, M., & Berwick, D. M. (2003). Advanced access: reducing waiting and delays in primary care. Jama, 289(8), 1035-1040.
Nazif, H. (2018). Operating Room Surgery Scheduling with Fuzzy Surgery Durations Using a Metaheuristic Approach. Advances in Operations Research, 2018. doi:
Nguyen, T. B. T., Sivakumar, A. I., & Graves, S. C. (2015). A network flow approach for tactical resource planning in outpatient clinics. Health Care Management Science, 18(2), 124-136.
Parallon. (2013). Using Centralized Scheduling to Improve Performance.   Retrieved from
Pena, S. M., & Lawrence, N. (2017). Analysis of wait times and impact of real-time surveys on patient satisfaction. Dermatologic Surgery, 43(10), 1288-1291.
Penn, M., Potts, C. N., & Harper, P. R. (2017). Multiple criteria mixed-integer programming for incorporating multiple factors into the development of master operating theatre timetables. European Journal of Operational Research, 262(1), 194-206.
Poli, R., Kennedy, J., & Blackwell, T. (2007). Particle swarm optimization. Swarm intelligence, 1(1), 33-57.
Rabani, M., & Niyazi, M. (2017). Solving a nurse rostering problem considering nurses preferences by graph theory approach. Journal of Industrial and Systems Engineering, 10(special issue on scheduling), 38-57.
Reliasmedia. (2014). Centralized scheduling provides many benefits.   Retrieved from
Roshanaei, V., Luong, C., Aleman, D. M., & Urbach, D. (2017). Propagating logic-based Benders’ decomposition approaches for distributed operating room scheduling. European Journal of Operational Research, 257(2), 439-455.
Santibáñez, P., Begen, M., & Atkins, D. (2007). Surgical block scheduling in a system of hospitals: an application to resource and wait list management in a British Columbia health authority. Health Care Management Science, 10(3), 269-282.
Saure, A., Patrick, J., Tyldesley, S., & Puterman, M. L. (2012). Dynamic multi-appointment patient scheduling for radiation therapy. European Journal of Operational Research, 223(2), 573-584.
Scisolutions. (2017). centralized patient access: a checklist for success. Retrieved from
Smalley, H. K., & Keskinocak, P. (2016). Automated medical resident rotation and shift scheduling to ensure quality resident education and patient care. Health Care Management Science, 19(1), 66-88.
Taguchi, G. (1986). Introduction to quality engineering: designing quality into products and processes.
Tohidi, M., Kazemi Zanjani, M., & Contreras, I. (2019). Integrated physician and clinic scheduling in ambulatory polyclinics. Journal of the Operational Research Society, 70(2), 177-191.
Trang, A., Kampangkaew, J., Fernandes, R., Tiwana, J., Misra, A., Hamzeh, I., Blaustein, A., Aguilar, D., Shah, T., & Ballantyne, C. (2019). Understanding by General Providers of the Echocardiogram Report. The American journal of cardiology, 124(2), 296-302.
Tsai, P.-F. J., & Teng, G.-Y. (2014). A stochastic appointment scheduling system on multiple resources with dynamic call-in sequence and patient no-shows for an outpatient clinic. European Journal of Operational Research, 239(2), 427-436.
Vali Siar, M., Gholami, S., & Ramezanian, R. (2017). Multi-period and multi-resource operating room scheduling and rescheduling using a rolling horizon approach: a case study. Journal of Industrial and Systems Engineering, 10(special issue on healthcare), 97-115.
Vogl, P., Braune, R., & Doerner, K. F. (2019). Scheduling recurring radiotherapy appointments in an ion beam facility. Journal of Scheduling, 22(2), 137-154.
Volland, J., Fügener, A., & Brunner, J. O. (2017). A column generation approach for the integrated shift and task scheduling problem of logistics assistants in hospitals. European Journal of Operational Research, 260(1), 316-334.
Welch, J., & Bailey, N. J. (1952). Appointment systems in hospital outpatient departments. The lancet, 259(6718), 1105-1108.
Zhang, P., Bard, J. F., Morrice, D. J., & Koenig, K. M. (2019). Extended open shop scheduling with resource constraints: Appointment scheduling for integrated practice units. IISE Transactions, 51(10), 1-24.
Zhou, L., Geng, N., Jiang, Z., & Wang, X. (2017). Combining revenue and equity in capacity allocation of imaging facilities. European Journal of Operational Research, 256(2), 619-628.
Zhou, L., Geng, N., Jiang, Z., & Wang, X. (2018). Multi-objective capacity allocation of hospital wards combining revenue and equity. Omega, 81, 220-233.