A comparative analysis of classical and cooperative coevolutionary genetic algorithms for solving nurse scheduling problems

Abstract

The Nurse Scheduling Problem (NSP) is a complex workforce planning task that involves assigning nurses to shifts while satisfying operational feasibility, legal regulations and preference-based quality requirements. Classical Genetic Algorithms (GA) are widely applied to NSP but rely on monolithic optimisation structures that evaluate all constraints within a single population, which can lead to constraint interference and reduced stability as problem realism increases. This study investigates a Cooperative Co-Evolutionary approach for NSP (Coop-NSP), which decomposes optimisation into two interacting subpopulations corresponding to hard and soft constraints. Both subpopulations employ an identical nurse-by-day chromosome representation and evolve independently under specialised objectives, with cooperation introduced through contextual fitness evaluation. Experiments were conducted on a weekly NSP with a seven-day planning horizon and multiple nurse roles, evaluated for 15,000 generations across 30 independent runs under identical parameter settings. The Classical GA achieved a mean best penalty of 651.30 ± 37.90, with a minimum best penalty of 581.7, while Coop-NSP obtained a higher mean best penalty of 768.72 but achieved a lower minimum best penalty of 507.64. The Classical GA exhibited rapid convergence, whereas Coop-NSP demonstrated stepwise convergence with sustained population diversity. Although Coop-NSP incurred higher computational cost, its structured cooperative optimisation framework provides a stable and extensible foundation for future integrated healthcare scheduling research.