In this thesis we investigate an extension of the famous Nurse Rostering Problem. The Nurse Rostering Problem is the problem of finding an optimal assignment of nurses to shifts given some constraints. We extend the problem by considering that the nurses different sets of skills
...
In this thesis we investigate an extension of the famous Nurse Rostering Problem. The Nurse Rostering Problem is the problem of finding an optimal assignment of nurses to shifts given some constraints. We extend the problem by considering that the nurses different sets of skills by which they can only perform certain tasks. We want the working hours of the nurses to be as close as possible to their contract hours, and moreover, we want the amount of work done on a specific task to be as close as possible to the demand for that task. It is important that the user of the model has control over the execution time. We model this problem with an Integer Linear Program (ILP). The data we use to test the model is provided by ORTEC. ORTEC provided a random data generator which generates data such as contract hours and demands for certain skills, for a fictional company. The number of employees, skills and weeks can be determined by the user. We use small, medium and large data sets where large data sets consist of 100 employees, 52 weeks and 5 different skills. Our model is a linear approximation of a quadratic problem. It is based on minimizing the largest deviation in contract hours and demand. To get control over the computation time of the model, a timer is implemented. The desired maximum computation time can be set by the user and the model provides the best solution found within that time boundary. The initial model is tested with three different solvers: COIN-OR, CPLEX and Gurobi. The computation times and consistency of the solvers are compared. We found that CPLEX was in our case the best solver with an average computation time of 7.2 seconds for data sets of 100 employees, 5 skills, and 52 weeks. Next, we use an iterative procedure, which runs the model several times in order to obtain a more accurate solution. In this procedure, certain deviations, and their contributing variables, are fixed in every iteration while the model runs on the remaining non-fixed variables. An extension to this iterative procedure is also presented. In this extension, multiple deviations are fixed in every iteration to decrease the execution time. The fixed percentage of maximum deviations per iteration is tested on accuracy and computation time. We found that for small data sets it is best to use 1%, which results in one fixed deviation per iteration. For medium data sets, the best range is from 1% to 10%. Lastly for large data sets we recommend to use a range of 10% to 20%.