Scheduling of work periods for nurses is a complex task that has a significant impact on healthcare. It can be described as a constraint-based scheduling problem, the Nurse Rostering Problem (NRP), which consists of assigning shifts to nurses according to a set of hard and soft constraints. This thesis evaluates the use of Genetic Algorithms (GAs) to solve NRPs. The GA is an Evolutionary Algorithm (EA) that mimics natural selection by evolving a population of solutions through genetic processes, henceforth genetic operators. It is a stochastic algorithm that can handle hard and soft constraints simultaneously and is not vulnerable to local optima. In this thesis, the fitness and scalability of the GA for the NRP were evaluated and compared to a greedy benchmark algorithm. The fitness function quantifies the performance of the algorithms by adding up the incurred penalties associated with violating different constraints. The scalability corresponds to the algorithms’ performance for different problem sizes. A computational model of the NRP was implemented based on the International Nurse Rostering Competition (INRC) dataset, as well as a greedy benchmark algorithm and different versions of the GA. It was found that the most effective combination of methods for genetic operators was tournament selection, uniform crossover, and swap mutation. The selected parameter settings were 90% crossover probability, 10% mutation probability, and 3% elitism. A population size of 100, 220, and 340 was chosen for the sprint, medium, and long problem sizes, respectively. The GA received lower and therefore better fitness than the benchmark algorithm for all problem sizes. On average, the GA scored a fitness of 107.0 for the sprint instances, 395.6 for the medium, and 394.2 for the long. The corresponding results for the benchmark algorithm were 111.8, 535.4, and 631.2. Thus, the fitness for the GA was 3.77%, 25.73%, and 36.82% lower than for the benchmark algorithm, for the sprint, medium, and long problem sizes, respectively. This thesis concludes that the GA performs better than the benchmark algorithm for all problem sizes and that the GA scales better with increasing problem sizes. The results suggest that a balance between exploration and exploitation is a key aspect to converge well while avoiding local optima. In conclusion, the proposed GA presents a promising solution approach for nurse scheduling. Potential areas for future work include further improving the GA version, incorporating fairness between the individual nurse schedules, and comparisons to other EAs and manual scheduling.

Schemaläggning av arbetstid för sjuksköterskor är en komplex uppgift med stor påverkan på sjukvården. Det kan beskrivas som ett begränsningsbaserat schemaläggningsproblem, s.k. Nurse Rostering Problem (NRP), som innebär att tilldela skift till sjuksköterskor utifrån en uppsättning av hårda och mjuka begränsningar. Denna avhandling utvärderar användandet av Genetiska Algoritmer (GAs) för att lösa NRPs. GA är en evolutionär algoritm (EA) som imiterar naturligt urval genom att evolvera en population av lösningar genom genetiska processer, härefter genetiska operatorer. Det är en stokastisk algoritm som kan hantera hårda och mjuka begränsingar samtidigt och inte är känslig för lokala optima. I denna avhandling utvärderades fitnessen samt skalbarheten av GA för NRP och jämfördes med en girig benchmark-algoritm. Fitness-funktionen kvantifierar algoritmernas prestation genom att summera straffen för att bryta mot olika begränsingar. Skalbarheten motsvarar algoritmernas prestation för olika problemstorlekar. En beräkningsmodell för NRP implementerades baserat på datamängden från International Nurse Rostering Competition (INRC), samt en girig benchmark-algoritm och olika versioner av GA. Den mest effektiva kombinationen av metoder för genetiska operatorer visade sig vara turneringsselektion, enhetlig korsning och bytesmutation. De valda parameterinställningarna var 90% sannolikhet för korsning, 10% för mutation och 3% elitism. Populationstorlekarna 100, 220 respektive 340 valdes för problemstorlekarna sprint, mellan och lång. GA gav lägre och därmed bättre fitness än benchmark-algoritmen för alla problemstorlekar. I genomsnitt fick GA en fitness på 107.0 för sprintinstanserna, 395.6 för mellan och 394.2 för lång. De motsvarande resultaten för benchmark-algoritmen var 111.8, 535.4 och 631.2. Således var fitnessen för GA 3.77%, 25.73% respektive 35.82% lägre än för benchmark-algoritmen för problemstorlekarna sprint, mellan och lång. Denna avhandling drar slutsatsen att GA presterar bättre än benchmark-algoritmen för alla problemstorlekar samt att GA skalar bättre med ökande problemstorlek. Resultaten antyder att balansen mellan utforskning och exploatering är en viktig aspekt för att konvergera väl och samtidigt undvika lokala optima. Den föreslagna GA utgör en lovande lösningsansats till schemaläggning av sjuksköterskor. Potentiella områden för framtida studier inkluderar förbättring av GA-versionen, inkorporering av rättvisa mellan individuella sjuksköterskors scheman samt jämförelser med andra EAs och manuell schemaläggning.