Large-Scale Rostering and Allocation Problem

Foong Chee Kin

Abstract

Many labor intensive organizations in service industry such as airlines, hospitals and hotels have extremely high workforce cost. They believe by having the right staffs at the right time to serve customers makes them remain viable in the competitive market. However, keeping high level of human resource is not a good solution as it directly increases the operating cost. Due to the conflict of interest, these organizations invest heavily in finding ways to manage human resource effectively, with the mission of reducing workforce cost while keeping high service level. Among all, personnel scheduling and rostering has become a popular approach that has been used widely since 1950s. It is defined as the process of constructing optimized work timetables for staff and involves allocating suitably qualified staffs to meet a time dependent demand for different services and at the same time observing industrial workplace agreements and attempting to satisfy individual work preferences (see Ernst et al., 2004).

In the old days, rosters were constructed manually. Only a limited amount of constraints could be included in the calculation because of the slow computational speed. As a result of technological advancement, rosters are now constructed using computers. Problems involving complex rules have been modeled and solved successfully. For example, according to Barnhart, C., American Airlines with more than 25,000 staffs enjoyed savings of US$20 million a year when staff planning was being done in a more effective way in 1993. In general, organizations enjoy greater cost savings with lower workforce cost. Although more constraints can be included to find the best work timetables, the solving time still depends greatly on the complexity of the problem. Hence, choosing a suitable formulation which is able to solve large scale rostering problem is very important.

This project involves the allocation of staffs to various tasks in an organization. There are different types of staffs. Each of them has his own skill and experience. Similarly, there are many types of tasks. Each of the tasks requires different amount of staffs, depending on the level of difficulty. Staffs have to be allocated to tasks in accordance to combination rules and constraints. The objective of this project is to develop a computational model to assign staffs to tasks by using Branch-and-Price. Branching is applied to select an optimal set of rosters from a generalized set partitioning problem (GSPP) where the variables are all integers. Pricing (i.e. Column Generation) is used to generate worthy rosters for each staff. This is done by modeling each staff using either resource-constrained shortest path problem (RCSPP) or ordinary shortest path (SP). The model is then implemented using ILOG OPL Studio and tested for efficiency with some data sets. It can be concluded that good rosters can be obtained by using the proposed model. Some recommendations are also given to improve the proposed.