Personnel scheduling: A literature review <s> Application area and applicability of research <s> The annual Edmonton Folk Music Festival is run almost entirely by its 1,800 volunteers. While people are usually enticed into volunteering for the folk fest by perks, such as free access to the entertainment, gourmet meals, and T-shirts, their willingness to return year after year depends on an intangible degree of satisfaction. In spring 2003, a crew coordinator sought to automate the scheduling process for his crew of about 35 volunteers to save time and to accommodate volunteers' preferences when possible. We developed a spreadsheet-based decision-support tool that generated shift times, scheduled volunteers according to various constraints and preferences, and produced master and individual schedules. <s> BIB001 </s> Personnel scheduling: A literature review <s> Application area and applicability of research <s> Computational methods for rostering and personnel scheduling has been a subject of continued research and commercial interest since the 1950s. This annotated bibliography puts together a comprehensive collection of some 700 references in this area, focusing mainly on algorithms for generating rosters and personnel schedules but also covering related areas such as workforce planning and estimating staffing requirements. We classify these papers according to the type of problem addressed, the application areas covered and the methods used. In addition, a short summary is provided for each paper. <s> BIB002 </s> Personnel scheduling: A literature review <s> Application area and applicability of research <s> The problem of rerostering nurse schedules arises in hospitals when at least one nurse informs that she will be unable to perform the shifts assigned to her on one or more future work days. As a result, the current roster must be rebuilt in accordance with labour contract rules and institutional requirements. All such restraints are regarded as hard constraints. However, major alterations in the previously assigned nurse schedules must be avoided. This paper is based on a case study of a public hospital in Portugal. It presents two new integer multicommodity flow formulations for the rerostering problem, besides a computational experiment performed using real data. The first model is based on a directed multilevel acyclic network. The aggregation of nodes in this network led to the second model. The results obtained show that the second integer multicommodity flow formulation outperforms the first, both in terms of solution quality, as well as in computational time. <s> BIB003 </s> Personnel scheduling: A literature review <s> Application area and applicability of research <s> In this paper, we present a scatter search algorithm for the well-known nurse scheduling problem (NSP). This problem aims at the construction of roster schedules for nurses taking both hard and soft constraints into account. The objective is to minimize the total preference cost of the nurses and the total penalty cost from violations of the soft constraints. The problem is known to be NP-hard. The contribution of this paper is threefold. First, we are, to the best of our knowledge, the first to present a scatter search algorithm for the NSP. Second, we investigate two different types of solution combination methods in the scatter search framework, based on four different cost elements. Last, we present detailed computational experiments on a benchmark dataset presented recently, and solve these problem instances under different assumptions. We show that our procedure performs consistently well under many different circumstances, and hence, can be considered as robust against case-specific constraints. <s> BIB004 </s> Personnel scheduling: A literature review <s> Application area and applicability of research <s> Labour scheduling plays an important and critical role in Sainsburys day to day operations and profitability. The integrated workforce management solution for Sainsburys is an intelligent solution for the operational deployment of human resources, integrated business forecasting, generation and calculation of workload and staff scheduling. The workforce management technology has provided Sainsburys with a fully web-based and centralised system that produces optimised schedules for all employees satisfying the forecasted demand of work with granularity of fifteen minutes. The system is configured to respect all operational and business requirements as well as employee contractual constraints. This paper introduces the workforce management solution system designed, developed and implemented for Sainsburys. We concentrate on two modelling structures, namely the work pattern model and optimisation model, and briefly discuss the optimisation process. Copyright Springer Science+Business Media, LLC 2007 <s> BIB005 </s> Personnel scheduling: A literature review <s> Application area and applicability of research <s> This paper presents an integrated staff-sizing system for analyzing and determining workforce management policies with consideration of staff flexibility in service organizations, which addresses and captures the integrated requirements between long-term manpower planning and short-term staff scheduling in the service sector. Multiple Objective Linear Programming (MOLP) is applied to optimize several diversified goals. Solution methods to the MOLP models for the staff planning and staff scheduling are developed respectively, then a solution approach is proposed to iteratively revise the unacceptable staff-sizing plan or scheduling plan. Finally, an example of nurse sizing is analyzed and computational studies are carried out to investigate managerial insights. <s> BIB006 </s> Personnel scheduling: A literature review <s> Application area and applicability of research <s> Labour costs represent the major portion of the total cost in many industries and activities. This investigation examines a four-day workweek (compared with the current five-day week schedule) for maintenance operations in the Power Holding Company of Nigeria (PHCN). The aim is to reduce maintenance labour-costs, while satisfying increasing demands for higher effectiveness. Changing from the five to a four-day workweek for maintenance personnel at the Afam power-station is predicted to produce savings of 10% of maintenance labour cost without any loss of output or quality of service. <s> BIB007 </s> Personnel scheduling: A literature review <s> Application area and applicability of research <s> The solution of the aircrew-scheduling problem is represented by a set of rotations developed from a given set of flight segments. Once the set of rotations to be made by aircrew members has been determined, the air carrier must solve the aircrew rostering problem that entails the monthly assignment of aircrew members to planned rotations. This paper attempts to solve the aircrew rostering problem, thus constructing personalized monthly schedules using Simulated Annealing, Genetic Algorithms, and Tabu Search techniques. The developed models are tested on numerical examples that consist of constructing schedules for pilots. Dimensions of the considered examples are characteristic of small and medium-sized airlines. <s> BIB008 </s> Personnel scheduling: A literature review <s> Application area and applicability of research <s> Abstract The nurse rerostering problem occurs when one or more nurses cannot work in shifts that were previously assigned to her or them. If no pool of reserve nurses exists to replace those absent, then the current roster must be rebuilt. This new roster must comply with the labour rules and institutional constraints. Moreover, it must be as similar as possible to the current one. The present paper describes constructive heuristics, besides several versions of genetic algorithms based on specific encoding and operators for sequencing problems applied to the nurse rerostering problem, defined with hard constraints. In the genetic algorithms described, each individual in the population is associated with a pair of chromosomes, representing permutations of tasks and nurses. Those permutations are used as input to a procedure that generates rosters. The fitness of individuals is given by the similarity between the roster generated from the permutations and the current one. The authors developed several versions of the genetic algorithm, whose difference lay in the encoding of permutations and in the genetic operators used for each encoding. These heuristics were tested with real data from a Lisbon hospital and yielded good quality solutions. Scope and purpose The research reported is part of a project designed to develop a system for the management of nurse schedules for implementation in Portuguese public hospitals. The specific problem of rebuilding nurse schedules is addressed when unexpected staff absences arise. The complexity of the problem led the authors to design heuristic procedures. The tests performed so far with real data have shown that the algorithms attain good quality solutions at a computing time within the bounds stipulated by the hospital. <s> BIB009 </s> Personnel scheduling: A literature review <s> Application area and applicability of research <s> In labor scheduling, restaurant managers face dual challenges: overstaffing that means excessive labor costs and understaffing that invites the opportunity cost of service errors and lost business. Most operators seek to rely on their personal experience and judgment to determine schedules that are meant to maintain service quality and limit labor costs, but an analysis of one Korean restaurant finds that this goal is elusive. The labor scheduling model based on integer programming (IP) is presented to address the staffing and scheduling issues and service standards by maintaining an appropriate ratio of part-time to full-time employees. Using appropriate constraints, the model was used to generate a schedule for a table service restaurant in Seoul, South Korea, that is affiliated with a global chain. When compared to the existing schedule, the IP-generated schedule helped the restaurant reduce overall labor costs while ensuring appropriate service levels. <s> BIB010 </s> Personnel scheduling: A literature review <s> Application area and applicability of research <s> Real applications in shift scheduling often require handling rules such as multiple breaks, flexible shift lengths, overtime, multiple activities, among others. Because these rules demand a high level of flexibility, we model the problem as a Multi-Activity Shift Scheduling Problem (MASSP), where multiple activities can be scheduled in a shift. To solve the MASSP, we propose a column generation-based approach. The auxiliary problem is modeled as a Shortest Path Problem with Resource Constraints (SPPRC), where most difficult constraints are embedded in the underlying graph. To illustrate the solution approach, we present our experience solving a real-world problem from a large parking lot operator that schedules security staff and cashiers among several parking lots in Bogota (Colombia). The results show a significant reduction on the staffing total costs and on man-hours used. <s> BIB011 </s> Personnel scheduling: A literature review <s> Application area and applicability of research <s> This paper presents an adaptive neighborhood search method (ANS) for solving the nurse rostering problem proposed for the First International Nurse Rostering Competition (INRC-2010). ANS uses jointly two distinct neighborhood moves and adaptively switches among three intensification and diversification search strategies according to the search history. Computational results assessed on the three sets of 60 competition instances show that ANS improves the best known results for 12 instances while matching the best bounds for 39 other instances. An analysis of some key elements of ANS sheds light on the understanding of the behavior of the proposed algorithm. <s> BIB012 </s> Personnel scheduling: A literature review <s> Application area and applicability of research <s> The efficient and effective management of nursing personnel is of critical importance in a hospital's environment comprising a vast share of the operational costs. The adopted nurse workforce practices and policies highly affect the nurses' working conditions and the provided quality of care. Policy decisions on the staffing level have an impact on the outcome of the scheduling level and vice versa. Isolated reasoning typically leads to suboptimal decisions often resulting in ineffective outcomes of care. In order to overcome these inefficiencies, we propose in this paper a new integrative nurse staffing and shift scheduling approach. We test and assess the benefits of our approach in a reallife environment. Moreover, we examine the impact of several personnel policies on the staffing decision. <s> BIB013 </s> Personnel scheduling: A literature review <s> Application area and applicability of research <s> Nurse rostering is a complex task of practical relevance. Over the last years, researchers have been able to solve increasingly larger and more complex problems. In this paper, we describe the full procedure of running the First International Nurse Rostering Competition. The aim of the competition was to develop further interest in the area and to stimulate new solution approaches by bringing together researchers from different areas. <s> BIB014
We distinguish between six application areas: services, transportation, general, manufacturing, retail and military personnel scheduling problems. When no application area is mentioned in the text, we considered the paper to be "general". In Table 15 we list the relevant manuscripts classified according to the type of application area. Among the less frequent service application areas, classified as "Other", we find organizations such as restaurants BIB010 , supermarkets BIB005 , festivals BIB001 , parking lots BIB011 , etc. We can compare our results with the annotated library of Ernst et al. BIB002 . A notable difference is the share of manuscripts applied to transportation systems. Half of the papers in their library are developed for airline, railway, bus or subway systems. The impact of the transportation sector is limited in our findings, but the other application areas share similarities. Nurse rostering is by far the most popular and personnel rostering problems in services receive more attention than those in a production environment. In addition to the development of a model or a formulation, researchers usually provide a testing phase to illustrate the applicability of their research. The majority of papers favor real-world based data over theoretical data (Table 16 ). If it is not clear whether the model was actually implemented, we classify those papers into the set with real-world data. When the research was carried out, the authors hardly ever provided details of the process of implementation or the observed results, although these could have been of interest to the reader. The different stakeholders that are involved in personnel scheduling problems need to be kept satisfied during the implementation process. The problems that come in the wake of this implementation can be similar to problems other authors face in their work. Therefore, we encourage the provision of additional information on the behavioral factors that coincide with actual implementation.   BIB006 BIB007 BIB012 BIB008 BIB004    BIB013  BIB005 We noticed that in many papers the solution approach is only compared (if it is) with a few recent other solution techniques which the researchers had to implement themselves. Preferably, they only consider the problem setting which is the topic of their paper, rather than checking the performance on some benchmark instances. However, many of the considered problem instances look similar. Of course there are differences regarding the constraints and the objectives, but authors really avoid searching for benchmark instances to compare with. There are a few exceptions though. The NRPcompetition of the PATAT conference 2010 BIB014 , for example, is an excellent tool to give researchers the opportunity to check the quality of their solution approach concerning a number of different instances. Burke and Curtois  compare their solution method to a number of benchmark instances of nurse rostering problems they have collected over the years. Linked with the previous remark, we want to stress the benefits of a classification notation. De Causmaecker and Vanden Berghe  have introduced a classification notation for the nurse rostering problem, which could be extended to the personnel scheduling problem in general. Their classification notation is based on the α|β|γ-notation, which has proven very worthy in the field of resource constrained project scheduling. The widely studied personnel scheduling problem can take advantage of such a classification method, where the constraints, objectives, problem characteristics, etc. are indicated with parameters, allowing researchers to compare their methods with others in a similar problem setting. It can also be suitable to detect some new research areas. One of the reasons why many research projects do not make it until the implementation in practice is the restrictive problem setting they consider. As we already discussed in Section 2, the personnel scheduling problem is hardly ever integrated with other scheduling problems such as operating room scheduling, machine scheduling, etc. In reality, however, these different scheduling problems interfere with each other on a constant basis. Not only the lack of integration with other scheduling problems undermines the implementation ratio, the low degree of uncertainty incorporation is also one of the main reasons. Most of the researchers do not consider the effect of cancelled tasks, unavailable employees, increased workload, … Researchers should keep in mind that these events have a great impact on the quality of the proposed solutions. Instead of considering these events in the problem setting and trying to cope with them by using stochastic programming, researchers could also study their effects on the robustness of the solutions with a simulation experiment for example. Finally, only a handful of papers cope with these events by personnel (re)scheduling (combined with task assignment), rolling horizon techniques, etc. In the papers of Moz and Pato BIB003 BIB009 , for example, 68 random test instances are generated to mimic the absence of workers and to test the quality of the solution method, rather than considering distributions to model the absence. The lack of implementation is not always due to the researchers or the problem setting under consideration. It can be very hard to integrate the proposed algorithm into the software system(s) of the company. This can be restrictive for both the researchers and the company. From the viewpoint of the researchers, it is important to define the proposed algorithm as clearly as possible, so that the company's IT-department is able to integrate all the necessary steps into the software. The shift towards a multi-objective and over-constrained problem setting probably leads to an increased use of self-created hybrid heuristics in comparison to the use of commercial optimization software.