Development of a doctor scheduling system: a constraint satisfaction and penalty minimisation scheduling model

Document Type: Research Paper


1 Department of Mechanical, Industrial and Aeronautical Engineering, University of the Witwatersrand, Johannesburg, South Africa.

2 Department of Mechanical and Industrial Engineering, College of Engineering and Technology, University of Dar es Salaam, Tanzania.


Doctor scheduling is a complex, costly and time-consuming exercise. This study develops a constraint satisfaction and penalty minimisation scheduling model for meeting ‘hard constraints’ and minimises the cost of violating ‘soft constraints’, i.e. the user inputs, the total number of doctors to be scheduled, the maximum penalty to be met, and the minimum number of doctors to be assigned per shift. The algorithm creates a schedule which checks against all the constraints. The total schedule penalty associated with the constraint violations should be less than or equal to the user input penalty. If this condition is met, the schedule gets produced as the final and near-optimal solution. The model is managed to create a near optimal schedule with the minimal rule violations. However, it is challenging to provide a schedule with no rule violations. Such a situation is shown by the amount of computational time required to create a zero-penalty schedule, hours or even days needed to create a zero-penalty schedule. The system creates a schedule for a short period (weekly schedule) to promote flexibility; however, such a system does not promote fairness. Fairness is achieved through a cyclic schedule with rotations equal to the total number of doctors being scheduled. The system is managed to create a streamlined and flexible working environment and helped to improve the quality of healthcare. An optimization protocol can be incorporated into the system to reduce the search space and get the best optimal schedule since it is possible to get many schedules under the same user-defined parameters.


Main Subjects

[1]     Taifa, I. W., & Desai, D. A. (2017). User requirements customization and attractive quality creation for design improvement attributes. International journal for quality research11(1).

[2]     Taifa, I. W. (2016). Integration of quality function deployment (QFD) and ergonomics principles in product design improvement. Case study: student desk at engineering college (Master`s dissertation, Ahmedabad: Gujarat Technological University).

[3]     Puente, J., Gómez, A., Fernández, I., & Priore, P. (2009). Medical doctor rostering problem in a hospital emergency department by means of genetic algorithms. Computers & industrial engineering56(4), 1232-1242.

[4]     Cheng, B. M. W., Lee, J. H. M., & Wu, J. C. K. (1997). A nurse rostering system using constraint programming and redundant modeling. IEEE Transactions on information technology in biomedicine1(1), 44-54.

[5]     Trilling, L., Guinet, A., & Magny, D. Le. (2007). Nurse scheduling using integer linear programming and constraint programming. 12th IFAC symposium on information control problems in manufacturing INCOM 2006 (pp. 651-656). Saint-Etienne, France: Elsevier.

[6]     Banet, D. (2010). Heuristic scheduling for clinical physicians (Master thesis,University of Louisville). Retrieved from

[7]     Leksakul, K., & Phetsawat, S. (2011). Nurse scheduling using genetic algorithm. Mathematical problems in engineering.

[8]     Chen, J. G., & Yeung, T. W. (1993). Hybrid expert-system approach to nurse scheduling. Computers in nursing11(4), 183-190.

[9]     Kuo, Y. H. (2014). Integrating simulation with simulated annealing for scheduling physicians in an understaffed emergency department. HKIE transactions21(4), 253-261.

[10]  De Villiers, M. R., & De Villiers, P. J. T. (2004). Doctors' views of working conditions in rural hospitals in the Western Cape. South African family practice46(3), 21-26.

[11]  Leung, J. Y. (Ed.). (2004). Handbook of scheduling: algorithms, models, and performance analysis. CRC Press.

[12]  Carter, M. W., & Lapierre, S. D. (2001). Scheduling emergency room physicians. Health care management science4(4), 347-360.

[13]  Beaulieu, H., Ferland, J. A., Gendron, B., & Michelon, P. (2000). A mathematical programming approach for scheduling physicians in the emergency room. Health care management science3(3), 193-200.

[14]  Wang, T., Meskens, N., & Duvivier, D. (2015). Scheduling operating theatres: Mixed integer programming vs. constraint programming. European journal of operational research247(2), 401-413.

[15]  Marriott, K., Stuckey, P. J., & Stuckey, P. J. (1998). Programming with constraints: an introduction. MIT press.

[16]  Rousseau, L. M., Pesant, G., & Gendreau, M. (2000). A hybrid algorithm to solve a physician rostering problem. Second workshop on integration of AI and OR techniques in constraint programming for combinatorial optimization problems. Paderborn, Germany.

[17]  Cangini, G. (2000). A constraint programming local search algorithm for physician scheduling. Université de Montréal, Centre de recherche sur les transports.

[18]  Trilling, G. (1998). Automatic scheduling of doctors on call for the Côte-des-Neiges hospital in Montreal. University of Montreal, Center for Transport Research.

[19]  Bourdais, S., Galinier, P., & Pesant, G. (2003, September). HIBISCUS: A constraint programming application to staff scheduling in health care. International conference on principles and practice of constraint programming (pp. 153-167). Springer, Berlin, Heidelberg.

[20]  Gendreau, M. (2003). An introduction to tabu search. Handbook of metaheuristics (pp. 37-54). Springer, Boston, MA.

[21]  Labbé, S. (1998). Automated scheduling for doctors in emergency rooms (Master thesis, University of Montreal). Retrieved from

[22]  Cantera, I. E. B. (2001). The preparation of working hours of emergency physicians resolved using taboo research (University of Montreal). Retrieved from

[23]  Lo, C. C., & Lin, T. H. (2011, July). A particle swarm optimization approach for physician scheduling in a hospital emergency department. Seventh international conference on natural computation (ICNC) (pp. 1929-1933). IEEE.

[24]  Eberhart, R. C., & Shi, Y. (1998, March). Comparison between genetic algorithms and particle swarm optimization. International conference on evolutionary programming (pp. 611-616). Springer, Berlin, Heidelberg.

[25]  Trilling, L., Guinet, A., & Le Magny, D. (2006). Nurse scheduling using integer linear programming and constraint programming. IFAC proceedings volumes39(3), 671-676.

[26]  Acme Express Inc. (n.d.). Who’s on call? Retrieved Jul 15, 2013, from

[27]  ByteBloc. (n.d). Emergency providers scheduling system. Retrieved Jul 15, 2013, from

[28]  Tangier. (n.d.). The # 1 emergency medicine scheduling software. Retrieved Jul 15, 2013, from

[29]  Cerner. (n.d). Clairvia physician scheduler. Retrieved Jul 15, 2013, from

[30]  Gendreau, M., Ferland, J., Gendron, B., Hail, N., Jaumard, B., Lapierre, S., ... & Soriano, P. (2006, August). Physician scheduling in emergency rooms. International conference on the practice and theory of automated timetabling (pp. 53-66). Springer, Berlin, Heidelberg.

[31]  Taifa, I. W., & Desai, D. A. (2015). Quality function deployment integration with kano model for ergonomic product improvement (classroom furniture)-a review. Journal of multidisciplinary engineering science and technology (JMEST)2(9), 2484-2491.

[32]  Taifa, I. W., Desai, D. A., & Bulsara, N. M. (2018). The development of an ergonomically designed product through an integrated product team approach. International journal of occupational safety and ergonomics, (just-accepted), 1-32.

[33]  Knauth, P. (1993). The design of shift systems. Ergonomics36(1-3), 15-28.

[34]  Knauth, P. (1996). Designing better shift systems. Applied ergonomics27(1), 39-44.

[35]  The South African Department of Labour. (n.d). Basic guides for basic conditions of employment. Retrieved Aug 1, 2013, from of-employment-act-and-amendments

[36]  HPCSA. (n.d). Basic conditions of employment act. Retrieved May 12, 2013, from of_employment_2007.pdf

[37]  Munassar, N. M. A., & Govardhan, A. (2010). A comparison between five models of software engineering. International journal of computer science issues (IJCSI)7(5), 94.

[38]  Sheu, P. C. Y. (n.d). Software lifecycle models. Retrieved Dec 6, 2018, from

[39]  National Instruments Corporation. (n.d). Lifecycle models. Retrieved from

[40]  Taifa, I. W., & Desai, D. A. (2015). A review and gap analysis on integration of quality function deployment and ergonomics principles for product improvement (classroom furniture). Industrial Engineering journal, VIII12, 16-25.

[41]  Taifa, I. W., & Desai, D. A. (2016). Student-defined quality by kano model: a case study of engineering students in India. International journal for quality research10(3).