This thesis considers three physician scheduling problems in health care systems. Specifically, we focus on improvements to current physician scheduling practices through the use of mathematical modeling. In the first part of the thesis, we present a physician shift scheduling problem focusing on maximizing continuity of care (i.e., ensuring that patients are familiar with their treating physicians, and vice versa). We develop an objective scoring method for measuring the continuity of a physician schedule and combine it with a mixed integer programming model. We apply our methods to the problem faced in the pediatric intensive care unit at Children's Healthcare of Atlanta at Egleston, and show that our schedule generation approach outperforms manual methods for schedule construction, both with regards to solution time and continuity. The next topic presented in this thesis focuses on two scheduling problems: (i) the assignment of residents to rotations over a one-year period, and given that assignment, (ii) the scheduling of residents' night and weekend shifts. We present an integer programming model for the assignment of residents to rotations such that residents of the same type receive similar educational experiences. We allow for flexible input of parameters and varying groups of residents and rotations without needing to alter the model constraints. We present a simple model for scheduling 1st-year residents to night and weekend shifts. We apply these approaches to problems faced in the Department of Surgery Residency Program at Emory University School of Medicine. Rotation assignment is made more efficient through automated schedule generation, and the shift scheduling model allows us to highlight infeasibilities that occur when shift lengths exceed a certain value, and we discuss the impact of duty hour restrictions under limitations of current scheduling practices. The final topic of this thesis focuses on the assignment of physicians to various tasks while promoting equity of assignments and maximizing space utilization. We present an integer programming model to solve this problem, and we apply this model to the physician scheduling problem faced in the Department of Gynecology and Obstetrics at Emory University Hospital and generate high quality solutions very quickly.

A hybrid methodology of game theory and Monte Carlo Tree Search was developed and the hybrid methodology was tested with various case studies through the nurse scheduling problem to show that it was able to form Pareto front dominance solutions, finding feasible solutions that were optimal and finding feasible partial solutions in over-constrained problems. The performance comparison was carried out with the Genetic Algorithm on the Resident Physician Scheduling problem and showed that the hybrid methodology was able to produce better quality solutions compared to the state of the art approach.

O Problema de Escalonamento de Médicos (Physician Scheduling Problem) consiste em atribuir tarefas a médicos num horizonte de planejamento respeitando regras laborais, contratuais e de preferências pessoais de modo a satisfazer a demanda de serviços de um hospital. O problema lida majoritariamente com o objetivo de maximizar o atendimento dos requisitos de preferência pessoal, respeitando as restrições laborais e organizacionais. Sobre esta classe de problemas, vários métodos de resolução e suas variantes têm sido propostos na literatura. Ademais, mais características têm sido agregadas ao problema, tornando-o mais complexo e deste modo fazendo-se mais necessária a aplicação de métodos mais elaborados para a sua resolução. Neste trabalho são estudados, reformulados e propostos métodos de resolução baseados em programação matemática para tratar o problema de escalonamento acíclico de médicos em departamento de emergência de hospitais. O primeiro modelo tem como objetivo a minimização da soma ponderada dos desvios das restrições de distribuição. O segundo modelo tem como objetivo, a minimização do máximo dos desvios obtidos nas restrições de distribuição, a fim de se obter escalas mais equilibradas entre os médicos. Foram também propostas heurísticas baseadas na formulação matemática cujos resultados não foram competitivos com as dos modelos. Os modelos foram testados sobre um conjunto de instâncias fictícias resultantes de uma mescla entre instâncias benchmark e características do problema. Os resultados computacionais demonstram que formulação ponderada obteve solução ótima para grande parte das instâncias, embora os limitantes inferiores tenham sido majoritariamente fracos. Em relação ao segundo modelo, soluções ótimas não foram obtidas e os limitantes inferiores foram igualmente fracos. Relativamente a qualidade das escalas, o segundo modelo teve melhor comportamento comparando ao modelo de somas ponderadas. Dada a qualidade das soluções, nota-se a viabilidade da solução baseada em técnicas de otimização em detrimento da manual, pois esta ainda é mais suscetível de erros e acarreta um alto tempo para obtenção de solução. / The Physician Scheduling Problem consists in task assignment to physicians in a planning horizon considering a set of organizational rules, work regulations and individual preferences in order to satisfy an hospital wards work demand. The aim is to find a schedule which maximizes the satisfaction of individual preferences requirements while meeting work regulations and organizational rules. A plethora of solution methods and its variants have been proposed in the literature to solve this class of problem. Moreover, more features have been aggregated to the problem turning it into a more complex and thus estimulating the application of more elaborated methods to its decision. In this work we study, reshape and propose decision methods based in mathematical programming to handle non-ciclic physician scheduling problem in emergency wards. The first formulation targets the minimization of the weighted sum of distribution constraints deviations. The second formulation targets the minimization of the maximum deviations obtained at the distribution constraints aiming more balanced schedules between the physicians. Mathematical formulation heuristics were also proposed and the findings were not satisfactory as they were not competitive with the model. Experiments with our models were performed over a set of dummy instances, as result a of a mixture of benchmark instances and the considered problems features. From our experiments we have found that optimal solutions were obtained through the weighted sum model, despite the poor lower bounds. On the other hand, for the second model, no optimal solution was found and poor lower bounds were similarly obtained. Regarding to the schedules quality, the min-max model had a better performance comparing to the weighted sum model. Given the solutions quality we can assume that optimization based techniques are sustainable comparing to manual, because the latter is prone to errors and omissions and also critical in terms of solutions achievement time.

O Problema de Escalonamento de Médicos (Physician Scheduling Problem) consiste em atribuir tarefas a médicos num horizonte de planejamento respeitando regras laborais, contratuais e de preferências pessoais de modo a satisfazer a demanda de serviços de um hospital. O problema lida majoritariamente com o objetivo de maximizar o atendimento dos requisitos de preferência pessoal, respeitando as restrições laborais e organizacionais. Sobre esta classe de problemas, vários métodos de resolução e suas variantes têm sido propostos na literatura. Ademais, mais características têm sido agregadas ao problema, tornando-o mais complexo e deste modo fazendo-se mais necessária a aplicação de métodos mais elaborados para a sua resolução. Neste trabalho são estudados, reformulados e propostos métodos de resolução baseados em programação matemática para tratar o problema de escalonamento acíclico de médicos em departamento de emergência de hospitais. O primeiro modelo tem como objetivo a minimização da soma ponderada dos desvios das restrições de distribuição. O segundo modelo tem como objetivo, a minimização do máximo dos desvios obtidos nas restrições de distribuição, a fim de se obter escalas mais equilibradas entre os médicos. Foram também propostas heurísticas baseadas na formulação matemática cujos resultados não foram competitivos com as dos modelos. Os modelos foram testados sobre um conjunto de instâncias fictícias resultantes de uma mescla entre instâncias benchmark e características do problema. Os resultados computacionais demonstram que formulação ponderada obteve solução ótima para grande parte das instâncias, embora os limitantes inferiores tenham sido majoritariamente fracos. Em relação ao segundo modelo, soluções ótimas não foram obtidas e os limitantes inferiores foram igualmente fracos. Relativamente a qualidade das escalas, o segundo modelo teve melhor comportamento comparando ao modelo de somas ponderadas. Dada a qualidade das soluções, nota-se a viabilidade da solução baseada em técnicas de otimização em detrimento da manual, pois esta ainda é mais suscetível de erros e acarreta um alto tempo para obtenção de solução. / The Physician Scheduling Problem consists in task assignment to physicians in a planning horizon considering a set of organizational rules, work regulations and individual preferences in order to satisfy an hospital wards work demand. The aim is to find a schedule which maximizes the satisfaction of individual preferences requirements while meeting work regulations and organizational rules. A plethora of solution methods and its variants have been proposed in the literature to solve this class of problem. Moreover, more features have been aggregated to the problem turning it into a more complex and thus estimulating the application of more elaborated methods to its decision. In this work we study, reshape and propose decision methods based in mathematical programming to handle non-ciclic physician scheduling problem in emergency wards. The first formulation targets the minimization of the weighted sum of distribution constraints deviations. The second formulation targets the minimization of the maximum deviations obtained at the distribution constraints aiming more balanced schedules between the physicians. Mathematical formulation heuristics were also proposed and the findings were not satisfactory as they were not competitive with the model. Experiments with our models were performed over a set of dummy instances, as result a of a mixture of benchmark instances and the considered problems features. From our experiments we have found that optimal solutions were obtained through the weighted sum model, despite the poor lower bounds. On the other hand, for the second model, no optimal solution was found and poor lower bounds were similarly obtained. Regarding to the schedules quality, the min-max model had a better performance comparing to the weighted sum model. Given the solutions quality we can assume that optimization based techniques are sustainable comparing to manual, because the latter is prone to errors and omissions and also critical in terms of solutions achievement time.