Abstract
We discuss the problem of constructing physician schedules in emergency rooms. Starting from practical instances encountered in five different hospitals of the Montreal (Canada) area, we first propose generic forms for the constraints encountered in this context. We then review several possible solution techniques that can be applied to physician scheduling problems, namely tabu search, column generation, mathematical programming and constraint programming, and examine their suitability for application depending on the specifics of the situation at hand. We conclude by discussing the problems encountered when trying to perform computational comparisons of solution techniques on the basis of implementations in different practical settings.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Acme-Express: Medical staff and physician scheduling software (2000), http://www.docs2000.net/productdetailsy2k.asp
Beaulieu, H.: Planification de l’horaire des médecins dans une salle d’urgence. Master’s Thesis, Département d’informatique et de recherche opérationnelle, Université de Montréal, Canada (1998)
Beaulieu, H., Ferland, J.A., Gendron, B., Michelon, P.: A mathematical programming approach for scheduling physicians in the emergency room. Health Care Management Science 3, 139–200 (2000)
Berrada, I.: Planification d’horaires du personnel infirmier dans un établissement hospitalier. Ph.D. Dissertation, Département d’informatique et de recherche opérationnelle, Université de Montréal, Canada (1993)
Berrada, I., Ferland, J.A., Michelon, P.: A multi-objective approach to nurse scheduling with both hard and soft constraints. Socio-Economic Planning Sciences 30, 183–193 (1996)
Bourdais, S., Galinier, P., Pesant, G.: HIBISCUS: A constraint programming application to staff scheduling in health care. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 153–167. Springer, Heidelberg (2003)
Burke, E.K., De Causmaecker, P., Vanden Berghe, G.: A hybrid tabu search algorithm for the nurse rostering problem. In: McKay, B., Yao, X., Newton, C.S., Kim, J.-H., Furuhashi, T. (eds.) SEAL 1998. LNCS (LNAI), vol. 1585, pp. 187–194. Springer, Heidelberg (1999)
Burke, E.K., De Causmaecker, P., Vanden Berghe, G., Van Landeghem, H.: The state of the art of nurse rostering. Journal of Scheduling 7, 441–499 (2004)
Buzon, I.: La confection des horaires de travail des médecins dans une salle d’urgence résolue à l’aide de la méthode tabou. Master’s Thesis, École Polytechnique, Montréal, Canada (2001)
ByteBloc Software: Epsked 3.0 bytebloc software (1995), http://www.bytebloc.com
Cangini, G.: A constraint programming local search algorithm for physician scheduling. Publication CRT-2000-26, Centre for Research on Transportation, Université de Montréal, Canada (2000)
Carter, M.W., Lapierre, S.D.: Scheduling emergency room physicians. Health Care Management Science 4, 347–360 (2001)
Chvàtal, V.: Linear Programming. Freeman, New York (1983)
Dowsland, K.A.: Nurse scheduling with tabu search and strategic oscillation. European Journal of Operation Research 106, 393–407 (1998)
Forget, F.: Confection automatisée des horaires des médecins dans une salle d’urgence. Master’s Thesis, Département d’informatique et de recherche opérationnelle, Université de Montréal, Canada (2003)
Gendreau, M.: An introduction to tabu search. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics, pp. 37–54. Kluwer Academic Publishers, Dordrecht (2003)
Gendreau, M., Hertz, A., Laporte, G.: A tabu search algorithm for the vehicle routing problem. Management Science 40, 1276–1290 (1994)
Gendreau, M., Soriano, P., Salvail, L.: Solving the maximum clique problem using a tabu search approach. Annals of Operations Research 41, 385–403 (1993)
Glover, F.: Future paths for integer programming and links to artificial intelligence. Computers and Operations Research 13, 533–549 (1986)
Knaunth, P.: The design of shift systems. Ergonomics 36, 15–28 (1993)
Knaunth, P.: Design better shift systems. Applied Ergonomics 27, 39–44 (1996)
Labbé, S.: La confection automatisée d’horaires pour les médecins en salles d’urgence. Master’s Thesis, École des Hautes Études Commerciales de Montréal, Canada (1998)
Labit, P.: Amélioration d’une méthode de génération de colonnes pour la confection d’horaire d’infirmières. Master’s Thesis. École Polytechnique, Montréal, Canada (2000)
Lloyd, S., Shannon, S., Steiner, D.: Burnout, depression, life and job satisfaction among Canadian emergency physicians. Journal of Emergency Medicine 12, 559–565 (1994)
Marriott, K., Stuckey, P.J.: Programming with Constraints: An Introduction. MIT Press, Cambridge, MA (1998)
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience, New York (1988)
Rousseau, L.M., Pesant, G., Gendreau, M.: A hybrid algorithm to solve a physician rostering problem. In: Second Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems Paderborn, Germany (2000)
Skorin-Kapov, J.: Tabu search applied to the quadratic assignment problem. ORSA Journal on Computing 2, 33–45 (1990)
Taillard, É.: Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research 47, 65–74 (1990)
Taillard, É.: Robust taboo search for the quadratic assignment problem. Parallel Computing 17, 443–455 (1991)
Peake Software Laboratories: Tangier emergency physician scheduling software. http://peakesoftware.com/peake/
Trilling, G.: Génération automatique d’horaires de médecins de garde pour l’hôpital Côte-des-Neiges de Montréal. Publication CRT-98-05. Centre for Research on Transportation, Université de Montréal, Canada (1998)
Vovor, T.: Problème de chemins bicritère ou avec contraintes de ressources: algorithmes et applications. Ph.D. Thesis, École Polytechnique, Montréal (1997)
Weil, G., Heus, K., Poujade, P., François, M.: Constraint Programming for nurse scheduling. Engineering in Medicine and Biology 14, 417–422 (1995)
Warner, D.M.: Scheduling nursing personnel according to nursing preference: a mathematical programming approach. Operations Research 24, 842–856 (1976)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gendreau, M. et al. (2007). Physician Scheduling in Emergency Rooms. In: Burke, E.K., Rudová, H. (eds) Practice and Theory of Automated Timetabling VI. PATAT 2006. Lecture Notes in Computer Science, vol 3867. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77345-0_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-77345-0_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77344-3
Online ISBN: 978-3-540-77345-0
eBook Packages: Computer ScienceComputer Science (R0)