From large to small, most every workplace requires some sort of scheduling. Nowhere perhaps is this more critical than in hospitals, where, in addition to all the normal labor restrictions for scheduling, it is a matter of life or death that hospitals be sufficiently staffed at any hour of the day. The nurse scheduling problem (NSP) is the problem of creating a schedule that satisfies all the wants and needs of a hospital and its nurses. With current methods, the problem cannot be solved directly in reasonable runtime and its large number of constraints mean that any feasible solution may be difficult or even impossible to find. This problem's difficulty, real-world application, and its unique relationship to its constraints have solidified the NSP's importance in the field of computational complexity theory. In this paper the NSP is analyzed and methods for solving it are discussed. Additionally select methods and constraints are showcased in corresponding software.


Fox, Nathan

Second Advisor

Kelvey, Rob


Computer Science; Mathematics


Nurse Scheduling Problem, Nurse Rostering Problem, complexity theory, computational complexity theory

Publication Date


Degree Granted

Bachelor of Arts

Document Type

Senior Independent Study Thesis



© Copyright 2018 Nicholas Hagopian-Zirkel