The aim of the project BeAct is to automate shift design/scheduling for hospitals. Shift design/scheduling is the process of making a schedule containing shifts that cover the demand for workers while satisfying a set of other requirements. The requirements are many, and the number of possible solutions too vast for a manual approach-finding a solution manually is possible, but it is unlikely to be an optimal solution. Part of the challenge we have tackled is to formalize the set of requirements in a mathematical model-it is critical for the optimization to include all of the actual requirements, and not only simplified versions or just those that are easy to formulate.

In BeAct, we have used a mixed integer linear programming (MILP) approach. Through a continuous dialog with several Norwegian hospitals we have built the model with variables, constraints, and objectives.

Some of the objectives included are: minimization of personnel cost; minimization of the total number of different shifts; matching with the contracted working hours; even distribution of excess capacity. Constraints included are: a maximum of different shifts to be used during different periods; overlap between shifts; a common leaving time for all day shifts; one main shift with most of the workers each day.

The formulation allows for different kinds of tasks requiring skills that only a part of the workforce possesses. The requirement of meeting the demand is formulated as a ‘hard' constraint, but a possibility for doing some of the tasks at another time than originally specified is implemented.

The developed prototype that is developed is using the Xpress-MP as the solver. In the test cases tried so far, the solution gap is usually below 5-10 % within five minutes, and in some cases optimal solutions are found within seconds or a few minutes. A few tests have been performed on real cases from hospitals, but these cases were quite simple, and more testing should be done.