Nurse rostering is the assignment of specific nurses to specific shifts for a future scheduling period. The work schedule that is created is called a roster. The reconstruction of a disrupted roster is called rerostering. When solving the rostering and rerostering problems there are two considerations: the organization's costs and the nurses' preferences. Traditional solution methods, often based on integer programs (IP), have two short comings; first, they rely on one objective function to represent both the organization's and nurses' goals; and second, rerostering requires either the complete resolving of the rostering problem or a new solution method to fix the roster.

This dissertation proposes three agent-based heuristics; Competitive Nurse Rostering (CNR), an extension called CNR-Iterated Local Search (CNR-ILS), and an extension of CNR-ILS called CNR-Rerostering (CNRR). These decentralized heuristics model shift trading between nurses via an auction protocol. They are the first nurse rostering methods that model each nurse's preferences in separate objective functions and are the first competitive, agent-based rostering and rerostering methods. They uniquely separate the organizational cost and nurse preference problems by constraining the preference problem's solution space to alternate cost optimal solutions. CNRR is the first rostering solution that also rerosters nurses. Furthermore, they all can be easily parallelized, have the ability to attribute agents to the entities in the system (nurses), and have a natural ability for real-time scheduling.

The rostering algorithms presented in this dissertation were tested on realistic random data sets and further tested by developing schedules for the nurses of a real hospital's medical surgical ward. When the test ward's nurses were surveyed, they consistently favored the solutions produced by CNR-ILS compared to those produced by CNR, an IP and the hospital.

CNRR was tested on realistic datasets that mimic potential random disruptions to rosters produced by CNR-ILS. CNRR finds solutions to over 90% of these random disruptions. Less than one sixth of the solutions had a serious impact to nurse preferences.