Rostering and Task Scheduling: Applications in Manpower Planning

In a modern society, manpower can be both a scarce and an expensive resource. Skilled personnel is usually in high demand and accounts for a significant part of total expenses in many companies. When the work is divided in shifts, a roster is compiled to allocate these to the employees. The rostering process is non-trivial and especially when service is required around the clock, rostering may involve considerable effort from a designated planner. Therefore, in order to minimize costs and overstaffing, to maximize the utilization of available staff, and to ensure a high level of satisfaction among the employees, sophisticated scheduling methods are required. When approaching the day of operation, the detail level of the planning becomes finer. With a given allocation of shifts to employees, the focus is turned to tasks scheduling within those shifts. The objective is to assign as much work as possible to the available staff, while respecting various requirements and rules and while including possible transportation time between tasks. This thesis presents a number of industrial applications in rostering and task scheduling. The applications exist within various contexts in health care, the aviation industry, transportation, and production. The focus regarding rostering is both on a generalized rostering problem, which captures most realistic settings, and also on a more specific case, where particular issues and extensions are examined. In task scheduling, the focus is restricted to scheduling problems with temporal dependencies between tasks. However, these problems appear in various contexts and with different properties. A group of the problems considered are related to vehicle routing problems, where transportation and time windows are important factors that must be accounted for. Mathematical and logic-based models are presented for the problems considered. Novel components are added to existing models and the modeling decisions are justified. In one case, the model is solved by a simple, but efficient greedy construction heuristic. In the remaining cases, column generation is applied. Column generation is an iterative exact solution method based on the theory of linear programming and is capable of providing provably optimal solutions. In some of the applications, the approach is modified to provide feasible solutions of high-quality in less time. The exceptional solution quality of column generation is maintained, but the certificate of optimality is compromised. The contribution of this thesis is partly in the introduction, extension, and refinement of mathematical models for practical planning problems. Further, the contribution is in the proposed solution methods, which produce applicable and superior results to a range of realistic manpower planning problems. The contributions are presented in six scientific papers, which are compiled in the thesis. These include the development of a versatile approach to generalized rostering, building on an idea of compile-time customization. Several extensions of practical rostering problems are presented. For task scheduling, a general modeling of temporal dependencies is introduced and included in the methodology of column generation. The approach is applied to several practical problems with promising results. Lastly, a novel approach to crane scheduling with superior results is presented.