Negotiation at the short and mid term level supported by analysis of nurse rostering problems

The nurse rostering problem is an NP-hard combinatorial optimisation problem for the assignment of shifts to nurses. The rosters need to comply to an extensive set of constraints stemming from legal concerns, organizational concerns and personal preferences of the nurses. In most cases, the rostering is performed at the level of one ward in a hospital. There is a wide set of different models for nurse rostering problems. The problems differ from country to country, from hospital to hospital and even wards within the same hospital may have different models. To improve the transferability of solution methods, designed for the different models, common and standardised formulations are necessary. We show how numberings, designed for a fast evaluation of nurse rostering problem solutions can be used to generate a formal, unambiguous representation of nurse rostering problem instances. The use of numberings allows for an efficient translation of instances to other problem domains. We give a proof of concept in the form of translation schemes to Satisfiability Problems and Mixed Integer Programs. The schemes can be used for the fast development of prototype solvers for new problems, or variations of known ones for which no specific solver is available. As is commonly known, there is a gap between the nurse rostering problem models developed for research purposes and those used in practice. We organised the First International Nurse Rostering Competition 2010 . The main objectives of the competition were to generate new approaches to the associated problem by attracting researchers from different areas of research, to reduce the gap between research and practice in this important area of operations research and to further stimulate debate within the widening rostering research community. Wards operate within a larger whole. At the individual level of a ward, (sudden) nurse shortages may arise. As a solution, wards in a hospital can cooperate to resolve shortages and to increase their level of efficiency. This kind of interoperability is naturally modelled using agents. The autonomous agents are responsible for the optimisation of their rosters and communicate in order to tackle the aforementioned issues. In this thesis, we apply a number of state-of-the-art negotiation protocols and compare computation times, solution quality and communication times (network load) of the aforementioned approaches. We compare with a centralised approach. The above stated problems are at the short term level of personnel management. The problems at the different personnel management levels, short, mid and long term, are interconnected and information from lower level problems should serve as input for the higher level decision problems. In this thesis we consider the mid term level problem of dividing workload (shifts) and personnel (nurses) among the different wards in a hospital. We model this problem as a multiissue multi-agent negotiation problem with workload and personnel as issues. Information on the short term level problem is aggregated into operational performance level curves and serves as input for this negotiation problem. We study the problem in both an environment with complete and incomplete information. For the incomplete information setting, we design a negotiation protocol and study theoretical and qualitative properties of the protocol such as Pareto optimality, solution quality, convergence, In the first part of the thesis, we elaborate on the nurse rostering problem under study. Besides an informal problem description, we present a formal representation using numberings and we elaborate on a mathematical model. We show how the use of numberings allows for an automated translation into Satisfiability Problems and Mixed Integer Programs. Next, we present the First International Nurse Rostering Competition 2010 . We elaborate on the organisation of the competition, its spirit and its rules, and we discuss the results. Negotiation is the main subject of the second part of the thesis. We study the application of five state-of-the-art negotiation protocols to the short term level problem of resolving nurse shortages and increasing the efficiency levels of wards in a hospital. Next, we perform an in-depth study of short term nurse rostering problem instances, leading to the introduction of the operational performance platforms of a ward. Finally, we present and discuss the multi-issue multi-agent negotiation protocol we developed for the division of workload and personnel among the wards in a hospital.status: publishe