Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> E. W. Paxson of Rand has suggested that linear programming methods could be used as an alternative procedure in the scheduling section of Leslie C. Edie's interesting paper on “Traffic Delays at Toll Booths” (Leslie C. Edie. 1954. Traffic delays at toll booths. J. Opns. Res. Soc. Am. 2 107.). The purpose of this note is to elaborate on this suggestion. Operations Research, ISSN 0030-364X, was published as Journal of the Operations Research Society of America from 1952 to 1955 under ISSN 0096-3984. <s> BIB001 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> The purpose of this paper is to present a new methodology for scheduling nurses in which several conflicting factors guide the decision process. Unlike manufacturing facilities where standard shifts and days off are the rule, hospitals operate 24 hours a day, 7 days a week and face widely fluctuating demand. A more flexible arrangement for working hours and days off is needed, especially in light of the growing nursing shortage. To improve retention, management must now take into account individual preferences and requests for days off in a way that is perceived as fair, while ensuring sufficient coverage at all times. This multi-objective problem is solved with a column generation approach that combines integer programming and heuristics. The integer program is formulated as a set covering-type problem whose columns correspond to alternative schedules that a nurse can work over the planning horizon. A double swapping heuristic is used to generate the columns. The objective coefficients are determined by the degree to which the individual preferences of a nurse are violated. As part of the computational scheme, feasible solutions are refined to minimize the use of outside nurses, but when gaps in coverage exist, the outside nurses are distributed as evenly as possible over the shifts. The methodology was tested on a series of problems with up to 100 nurses using data provided by a large hospital in the US. The results indicate that high-quality solutions can be obtained within a few minutes in the majority of cases. <s> BIB002 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Nowadays flexibility is a strategic concept for firms. Indeed workload has to follow, as close as possible, the development of demand throughout the year. However, firms cannot engage and dismiss employees according to production requirements. Thus, workforce scheduling becomes a delicate task. In this paper, four mixed integer programming models are developed to solve the workforce schedule problem for a single-shift. The annualized hour scenario is considered with respect to a set of Swiss legal constrains. Furthermore, the minimal required workforce is guaranteed and it is assumed that each employee is able to perform each task within the team. All employees are full-time workers. <s> BIB003 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Abstract In the current economic and industrial conditions, with demand ever fluctuating, designing a timetable to define a work schedule for each employee is not an easy task. Moreover due to legal and cost constraints, it is not always possible to engage and dismiss the employees according to the production requirement. In this paper, a three-step method is presented assigning the daily work for full-time employees working on one shift. It takes into account a set of legal constraints (such as holiday arrangements) and it guarantees that the defined workforce is minimal, assuming that employees are able to perform their tasks. <s> BIB004 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> The need to adjust productive capacity to seasonal demand and the increasing flexibility in the distribution of annual working hours has given rise to new problems with respect to the organisation of staff working time. This paper presents a problem of planning annual working hours, in which the number of weekly working hours for any worker must belong to a previously agreed finite set and holiday weeks are the same for all the staff members. The problem is modelled and solved as a mixed integer linear program. <s> BIB005 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> The topic of this paper is workforce scheduling in a highly variable environment -- check proofing and encoding in a bank -- where uncertainties include both volume and arrival pattern of the work. A shop floor simulation model and a heuristic algorithm for workforce scheduling using simulation to estimate objective function are presented. The proposed approach results in a robust workforce schedule that can be easily adjusted in real time in response to environmental changes, such as volume and throughput fluctuations. A planning and scheduling framework within which the simulation is implemented is briefly discussed. <s> BIB006 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <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> BIB007 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper introduces a new integrated model for the combined days-off and shift scheduling problem (the tour scheduling problem). This model generalizes the forward and backward constraints, previously introduced by Bechtold and Jacobs for the shift scheduling problem, to the tour scheduling problem. This results in a general and compact formulation that can handle several types of scheduling flexibility. We also provide a new proof of the correctness of forward and backward constraints based on Benders decomposition. The latter approach is interesting in itself because it can be used to solve the problem when extraordinary overlap of break windows or start-time bands is present. A discussion of model size for a set of hypothetical test problems is presented to show the merits of the new formulation. Copyright Kluwer Academic Publishers 2004 <s> BIB008 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Many organizations face employee scheduling problems under conditions of variable demand for service over the course of an operating day and across a planning horizon. These organizations are concerned with the tour scheduling problem that involves assigning shifts and break times to the work days of employees and allocating days off to individual work schedules. Nowadays, organizations try to adopt various scheduling flexibility alternatives to meet the fluctuating service demand. On the other hand, they have also realized that providing employee productivity and satisfaction is as much important as meeting the service demand. Up to date, tour scheduling solution approaches have neglected considering employee preferences and tried to develop work schedules for employees in a subsequent step. This paper presents a goal programming model that implicitly represents scheduling flexibility and also incorporates information about the preferred working patterns of employees. After solving the proposed model, a work schedule will be generated for each employee without requiring a further step for the assignment of shifts, break times, and work days to employees. The model is capable of handling multiple scheduling objectives, and it can produce optimal solutions in very short computing times. Copyright Kluwer Academic Publishers 2004 <s> BIB009 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Bayesian forecasting models provide distributional estimates for random parameters, and relative to classical schemes, have the advantage that they can rapidly capture changes in nonstationary systems using limited historical data. Unlike deterministic optimization, stochastic programs explicitly incorporate distributions for random parameters in the model formulation, and thus have the advantage that the resulting solutions more fully hedge against future contingencies. In this paper, we exploit the strengths of Bayesian prediction and stochastic programming in a rolling-horizon approach that can be applied to solve real-world problems. We illustrate the methodology on an employee production scheduling problem with uncertain up-times of manufacturing equipment and uncertain production rates. Computational results indicate the value of our approach. <s> BIB010 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> The labor tour scheduling literature has focused on the development of schedules, and with a few exceptions, employees were assumed to have identical cost and productivity. Even the few exceptions in the literature that solved tour problems considered employees within a work group to have identical cost and productivity. In this paper we evaluated heuristics for assigning individual employees – who differed in cost and productivity – to labor tour schedules. Our results showed that considering productivity levels when assigning individuals to tours increased profitability. We found that a simple managerial heuristic of assigning individuals in descending order of their productivity to cost ratio was both fast and effective over a broad range of service environmental scenarios. Copyright Kluwer Academic Publishers 2004 <s> BIB011 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> In this paper a system for the automatic generation of shifts with breaks is presented. The problem of generating shifts with breaks appears in many areas of workforce scheduling, like in airline companies, airports, call centers etc. and is of high practical relevance. A heuristics algorithm for solving this problem is described. It is based on greedy assignment of breaks in shifts and repair steps for finding the best position of breaks inside of shifts. The commercial product in which the algorithms are included is used in practice. Computational results for a real life problem in a large European airport are given. <s> BIB012 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> In this paper a genetic algorithm based method for solving the rotating workforce scheduling problem is presented. Rotating workforce scheduling is a typical constraint satisfaction problem which appears in a broad range of workplaces (e.g. industrial plants). Solving this problem is of a high practical relevance. We propose a basic genetic algorithm for solving this problem. One mutation operator and three methods for crossover are presented. Finally we give computational results on benchmark examples from literature <s> BIB013 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper presents a new methodology for reactively scheduling nurses in light of shift-by-shift imbalances in supply and demand. In most hospitals, the nursing staff is given a midterm schedule that specifies their work assignments for up to 6 weeks at a time. However, emergencies, call-outs, and normal fluctuations in personnel requirements can play havoc with the schedule. As a result, it is necessary to make short-term adjustments, either by reallocating resources when shortages exist or by cancelling assignments when demand drops. The need to take into account individual preferences further complicates the process. The problem associated with making the daily adjustments is formulated as an Integer Program (IP) and solved within a rolling horizon framework. The idea is to consider 24 hours at a time, but to only implement the results for the first 8 hours. The IP is then re-solved for the next 24 hours after several hours have elapsed and new data are available, and so on. Initial attempts to solve 50-nurse problems with a commercial code proved to be unsuccessful and led to the development of a branch-and-price algorithm. Included in the algorithm are a feasibility heuristic to find the upper bounds and a cut generation procedure to improve the lower bound computations. A set-covering-type IP was used to find upper bounds and mixed-integer rounding cuts were used to tighten the relaxed feasible region. Although the effectiveness of all but the set covering heuristic proved to be marginal, most problem instances with up to 200 nurses were solved within 10 minutes. <s> BIB014 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Hourly changes in patient census and acuity require hospitals to update their staffing needs on a continuing basis. This paper discusses the problem that management faces several times a day as the demand for nursing services departs from the planned schedule. Prior to the start of each shift, the number of nurses who are scheduled to be on duty over the next 24 hours is compared with the number actually available, and if shortages exist a series of decisions have to be made to ensure that each unit in the hospital has sufficient coverage. These decisions involve the use of overtime, outside nurses, and floaters. To address this problem, we have developed an integer programming model that takes the current set of rosters for regular and pool nurses and the expected demand for the upcoming 24 hours as input, and produces a revised schedule that makes the most efficient use of the available resources. The model is formulated and solved at a hospital-wide level rather than for each unit separately. To determine its applicability, a representative set of scenarios was investigated using data obtained from a medium-size facility in the U.S. with 14 units. The results indicate that problem instances with up to 120 nurses can be solved in a negligible amount of time. <s> BIB015 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Regardless of the success that linear programming and integer linear programming has had in applications in engineering, business and economics, one has to challenge the assumed reality that these optimization models represent. In this paper the certainty assumptions of an integer linear program application is challenged in an attempt to improve the solution robustness in an uncertain environment. The authors resort to a two-stage, fixed recourse program to introduce random variables with a uniform distribution instead of deterministic expected values in a workforce sizing and scheduling problem. Although the solution to the problem comprises a significantly larger fulltime staff complement than that determined via the problem without the introduction of random variables, the expected workforce requirements preempt and consider the costly expense of casual workers. Key words: stochastic programming, fixed recourse, optimization, integer programming, workforce sizing, scheduling. ORiON Vol.21(1) 2005: 1-11 <s> BIB016 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> A workforce scheduling problem to schedule the minimum number of workers to perform a set of physical tasks such that their daily energy capacities are not exceeded is discussed. Firstly, a mathematical model is formulated. Two heuristics and one exact algorithm are then explained. Based on our computational experiment, a hybrid procedure consisting of the above mentioned algorithms is found to be very efficient in solving this workforce scheduling problem to optimality. <s> BIB017 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Rotating workforce scheduling is a typical constraint satisfaction problem which appears in a broad range of work places (e.g. industrial plants). Solving this problem is of a high practical relevance. In this paper we propose the combination of tabu search with random walk and min conflicts strategy to solve this problem. Computational results for benchmark examples in literature and other real life examples show that combination of tabu search with random walk and min conflicts strategy improves the performance of tabu search for this problem. The methods proposed in this paper improve performance of the state of art commercial system for generation of rotating workforce schedules. <s> BIB018 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Four heuristic algorithms based on or inspired by the well-known Tabu Search method have been used to cast heuristically optimized schedules for a clinical training unit of a hospital. It has been found experimentally that the algorithm of choice for this problem depends on the exact goal being sought where the execution time is one of the components of the goal. If only one run is allowed, then classical Tabu Search with a tenure of 5 gave the schedule with the lowest average (and fixed) penalty. If time is not of concern and many runs are allowed then the Great Deluge algorithm may generate the schedule with the lowest penalty. <s> BIB019 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> A method and apparatus for sequence control of vertical movement of slurried particulates from a lower level to the upper levels, more particularly a vertical hoist system for movement of slurry from a subterranean mine area upward through an earthen or cased borehole to a surface station. The vertical pump system includes series-connected pumps having variable speed capability to transport slurry particulate from an underground sump upward to a surface surge tank or other repository. The logic sequence system exercises control over valving sequence between the underground pumps and the vertical borehole in order to control slurry surges during start-up, shut-down and emergency dump operations. Thus, the pump input to the vertical conduit utilizes energy dissipator units as selectively controlled by automated block and by-pass valves to control flow of fluids from the pumps upward through the vertical conduit. Selective control of the dissipator units and valving enable critical start-up, shut-down and the emergency shut-down operations and this is effected by particular sequence control. <s> BIB020 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> The area of personnel scheduling is very broad. Here we focus on the ‘shift assignment problem’. Our aim is to discuss how ORTEC HARMONY handles this planning problem. In particular we go into the structure of the optimization engine in ORTEC HARMONY, which uses techniques from genetic algorithms, local optimization algorithms and variable neighborhood search. We will describe the result on an artificial test set. <s> BIB021 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Legislators at the state and national levels are addressing renewed concerns over the adequacy of hospital nurse staffing to provide quality care and ensure patient safety. At the same time, the well-known nursing shortage remains an ongoing problem. To address these issues, we reexamine the nurse scheduling problem and consider how recent health care legislation impacts nursing workforce management decisions. Specifically, we develop a scheduling model and perform computational experiments to evaluate how mandatory nurse-to-patient ratios and other policies impact schedule cost and schedule desirability (from the nurses' perspective). Our primary findings include the following: (i) nurse wage costs can be highly nonlinear with respect to changes in mandatory nurse-to-patient ratios of the type being considered by legislators; (ii) the number of undesirable shifts can be substantially reduced without incurring additional wage cost; (iii) more desirable scheduling policies, such as assigning fewer weekends to each nurse, have only a small impact on wage cost; and (iv) complex policy statements involving both single-period and multiperiod service levels can sometimes be relaxed while still obtaining good schedules that satisfy the nurse-to-patient ratio requirements. The findings in this article suggest that new directions for future nurse scheduling models, as it is likely that nurse-to-patient ratios and nursing shortages will remain a challenge for health care organizations for some time. <s> BIB022 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <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> BIB023 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <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> BIB024 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <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> BIB025 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper addresses the problem of developing cyclic schedules for nurses while taking into account the quality of individual rosters. In this context, quality is gauged by the absence of certain undesirable shift patterns. The problem is formulated as an integer program (IP) and then decomposed using Lagrangian relaxation. Two approaches were explored, the first based on the relaxation of the preference constraints and the second based on the relaxation of the demand constraints. A theoretical examination of the first approach indicated that it was not likely to yield good bounds. The second approach showed more promise and was subsequently used to develop a solution methodology that combined subgradient optimization, the bundle method, heuristics, and variable fixing. After the Lagrangian dual problem was solved, though, there was no obvious way to perform branch and bound when a duality gap existed between the lower bound and the best objective function value provided by an IP-based feasibility heuristic. This led to the introduction of a variable fixing scheme to speed convergence. The full algorithm was tested on data provided by a medium-size U.S. hospital. Computational results showed that in most cases, problem instances with up to 100 nurses and 20 rotational profiles could be solved to near-optimality in less than 20 min. <s> BIB026 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper presents a new methodology to solve the cyclic preference scheduling problem for hourly workers. The focus is on nurse rostering but is applicable to any organization in which the midterm scheduling decision must take into account a complex of legal, institutional, and preferential constraints. The objective is to strike a balance between satisfying individual preferences and minimizing personnel costs. The common practice is to consider each planning period independently and to generate new rosters at the beginning of each. To reduce some of the instability in the process, there is a growing trend toward cyclic schedules, which are easier to manage and are generally perceived to be more equitable. To address this problem, a new integer programming model is presented that combines the elements of both cyclic and preference scheduling. To find solutions, a branch-and-price algorithm is developed that makes use of several branching rules and an extremely effective rounding heuristic. A unique feature of the formulation is that the master problem contains integer rather than binary variables. Computational results are reported for problem instances with up to 200 nurses. Most were solved within 10 minutes and many within 3 minutes when a double aggregation approach was applicable. © 2006 Wiley Periodicals, Inc. Naval Research Logistics 54: 000 - 000, 2007. <s> BIB027 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Service organizations that operate outside the normal 8-hour day and face wide fluctuations in demand constantly struggle to optimize the size and composition of their workforce. Recent research has shown that improved personnel scheduling methods that take demand uncertainty into account can lead to significant reductions in labor costs. This paper addresses a staff planning and scheduling problem that arises at United States Postal Service (USPS) mail processing & distribution centers (P&DCs) and develops a two-stage stochastic integer program with recourse for the analysis. In the first stage, before the demand is known, the number of full-time and part-time employees is determined for the permanent workforce. In the second stage, the demand is revealed and workers are assigned to specific shifts during the week. When necessary, overtime and casual labor are used to satisfy demand. <s> BIB028 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Abstract Production flexibility is essential for industrial companies that have to deal with seasonal demand. Human resources are one of the main sources of flexibility. Annualising working hours (i.e., the possibility of irregularly distributing the total number of working hours over the course of a year) is a tool that provides flexibility to organizations; it enables a firm to adapt production capacity to fluctuations in demand. However, it can imply a worsening of the staff’s working conditions. To take the human aspect into account, the planning and scheduling of working time should comply with constraints derived from the law or from a collective bargaining agreement. Furthermore, new and more difficult working-time planning and scheduling problems are arising. This paper proposes a mixed-integer linear program model to solve the problem of planning the production and the working hours of a human team that operates in a multi-product process. Solving the model for different settings provides the essential quantitative information to negotiate the best conditions of the annualised hours system (the elements to establish the trade-off between weekly flexibility and economic or working-time reduction compensation can be obtained). The results achieved in a computational experiment were very satisfactory. <s> BIB029 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> In this paper we present an applied study, commissioned by the regional rail passenger carrier EuskoTren, into how the annual workload of drivers can be allocated in an egalitarian fashion. The allocation must meet the constraints arising from working conditions and the preferences of employees, as reflected in collective bargaining agreements. The workload varies over the five periods, into which the year is divided, and according to the day of the week. Moreover, not all morning, evening and night shifts are of equal duration. Reduced services on public holidays are also considered. The solution to the problem proposed is obtained in four linked steps, at each of which a binary programming problem is solved using commercial software. Step one is to build five lists of weekly multi-shift patterns, two of them rotating, that contain all the shifts in the week. Step two consists of the partially rotating annual assignment of patterns to drivers, step three involves the extraction of shifts by reduction of services on public holidays, and step four incorporates the durations in hours into the shifts already assigned. The final solution obtained is quite satisfactory: all drivers are assigned a similar number of morning, evening and night shifts and Sundays off, and they work practically the same number of days and hours per year. The results obtained, the adaptability of the system to new requirements and the computation time used are fully satisfactory to the firm, which has decided to implement the model. <s> BIB030 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper is concerned with an employee scheduling problem involving multiple shifts and work centers, where employees belong to a hierarchy of categories having downward substi- tutability. An employee at a higher category may perform the duties of an employee at a lower category, but not vice versa. However, a higher category employee receives a higher compensation than a lower category employee. For a given work center, the demand for each category during a given shift is fixed for the weekdays, and may differ from that on weekends. Two objectives need to be achieved: The first is to find a minimum-cost workforce mix of categories of employees that is needed to satisfy specified demand requirements, and the second is to assign the selected employ- ees to shifts and work centers taking into consideration their preferences for shifts, work centers, and off-days. A mixed-integer programming model is initially developed for the problem, based on which a specialized scheduling heuristic is subsequently developed for the problem. Computational results reported reveal that the proposed heuristic determines solutions proven to lie within 92-99% of optimality for a number of realistic test problems. <s> BIB031 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Constructing duty schedules for nurses at large hospitals is a difficult problem. The objective is usually to ensure that there is always sufficient staff on duty, while taking into account individual preferences with respect to work patterns, requests for leave and financial restrictions, in such a way that all employees are treated fairly. The problem is typically solved via mixed integer programming or heuristic (local) search methods in the operations research literature. In this paper the problem is solved using a tabu search approach as a case study at Stikland Hospital, a large psychiatric hospital in the South African Western Cape, for which a computerized decision support system with respect to nurse scheduling was developed. This decision support system, called NuRoDSS (short for Nurse Rostering Decision Support System) is described in some detail. <s> BIB032 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Abstract To the best of our knowledge, this paper describes the first ant colony optimization (ACO) approach applied to nurse scheduling, analyzing a dynamic regional problem which is currently under discussion at the Vienna hospital compound. Each day, pool nurses have to be assigned for the following days to public hospitals while taking into account a variety of soft and hard constraints regarding working date and time, working patterns, nurses qualifications, nurses’ and hospitals’ preferences, as well as costs. Extensive computational experiments based on a four week simulation period were used to evaluate three different scenarios varying the number of nurses and hospitals for six different hospitals’ demand intensities. The results of our simulations and optimizations reveal that the proposed ACO algorithm achieves highly significant improvements compared to a greedy assignment algorithm. <s> BIB033 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> The primary objective of the nurse scheduling problem is to ensure there are sufficient nurses on each shift. There are also a number of secondary objectives designed to make the schedule more pleasant. Neighbourhood search implementations use a weighted cost function with the weights dependent on the importance of each objective. Setting the weights on binding constraints so they are satisfied but still allow the search to find good solutions is difficult. This paper compares two methods for overcoming this problem, SAWing and Noising with simulated annealing and demonstrates that Noising produces better schedules. <s> BIB034 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper is concerned with the problem of assigning employees to gas stations owned by the Kuwait National Petroleum Corporation (KNPC), which hires a firm to prepare schedules for assigning employees to about 86 stations distributed all over Kuwait. Although similar employee scheduling problems have been addressed in the literature, certain peculiarities of the problem require novel mathematical models and algorithms to deal with the specific nature and size of this problem. The problem is modeled as a mixed-integer program, and a problem size analysis based on real data reveals that the formulation is too complex to solve directly. Hence, a two-stage approach is proposed, where the first stage assigns employees to stations, and the second stage specifies shifts and off-days for each employee. Computational results related to solving the two-stage models directly via CPLEX and by specialized heuristics are reported. The two-stage approach provides daily schedules for employees for a given time horizon in a timely fashion, taking into consideration the employees’ expressed preferences. This proposed modeling approach can be incorporated within a decision support system to replace the current manual scheduling practice that is often chaotic and has led to feelings of bias and job dissatisfaction among employees. Copyright Springer Science+Business Media, LLC 2007 <s> BIB035 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> The Royal Australian Navy's Patrol Boat Force carries out essential tasks in the surveillance, policing and defence of Australia's coastal waters. To help the Navy make efficient use of a new generation of boats, the authors have developed optimization procedures to schedule the activities of the boats and their crews. The procedures—embodied in a software system called CBM (‘Crews, Boats, Missions’)—use simulated annealing and specialized heuristic techniques within a multi-stage problem-solving framework. Tests show that CBM is reliable in terms of solution quality, and flexible with respect to the range of scheduling conditions applied. CBM has proved valuable to the Navy as an investigatory tool, and it is planned that it should be adapted for operational use, as part of a decision support system to aid in the ongoing management of patrol boat operations. <s> BIB036 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Capacity flexibility is becoming increasingly important as a means for reducing inventory while maintaining customer service levels. We examine two means to increase capacity flexibility. In particular, we examine an environment where both cross training and flexible workdays are available to respond to workload variability. Flexible workdays are under consideration in the US Legislature. This proposed legislation provides the opportunity for workers to exchange overtime for time off. From a managerial perspective, flexible workdays allow management to shift capacity from periods of light load to periods of heavy load. We simulate the operation of a job shop with both cross training and flexible workdays. Our results indicate that cross training is a far more effective tool for improving performance as compared to flexible workdays. Flexible workdays can be valuable particularly in volatile conditions. However, our results indicate that the degree of cross training is a critical consideration in determining the impact of flexible workdays. <s> BIB037 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> The min-Shift Design problem (MSD) is an important scheduling problem that needs to be solved in many industrial contexts. The issue is to find a minimum number of shifts and the number of employees to be assigned to these shifts in order to minimize the deviation from workforce requirements. <s> BIB038 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Starting from the last decade of the twentieth century, most hospital Emergency Department (ED) budgets did not keep up with the demand for ED services made by growing populations and aging societies. Since labor consumes over 50% of the total monies invested in EDs and other healthcare systems, any downsizing, streamlining and reorganization plan needs to first address staffing issues such as determining the correct size of the workforce and its work shift scheduling. In this context, it is very important to remember that downsizing certainly does not mean a general cut-across-the-board. This study shows that a selective downsizing process in which each resource is treated separately (increasing the work capacity of some resources is also possible), based on its unique contribution to the overall ED operational performance, can approximately maintain current ED operational measures in terms patient length of stay (LOS) despite an overall reduction in staff hours. A linear optimization model (S-model) and a heuristic iterative simulation based algorithm (SWSSA) are used in this study for scheduling the resources' work shifts, one resource at a time. The algorithm was tested using data that was gathered from five general hospital EDs. By leveling the workload of the different resources in the ED, SWSSA was able to achieve LOS values within -19 to 4% of the original values despite a reduction of 8-17.5% in physicians' work hours and a reduction of 13-47% in the nurses' work hours. <s> BIB039 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper presents the novel application of a collaborative population-based meta-heuristic technique called Particle Swarm Optimization (PSO) to the scheduling of home care workers. The technique is applied to a genuine situation arising in the UK, where the provision of community care service is a responsibility of the local authorities. Within this provision, optimization routes for each care worker are determined in order to minimize the distance traveled providing that the capacity and service time window constraints are not violated. The objectives of this paper are twofold; first to exploit a systematic approach to improve the existing schedule of home care workers, second to develop the methodology to enable the continuous PSO algorithm to be efficiently applied to this type of problem and all classes of similar problems. For this problem, a particle is defined as a multi-dimensional point in space which represents the corresponding care activities and assignment priority. The Heuristic Assignment scheme is specially designed to transform the continuous PSO algorithm to the discrete job schedule. The Earliest Start Time Priority with Minimum Distance Assignment (ESTPMDA) technique is developed for generating an initial solution which guides the search direction of the particle. Local improvement procedures (LIP), i.e. insertion and swap, are embedded in the PSO algorithm in order to further improve the solution quality. The proposed methodology is implemented, tested, and compared with existing solutions on a variety of real problem instances. <s> BIB040 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> With the economy continually moving towards retail and services, the size of the part-time workforce is increasing constantly. In this paper, we consider the problem of scheduling a workforce consisting entirely of part-time workers. The part-time workers have availabilities, preferences for the shifts, and also a seniority level. We propose an integer programming model to maximize employee satisfaction and to meet the demand requirements for each shift. The model is tested on randomly generated instances. The results demonstrate the effectiveness of branch-and-cut methods in reducing computation time. <s> BIB041 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper is concerned with the problem of determining the optimal size and composition of a permanent workforce needed to run a facility when demand is specified by a workstation group (WSG) for up to 24 hours a day, 7 days a week. For full-time employees, a solution is characterized by a bid job, which consists of a five-day-a-week schedule, a lunch break for all shifts, and a set of WSG task assignments for each of the half-hour periods in a shift. In contrast, each part-time employee may be given anywhere from one to six shifts during the week, and each shift may vary from four to eight hours in length. To facilitate supervision, all employees must be assigned to a home WSG, but when idle time exists in their schedules, they can be redeployed to other WSGs for a portion of the day. ::: ::: One of the complicating and unique factors addressed in this paper is the existence of nonsymmetric movement restrictions between WSGs. For example, an employee whose home base is A may be permitted to perform tasks at B, but not vice versa. Because the full problem could not be reduced to a single model, a multistage solution approach was developed. In the first stage, an extended shift-scheduling problem is solved to determine the optimal number of employees and their shifts. The results are postprocessed in subsequent stages to obtain lunch breaks, days off, and task assignments under WSG movement restrictions. ::: ::: In the implementation of the multistage approach, two alternatives were explored. The first was based on the idea of partitioning the WSGs into manageable clusters and then solving them in series. The second involved the direct solution of an integer programming formulation of the task assignment problem with home-base restrictions and WSG movement restrictions, but for a fixed workforce. An iterative scheme was used to adjust the size of the workforce until all constraints were satisfied and overall optimality was achieved. Testing was done with data provided by the U.S. Postal Service (USPS) mail processing and distribution center (P&DC) in Dallas. The computations showed that the second alternative always yielded the smaller workforce and was always able to find good solutions within 30 minutes. <s> BIB042 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> A case of selection and adaptation of weekly work schedules is presented. Weekly work schedules in two franchises of an important retail clothing chain have to be established. Working time accounts are used: each week, an employee can owe the company a certain number of hours or vice versa. Nevertheless, over a certain threshold, the hours have to be paid for by the company and the account balance returns to zero. A minimum and desired level of capacity of employees is contemplated. Hierarchically, the planned capacity must attempt to reach the minimum level; then it must fit a desired level as much as possible. At present, the task of allocation and the final adjustment of schedules is done manually, which is difficult, ineffective and often inaccurate. The procedure proposed is divided into two phases. Firstly, a work schedule, selected from a list, is assigned to each worker; a mixed linear program, followed by a local optimization process, is used. In the second phase, the work schedules are modified according to predefined rules: if there is a surplus of capacity, work schedules are reduced, and if there is a shortage, work schedules are extended. The company considers the results to be satisfactory. <s> BIB043 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper introduces a formal description and mathematical modelling of the personnel scheduling problem in the context of a paced multi-product assembly centre. The model explicitly takes into consideration the individual competencies; mobility and preferences of each worker, as well as the personnel and competency requirements associated with each assembly activity given both the current master assembly schedule and the line balancing for each product. The paper then validates and analyses the performance of the model through the optimal resolution of a small yet representative case using a commercial solver. For simplicity, we focus on the deterministic case; however the stochastic case will be discussed in the future research. <s> BIB044 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This study considers decisions in workforce management assuming individual workers are inherently different as measured by general cognitive ability (GCA). A mixed integer programming (MIP) model that determines different staffing decisions (i.e., hire, cross-train, and fire) in order to minimize workforce related costs over multiple periods is described. Solving the MIP for a large problem instance size is computationally burdensome. In this paper, two linear programming (LP) based heuristics and a solution space partition approach are presented to reduce the computational time. A genetic algorithm was also implemented as an alternative method to obtain better solutions and for comparison to the heuristics proposed. The heuristics were applied to realistic manufacturing systems with a large number of machine groups. Experimental results shows that performance of the LP based heuristics performance are surprisingly good and indicate that the heuristics can solve large problem instances effectively with reasonable computational effort. <s> BIB045 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper describes a Genetic Algorithms (GAs) approach to a manpower-scheduling problem arising at a major UK hospital. Although GAs have been successfully used for similar problems in the past, they always had to overcome the limitations of the classical GAs paradigm in handling the conflict between objectives and constraints. The approach taken here is to use an indirect coding based on permutations of the nurses, and a heuristic decoder that builds schedules from these permutations. Computational experiments based on 52 weeks of live data are used to evaluate three different decoders with varying levels of intelligence, and four well-known crossover operators. Results are further enhanced by introducing a hybrid crossover operator and by making use of simple bounds to reduce the size of the solution space. The results reveal that the proposed algorithm is able to find high quality solutions and is both faster and more flexible than a recently published Tabu Search approach. <s> BIB046 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> A common problem at hospitals is the extreme variation in daily (even hourly) workload pressure for nurses. The operating room is considered to be the main engine and hence the main generator of variance in the hospital. The purpose of this paper is threefold. First of all, we present a concrete model that integrates both the nurse and the operating room scheduling process. Second, we show how the column generation technique approach, one of the most employed exact methods for solving nurse scheduling problems, can easily cope with this model extension. Third, by means of a large number of computational experiments we provide an idea of the cost saving opportunities and required solution times. <s> BIB047 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper is concerned with the problem of assigning employees to a number of work centres taking into account employees' expressed preferences for specific shifts, off-days, and work centres. This particular problem is faced by the Kuwait National Petroleum Corporation that hires a firm to prepare schedules for assigning employees to about 86 stations distributed all over Kuwait. The number of variables in a mixed-integer programming model formulated for this problem is overwhelming, and hence, a direct solution to even the continuous relaxation of this model for relatively large-scale instances is inconceivable. However, we demonstrate that a column generation method, which exploits the special structures of the model, can readily solve the continuous relaxation of the model. Based on this column generation construct, we develop an effective heuristic to solve the problem. Computational results indicate that the proposed approach can facilitate the generation of good-quality schedules for even large-scale problem instances in a reasonable time. <s> BIB048 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> In an assembly line with high labor proportion, the workforce planning and scheduling is a very complex problem. At the background of increasing labor costs, it is very important to increase workforce efficiency. It is essential for companies to remain competitive on global markets. Increasing efficiency is our motivation to work on simulation-based workforce scheduling for complex assembly lines. In this paper, we will focus on the heuristic algorithm in our simulation-based optimization approach. The objective is workforce quantity and slack reduction. To improve the objective, an algorithm assigns the number of workers for activities, scheduled in the simulation run. We will present three different strategies implemented in these optimization algorithms. They basically use the performance indicator slack time, work center utilization and a mix of both parameters. We will compare the algorithms according to their achieved objective and the required computation time. <s> BIB049 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> We consider in this paper a project scheduling problem where resources are employees and activity requirements are time-dependent. Furthermore, employees have different skills and legal constraints dictated by the French workforce legislation have to be respected. The project has to be scheduled and employees have to be assigned to activities, so that most of the constraints are respected and the maximal lateness is minimized. We first give a linear programming formulation of the problem. Then, greedy algorithms are proposed to give an approximate solution to the problem. These methods give an initial solution to a Tabu search algorithm. Finally, computational experiments are conducted and results are discussed. <s> BIB050 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Call centers constitute growing and significant portions in national economies. This is due to the fact that the customer satisfaction has become the sole performance measure that drives the businesses today, and the call centers are the main means for companies to communicate with their customers. Additionally many public services, such as emergency and security services, cannot operate without their call centers. There is a vast body of literature on different aspects of the call center related problems. In this study, we describe a comprehensive methodology for developing staff schedules in a bilingual (Arabic and English) call center of a local telecommunication company. Our approach involves two main parts. First we obtain agent requirements in each hour across a week. In this part we use data analysis, a queuing approximation, and a simulation model. The second part is about constructing optimization models for scheduling agents. We utilize two models; one for the case with no flexible workers, and another for the case with flexible workers. We include numerical experiments and analysis at the end to show the schedule optimization results under several scenarios. <s> BIB051 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> We consider a call center staffing problem with two types of costumers of which the arrival rates are allowed to be a random and non-stationary. In order to efficiently cope with such random workload fluctuations, the workforce presents some flexibility: the agents can be, in real-time, affected to each type of customers according to the instantaneously observed workload and the associated/relative cost criteria. We model this staffing problem as a cost optimization-based newsboy-type model. We then show how to numerically solve this model. In order to deal with the randomness characterizing the workloads of the call processes, we consider several solution tracks. First, we solve the model under the assumption that the workloads are deterministic and equal to their average values. In the second approach, we explicitly formulate in the optimization model the stochastic nature of the workloads. As a third approach, we develop a robust-type solution. Via several numerical analyzes we show the impact of the arrival rates randomness on the optimal staffing policy and on the operating costs. <s> BIB052 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper presents an integrated mixed integer linear programming (MILP) model for determining manpower requirements and related personnel shift designs for the build-up and break-down of the unit load devices (ULDs) at the air cargo terminal to minimize manpower costs. To utilize the manpower resources efficiently, we implement a new mechanism for demand leveling. In addition, we consider the qualification hierarchy between build-up and break-down workers. A case study based on the real-life data shows that the model is useful for manpower planning at air cargo terminals and the integrated approach is far superior to a traditional two-stage approach. <s> BIB053 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <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> BIB054 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper presents a multi-agent-based approach for personnel scheduling problems in the context of a paced multi-product assembly center. Our purpose is to elaborate daily assignment of employees to workstations in order to minimize simultaneously the operational costs and personnel dissatisfactions. The proposed approach considers the individual competencies, mobility and preferences of each employee, as well as the personnel and competency requirements associated with each assembly activity given both the current master assembly schedule and the line balancing for each product. To benchmark the performance of the multi-agent approach, we use optimal solutions obtained through a linear programming model resolution using a commercial solver. Experimental results show that our multi-agent approach can produce high-quality and efficient solutions in a short computational time. <s> BIB055 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> We address a multi-category workforce planning problem for functional areas located at different service centres, each having office-space and recruitment capacity constraints, and facing fluctuating and uncertain workforce demand. A deterministic model is initially developed to deal with workforce fluctuations based on an expected demand profile over the horizon. To hedge against the demand uncertainty, we also propose a two-stage stochastic program, in which the first stage makes personnel recruiting and allocation decisions, while the second stage reassigns workforce demand among all units. A Benders’ decomposition-based algorithm is designed to solve this two-stage stochastic mixed-integer program. Computational results based on some practical numerical experiments are presented to provide insights on applying the deterministic versus the stochastic programming approach, and to demonstrate the efficacy of the proposed algorithm as compared with directly solving the model using its deterministic equivalent. <s> BIB056 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper investigates an adaptive constructive method for solving nurse rostering problems. The constraints considered in the problems are categorised into three classes: those that are sequence related, those that are nurse schedule related and those that are roster related. We propose a decomposition approach (to construct solutions) that consists of two stages: (1) to construct high quality sequences for nurses by only considering the sequence constraints, and (2) to iteratively construct schedules for nurses and the overall rosters, based on the sequences built and considering the schedule and roster constraints. In the second stage of the schedule construction, nurses are ordered and selected adaptively according to the quality of the schedules they were assigned to in the last iteration. Greedy local search is carried out during and after the roster construction, in order to improve the (partial) rosters built. We show that the local search heuristic during the roster construction can further improve the constructed solutions for the benchmark problems tested. ::: ::: In addition, we introduce new benchmark nurse rostering datasets which are based upon real world data. The data sets represent a variety of real world constraints. The publication of this problem data to the research community is aimed at closing the gap between theory and practice in nurse scheduling research. One of the main objectives is to encourage more research on these data sets. <s> BIB057 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> The challenge in shift scheduling lies in the construction of a set of work shifts, which are subject to specific regulations, in order to cover fluctuating staff demands. This problem becomes harder when multi-skill employees can perform many different activities during the same shift. In this paper, we show how formal languages (such as regular and context-free languages) can be enhanced and used to model the complex regulations of the shift construction problem. From these languages we can derive specialized graph structures that can be searched efficiently. The overall shift scheduling problem can then be solved using a Large Neighbourhood Search. These approaches are able to return near optimal solution on traditional single activity problems and they scale well on large instances containing up to 10 activities. <s> BIB058 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper presents a profit-oriented shift scheduling approach for inbound contact centers. The focus is on systems in which multiple agent classes with different qualifications serve multiple customer classes with different needs. We assume that customers are impatient, abandon if they have to wait, and that they may retry. A discrete-time modeling approach is used to capture the dynamics of the system due to time-dependent arrival rates. Staffing levels and shift schedules are simultaneously optimized over a set of different approximate realizations of the underlying stochastic processes to consider the randomness of the system. The numerical results indicate that the presented approach works best for medium-sized and large contact centers with skills-based routing of customers for which stochastic queueing models are rarely applicable. <s> BIB059 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> A methodology is presented to solve the flexible shift scheduling problem of physicians when hospital administrators can exploit flexible start times, variable shift lengths, and overtime to cover demand. The objective is to minimize the total assignment cost subject to individual contracts and prevailing labor regulations. A wide range of legal restrictions, facility-specific staffing policies, individual preferences, and on-call requirements throughout the week are considered. The resulting model constructs shifts implicitly rather than starting with a predefined set of several shift types. To find high-quality rosters, a Branch-and-Price (B&P) algorithm is developed that uses two different branching strategies and generates new rosters as needed. The first strategy centers on the master problem variables and the second is based on the subproblem variables. Using data provided by an anesthesia department of an 1100-bed hospital as well as an extensive set of randomly generated test instances for 15 and ... <s> BIB060 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Although optimal staff scheduling often requires elaborate computational methods, those cases which are not highly constrained can be efficiently solved using simpler approaches. This paper describes how a simple procedure, combining random and greedy strategies with heuristics, has been successfully applied in a Spanish hospital to assign guard shifts to the physicians in a department. In this case, the employees prefer that their guard duties are regularly distributed in time. The workload distribution must also satisfy some constraints: in particular, the distribution of duties among the staff must be uniform when a number of tasks and shift types (including some unfrequent and aperiodic types, such as those scheduled during long weekends) are considered. Furthermore, the composition of teams should be varied, in the sense that no particular pairing should dominate the assignments. The procedure proposed is able to find suitable solutions when the number of employees available for every task is not small compared to the number required at every shift. The software is distributed under the terms of the GNU General Public License. <s> BIB061 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Hospital wards need to be staffed by nurses round the clock, resulting in irregular working hours for many nurses. Over the years, the nurses’ influence on the scheduling has been increased in order to improve their working conditions. In Sweden it is common to apply a kind of self-scheduling where each nurse individually proposes a schedule, and then the final schedule is determined through informal negotiations between the nurses. This kind of self-scheduling is very time-consuming and does often lead to conflicts. We present a pilot study which aims at determining if it is possible to create an optimisation tool that automatically delivers a usable schedule based on the schedules proposed by the nurses. The study is performed at a typical Swedish nursing ward, for which we have developed a mathematical model and delivered schedules. The results of this study are very promising and suggest continued work along these lines. <s> BIB062 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> The benefits of automating the nurse scheduling process in hospitals include reducing the planning workload and associated costs and being able to create higher quality and more flexible schedules. This has become more important recently in order to retain nurses and to attract more people into the profession. Better quality rosters also reduce fatigue and stress due to overwork and poor scheduling and help to maximise the use of leisure time by satisfying more requests. A more contented workforce will lead to higher productivity, increased quality of patient service and a better level of healthcare. This paper presents a scatter search approach for the problem of automatically creating nurse rosters. Scatter search is an evolutionary algorithm, which has been successfully applied across a number of problem domains. To adapt and apply scatter search to nurse rostering, it was necessary to develop novel implementations of some of scatter search's subroutines. The algorithm was then tested on publicly available real-world benchmark instances and compared against previously published approaches. The results show the proposed algorithm is a robust and effective method on a wide variety of real-world instances. <s> BIB063 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Purpose – The purpose of this paper is to propose a bicriteria integer programming model for hierarchical workforce scheduling in which the first criterion is the cost and the second is the suitability of task assignment to individual employees. The model is based on the integer programming formulation for the hierarchical workforce scheduling problem published in 2007 by Seckiner et al., which extends the model proposed by Billionnet in 1999.Design/methodology/approach – The principal hypothesis of this paper is that, although an employee is capable of performing several different tasks with equal efficiency, the type of task to which he/she is assigned affects the overall suitability of the assignment configuration. Therefore, cost‐minimising solutions should also optimise task assignment when possible. This paper considers real cases and confirm that this approach to the problem is appropriate for dealing with common situations in personnel management.Findings – The proposed idea is applied to the exam... <s> BIB064 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> In this article, we present strategies to help combat the U.S. nursing shortage. Key considerations include providing an attractive work schedule and work environment—critical issues for retaining existing nurses and attracting new nurses to the profession—while at the same time using the set of available nurses as effectively as possible. Based on these ideas, we develop a model that takes advantage of coordinated decision making when managing a flexible workforce. The model coordinates scheduling, schedule adjustment, and agency nurse decisions across various nurse labor pools, each of differing flexibility levels, capabilities, and costs, allowing a much more desirable schedule to be constructed. Our primary findings regarding coordinated decision making and how it can be used to help address the nursing shortage include (i) labor costs can be reduced substantially because, without coordination, labor costs on average are 16.3% higher based on an actual hospital setting, leading to the availability of additional funds for retaining and attracting nurses, (ii) simultaneous to this reduction in costs, more attractive schedules can be provided to the nurses in terms of less overtime and fewer undesirable shifts, and (iii) the use of agency nurses can help avoid overtime for permanent staff with only a 0.7% increase in staffing costs. In addition, we estimate the cost of the shortage for a typical U.S. hospital from a labor cost perspective and show how that cost can be reduced when managers coordinate. <s> BIB065 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> We consider the problem of simultaneously scheduling IT-projects and assigning multi-skilled internal and external human resources with resource-specific efficiencies to the project work. The objective is to minimize labor costs. The problem is modeled as a mixed-integer linear program (MIP) with a tight LP-bound. The performance of the model w.r.t. solution gap and computation time is assessed and managerial insight is given concerning different problem parameters such as the time window size of projects, the number of skills of human resources, and the workload. Furthermore, we show the benefit of applying the MIP compared to simple heuristics used in practice in terms of obtaining feasible and low-cost solutions. Finally, we provide insight into the benefit of applying the MIP in case of central compared to decentral planning. <s> BIB066 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This paper presents a case study commissioned by the Spanish railway carrier Ferrocariles Espanoles de Via Estrecha for the annual rostering of work schedules for station personnel. A mixed rostering process is used. The first part of the process is carried out manually with the aid of a spreadsheet and Visual Basic, and consists of designing an initial graphic with 4-week patterns for each station, assigning those patterns in a rotating schedule over the year and factoring in vacation time. The second part consists of assigning relief shifts to cover those shifts left vacant in such a way as to minimize the distance travelled by personnel from other stations brought in for relief shift duty. To that end, basic programmes are designed using binary programming and a 4-week time frame. The results obtained are a clear improvement on the system previously used at FEVE and the company has decided to implement the model. <s> BIB067 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> In this paper we propose a mathematical model to manage a Service Center (SC) which is based on a system of ordinary differential equations. By resorting to this model, the manager of the SC can design planning strategies to satisfy customer orders, under strict deadlines and human resource constraints. After describing the model, we introduce criteria which optimize the processing time and supply a more accurate description of working behavior. Finally, we conclude presenting some numerical simulations which demonstrate the usefulness of the proposed model to reach correct decisions in managing a SC. <s> BIB068 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Employee empowerment is a flexible management concept. As in traditional scheduling, the employer is still in charge of assigning jobs to staff. However, employees are allowed to express their preferences for the jobs they want to do. The hope is that empowerment will improve morale, which will improve productivity. The challenge is to design such an empowerment scheduling system without undesirable outcomes. <s> BIB069 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> In this paper, a Harmony Search Algorithm (HSA) is adapted for Nurse Rostering Problem (NRP). HSA is a global optimization method derived from a musical improvisation process which has been successfully tailored for several optimization domains. NRP is a hard combinatorial scheduling problem of assigning given shifts to given nurses. Using a dataset established by International Nurse Rostering Competition 2010 of sprint dataset that has 10-early, 10-late, 10-hidden, and 3-hint. The proposed method achieved competitively comparable results. <s> BIB070 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> In this paper we deal with shift scheduling of tank trucks for a small oil company. Given are a set of tank trucks with different characteristics and a set of drivers with different skills. The objective is to assign a feasible driver to every shift of the tank trucks such that legal and safety restrictions are satisfied, the total working times of the drivers are within desired intervals, requested vacation of the drivers is respected and the trucks are assigned to more favored drivers. We propose a two-phase solution algorithm which is based on a mixed integer linear programming formulation and an improvement procedure. Computational results are reported showing that the algorithm is able to generate feasible schedules in a small amount of time. <s> BIB071 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> The personnel scheduler constructs a deterministic personnel roster that determines the line-of-work for each personnel member. When unexpected events disrupt this roster, the feasibility needs to be restored by constructing a new workable roster. The scheduler must reassign the set of employees in order to cover the disrupted shift such that the staffing requirements and the time-related personnel constraints remain satisfied. In this paper, we propose an evolutionary meta-heuristic to solve the nurse rerostering problem. We show that the proposed procedure performs consistently well under many different circumstances. We test different optimisation strategies and compare our procedure with the existing literature on a dataset that is carefully designed in a controlled and varied way. <s> BIB072 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> The problem is related to a fleet of military aircraft with a certain flying program in which the availability of the aircraft sufficient to meet the flying program is a challenging issue. During the pre- or after-flight inspections, some component failures of the aircraft may be found. In such cases, the aircraft are sent to the repair shop to be scheduled for maintenance jobs, consisting of failure repairs or preventive maintenance tasks. The objective is to schedule the jobs in such a way that sufficient number of aircrafts is available for the next flight programs. The main resource, as well as the main constraint, in the shop is skilled-workforce. The problem is formulated as a mixed-integer mathematical programming model in which the network flow structure is used to simulate the flow of aircraft between missions, hanger and repair shop. The proposed model is solved using the classical Branch-and-Bound method and its performance is verified and analyzed in terms of a number of test problems adopted from the real data. The results empirically supported practical utility of the proposed model. <s> BIB073 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <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> BIB074 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> In this paper we study the problem of personnel planning in care-at-home facilities. We model the system as a Markov decision process, which leads to a high-dimensional control problem. We study monotonicity properties of the system and derive structural results for the optimal policy. Based on these insights, we propose a trunk reservation heuristic to control the system. We provide numerical evidence that the heuristic yields close to optimal performance, and scales well for large problem instances. <s> BIB075 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> In the Home Care Crew Scheduling Problem a staff of home carers has to be assigned a number of visits to patients’ homes, such that the overall service level is maximised. The problem is a generalisation of the vehicle routing problem with time windows. Required travel time between visits and time windows of the visits must be respected. The challenge when assigning visits to home carers lies in the existence of soft preference constraints and in temporal dependencies between the start times of visits. <s> BIB076 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> This research addresses a shift scheduling problem in which physicians are assigned to demand periods. We develop a reduced set covering approach that requires shift templates to be generated for a single day and compare it to an implicit modeling technique where shift-building rules are implemented as constraints. Both techniques allow full flexibility in terms of different shift starting times and lengths as well as break placements. The objective is to minimize the paid out hours under the restrictions given by the labor agreement. Furthermore, we integrate physician preferences and fairness aspects into the scheduling model. Computational results show the efficiency of the reduced set covering formulation in comparison to the implicit modeling approach. <s> BIB077 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Nurse rostering is an NP-hard combinatorial problem which makes it extremely difficult to efficiently solve real life problems due to their size and complexity. Usually real problem instances have complicated work rules related to safety and quality of service issues in addition to rules about quality of life of the personnel. For the aforementioned reasons computer supported scheduling and rescheduling for the particular problem is indispensable. The specifications of the problem addressed were defined by the First International Nurse Rostering Competition (INRC2010) sponsored by the leading conference in the Automated Timetabling domain, PATAT-2010. Since the competition imposed quality and time constraint requirements, the problem instances were partitioned into sub-problems of manageable computational size and were then solved sequentially using Integer Mathematical Programming. A two phase strategy was implemented where in the first phase the workload for each nurse and for each day of the week was decided while in the second phase the specific daily shifts were assigned. In addition, local optimization techniques for searching across combinations of nurses’ partial schedules were also applied. This sequence is repeated several times depending on the available computational time. The results of our approach and the submitted software produced excellent solutions for both the known and the hidden problem instances, which in respect gave our team the first position in all tracks of the INRC-2010 competition. <s> BIB078 </s> Personnel scheduling: A literature review <s> Constraints, performance measures and flexibility <s> Every company that has employees working on irregular schedules must deal with the difficult and time consuming problem of creating feasible schedules for the employees. We introduce an algorithm that takes a partial schedule created by requests from employees and creates feasible schedule where most of the employee’s requests are unchanged, while still making sure that rules and regulations are not violated. The algorithm is based on independent modules, which can be executed in any order, and each module tries to emulate some action taken by a staff manager. <s> BIB079
In this section, we classify the variety of constraints that appear in personnel scheduling problems. If possible, we distinguish between hard and soft constraints per category. The different categories are coverage, time-related, and fairness and balance constraints. In addition, the flexibility which allows the user to cope with these constraints, is discussed. Table 5 lists the coverage constraints. With a presence at a level of almost 75%, the hard coverage constraint is the key characteristic of personnel scheduling problems. The coverage constraint is also one of the most popular soft constraints in personnel scheduling problems. This is straightforward, since an important aspect of personnel scheduling problems is deciding on the number of employees needed to cover the workload. Therefore, some papers are listed twice in the table: the hard constraint ensure that enough workers are available during each time period, whereas the objective function minimizes the total workforce.   BIB023 BIB052 BIB024 BIB074 BIB025  BIB068  BIB041 When focusing on capacity as a soft constraint or performance measure, the difference from the optimal or minimal capacity is typically of interest. Bard and Purnomo have written a number of papers on the nurse scheduling problem BIB014 BIB002 BIB026 BIB027 . They define the workload demand as a lower and upper limit on the number of nurses needed per shift. Because of nationwide staff shortages, they assume it would be unusual to be able to cover all demand. Therefore, gaps in the schedule could be filled by (limited) outside resources. One objective is to generate a set of rosters that minimizes the number of uncovered shifts over the planning horizon (i.e., the cost of filling gaps with outside nurses). Nissen and Günther [141-143, 219, 220] consider coverage constraints as a set of soft constraints. When a discrepancy arises from the workstation staffing target, error points are generated for the duration and size of the erroneous assignment based on the error point size. They distinguish different types of errors for overstaffing and understaffing demand. When researchers classify coverage constraints as hard constraints, understaffing is not allowed. This does not mean that workforce demand has to be met exactly: one can still schedule some excess staff to deal with unexpected demand, etc. Table 6 lists the papers in a matrix according to the flexibility of the operator with respect to tackling coverage constraints. Table 6 indicates that the manuscripts are quite evenly distributed over the different alternatives, except for the case where understaffing is allowed and overstaffing is not, which is addressed in only one paper. In this exceptional paper, White et al. BIB019 evaluate heuristic algorithms used to produce duty rosters for medical trainees (residents and medical students) to man the overnight shift. Ideally, exactly 5 members are present, but for financial reasons only 4 or 3 may actually be scheduled. When the personnel can be classified into different skill categories, a hard constraint is mostly added to ensure the presence of a number of workers per skill needed during a specific period. The necessity of a specific skill can be modeled either as a hard or a soft constraint (Table 7 ). In the case of a soft constraint, people with other skills could take over when there is a lack of employees with the right skill, which penalizes the objective value. In the nurse scheduling problem of Brucker et al. BIB057 constructing shift sequences for each nurse of different skills is considered a hard constraint. However, "alternative skills" are considered a soft constraint, if a nurse is able to cover a shift but prefers not to, since it does not require his/her primary skill. We distinguish between three groups with respect to the extent to which skills are considered flexible ( Table 8 ). The first group consists of skills that are user definable. In this case the scheduler has the freedom to define skills for every personnel member in the set. This could be the case when the company has the ability to easily hire (or train) employees with these specific skills. Extra constraints could limit the number of people with a specific skill or enforce a minimum on a set. The second group concerns problems with a hierarchical workforce. In this case, employees classified in a higher category are able to carry out the tasks of lower ranked employees, but not vice versa. In this way, companies could differentiate based on educational background, training and experience, junior and senior employees, etc. Generally, employees in a higher classified category receive a greater level of compensation than employees in a lower classified category. Examples can be found in hospitals, where schedules have to satisfy demand for a given number of nurses with different grades  or students have to be scheduled together with nurses or physicians BIB019 . Hierarchical workforce applications do not only arise in health care. Rong and Grunow BIB053 consider a qualification hierarchy when scheduling freight handling personnel at air cargo terminals and Li et al. BIB023 propose an integrated (hierarchical) staff-sizing approach considering the feasibility of scheduling decisions for service organizations. In the last group, skills cannot be substituted. Tasks or jobs that need specific skills can only be covered by workers with those skills. Nevertheless, it is possible for workers to be cross-trained. As Table 7 and Table 8 show, skills are well-incorporated into personnel scheduling problems. In most papers, those skills are fixed, i.e., one cannot train or learn extra skills. The focus on hard constrained fixed skills does not reflect reality. Skills are too often considered as an input. Researchers should try to take advantage of a skills setting, by deciding on the assignment of (multiple) skills to workers at a certain training cost. The coverage constraints could be defined in a way to incorporate breaks. In his model, Dantzig BIB001 created the possibility of adding meal breaks to every distinct shift schedule. Now, more than half a century later, scheduling breaks are often omitted from personnel scheduling problems (Table 8) . A distinction can be made between the assignment of (long) meal breaks and (short) rest breaks. Quimper and Rousseau BIB058 , for example, schedule a rest break, a lunch break and another rest break for every work shift of a full-time employee. The timing of breaks is usually limited. Often a predefined time window is set, based on the starting and finishing hours of the employee's working shift (see for instance BIB028 BIB042 ). Both papers also differentiate between full-and part-time workers. Part-time workers only need a meal break if their shift length exceeds a certain threshold whereas full-time workers always need a break. Thompson and Pullman [273] present a paper in which the break assignment not only restrains the schedule possibilities, but actually forms the topic of the paper. They found that only 18% of the 64 papers they surveyed scheduled rest breaks or reliefs. The objective of their paper is to try to determine whether reliefs should be scheduled in advance (which confronts researchers with a growth in problem complexity) or scheduled in real-time (which permits researchers to continue to avoid scheduling reliefs). Scheduling reliefs in advance results in more costly schedules, but (according to the authors) will have undesirable outcomes such as a less profitable deployment of labor and a less productive workforce when some reliefs cannot be given. A third negative consequence can occur when scheduling relief breaks in real-time. These real-time schedule adjustments should be incorporated into the procedures developed by the researchers, as adjustments made by experienced managers are generally less profitable than adjustments made by computer-based heuristics. The flexibility alternatives discussed in this section are not exhaustive. The use of overtime also has an impact on the flexibility of the operator in dealing with coverage constraints. When scheduling overtime is allowed, a relation exists between assigning extra hours to employees and hiring a new employee (when possible). This relationship depends on the extra cost of overtime on top of the wage, the upper limit on the number of hours per day and/or per week per employee, etc. Instead of limiting the number of work hours by week, one could also use annualized hours or working time accounts BIB003 BIB004 BIB005 BIB043 . This way, the operator keeps track of the number of hours a specific employee has worked during the past period (month, year, …). This gives the operator more flexibility in scheduling employees, since one can compensate for weeks when demand and thus workload is high without having to pay for expensive overtime or to hire new (part-time) workers. Other factors of interest are the possibility of hiring interim or casual workers, outsourcing, etc. The category of financial measures entails different costs (Table 9) , such as personnel cost (regular wages), a cost depending on the day of the week (e.g., increased wage for weekend days), different cost per skill category (e.g., greater remuneration for a highly-skilled workforce), overtime cost, outsource cost, travel cost, cost or profit derived from carrying out various tasks and other costs. Minimizing personnel cost is closely related to minimizing the number of employees, but has more possibilities. When using personnel cost rather than the explicit number of employees, one can make a trade-off between hiring employees, overtime, casual workers, etc., by assigning a (relative) cost to all of these factors. The wider range of possibilities contributes to the popularity of this latter performance measure compared to the minimization of the number of employees. Helber and Henken BIB059 present a profit-oriented shift scheduling approach for inbound contact centers. The realized profit is influenced by the wage of the agents of a certain class working a specific shift (i.e., day and skill dependent), the line cost per period for a customer in the system (other costs) and the revenue for each processed customer (cost of carrying out tasks). Another example of incorporating multiple labor expenses is given by Brunner et al. BIB060 . They present a methodology to solve the flexible shift scheduling problem of physicians. The objective is to minimize the total assignment cost subject to individual contracts and prevailing labor regulations. The total assignment cost addressed in dealing with this problem consists of paid out time, planned overtime and the use of outside resources to cover shortfalls in coverage. Chen et al. [85] explicitly charge costs, on top of the crew salary and regular manpower cost per man-hour for different departments, for any surplus man-hour supply exceeding demand. Similarly, a cost is added for every temporary man-hour supply provided in order to deal with insufficient manpower for the departments. The authors do not restrict themselves to the costs we have discussed so far. Bagatourova BIB006 , for instance, offers the possibility of adding penalty costs for missed deadlines. Li et al. BIB023 incorporate hiring costs when employing extra workers. In addressing their personnel scheduling problem for assembly lines, Sabar et al. BIB044 allow workers to move between workstations in order to fulfill specific assembly tasks. The proposed approach also considers the possibility of assigning employees to secondary activities, which could generate net revenue, when the employees are not assigned to an assembly workstation. Other costs are for example production costs BIB029 , costs of missing calls BIB052 or missed production BIB045 , training costs BIB045 , different costs for a full-time or part-time employee BIB054 , rejection costs BIB075 , different costs per location BIB014 , etc. In personnel scheduling problems, the operators often want to create fairness in the work environments for different workers. Therefore, they try to balance dissimilarities between the workers. Table 10 lists the papers that incorporate balancing constraints. Most papers model these balancing constraints as soft constraints, except for BIB061 and BIB062 . Lucic and Teodorovic BIB025 develop a metaheuristic approach to the aircrew rostering problem. In their model they want to minimize the average relative deviation (per crew member) of the real monthly flight time from the ideal. Other balance constraints involve an equal number of weekend days spent outside the home, an equal number of departures before 7 A.M., etc. Lezaun et al. BIB030 balance between workers and between shifts when rostering employees in a rail passenger network. On the one hand, they want to distribute a driver's morning, evening and night shifts and Sundays off evenly over the year. On the other hand, shifts should be distributed in an egalitarian fashion. At the end of the year, drivers should have been assigned a similar number of working days and hours, morning, evening and night shifts and Sundays off. Besides balancing the workload, the time between consecutive assignments or the number of assignments to a specific shift, one could also consider balancing the treatment of employee preferences. In the multiple shift scheduling problem of a hierarchical workforce with multiple work centers of Al-Yakoob and Sherali BIB031 , the employees expressed preferences for specific shifts, work centers and weekly off-days. They formulate a mixed integer programming model that determines a minimum-cost workforce mix of the categories of employees needed to satisfy the specified demand requirements and to assign the selected employees to shifts and work centers while specifying their off-days based on their stated preferences. BIB046 BIB069 BIB079 BIB070 BIB015 BIB047 BIB032  BIB057  BIB063  BIB020  BIB007 BIB033 BIB071  BIB074  BIB072  BIB064 BIB076 BIB008 BIB055 BIB044 BIB077 BIB034 BIB009 BIB078 BIB021 BIB065 BIB022 The granted personnel requests are not only being balanced, they could also come as separate soft constraints. A willingness of working together with (or separate from) a specific worker, the difference to preferred work duration, preferences towards a specific work location, days or shifts, etc., are examples of such preference constraints (Table 11) . The idea of using time-related constraints rather than categorizing the constraint according to a tour scheduling or shift scheduling classification, originates from Brucker et al. BIB057 , when representing all the constraints that appeared when introducing benchmarks in dealing with the nurse scheduling problem. They created a number of problem instances, with different subsets of these constraints. One way of making the schedule attractive to workers is to limit the number of assignments per day (e.g., the number of jobs done per day, which comes down to limiting the number of switches per worker) or per week (typically the number of active shifts per week is limited). Instead of limiting the number of assignments, often a minimum number of consecutive free days is enforced (for instance BIB035 BIB048 BIB036 ). Since the maximum number of hours that an employee is allowed to work per week is typically limited by regulations, this measure is actually applied to avoid employees being scheduled for many short shifts. In order to ensure a minimum variation in a worker's shift pattern, a constraint can be set on the number of assignments to a specific day or shift. Organizations frequently impose limits on the number of consecutive working and non-working shifts. The lower limit of consecutive (non-)working shifts ensures that workers do not have to switch too often from working to non-working patterns. This lower limit is mainly used to avoid the existence of a single working shift between two non-working shifts (or a single non-working shift between two working shifts), which is considered undesirable by the personnel. Another constraint based on consecutiveness is a maximum number of consecutive assignments to the same shift type. The most popular time-related soft constraints are those that consider consecutive (non-) working shifts. Whereas a measure such as the maximum number of hours worked is usually dictated by official regulations (i.e., hard constraints), the modification of the maximum and minimum number of consecutive shifts is less restricted. When doing so, one has to take into account employee satisfaction, as the minimum number of consecutive working and non-working shifts is related to single stand-alone shifts, which are considered undesirable. Aside from official regulations, organizations themselves can also impose hard constraints on the (regular) number of hours an employee is allowed to work per day or/and per week/month. If regular work hours do not suffice to cover all the workload, the organizations can switch to overtime, but the use of overtime is often restricted. In the personnel scheduling problem at USPS mail processing and distribution centers of Bard et al. [34-36, 40, 41, 238, 291] , for instance, the use of overtime is restricted to 6% of the total number of hours worked. Days on/off and shifts on/off refer to problems where the workers have announced that they will not be available on specific days/shifts (i.e., the label "Days off" addresses the papers in which the user is asked to deliberately consider holidays of the personnel or requests for days off, which is a restriction on assigning an employee to a specific day, whereas "Max # consecutive days off" considers the regular rest days after a working period). With this in mind, the scheduler has to consider other workers to solve the coverage problems. When a worker has to change from one shift type to another, one has to make sure that the specific pattern is allowed. When a worker works late one day, (s)he will not be thrilled to start early the next day and one wants to ensure a minimum rest time between assignments. For this reason, some shift type successions will not be tolerated. These restrictions can be modeled by allowing the user to choose from a predefined set of patterns, by prohibiting certain shift sequences, by ensuring a minimum time between consecutive assignments or shifts, etc. Weekends are quite important for workers and organizations have to be thoughtful when scheduling weekend days. The most popular of the set of weekend constraints is the creation of complete weekends. Employees prefer to work one full weekend with the knowledge they have another weekend off, rather than working two weekends for a single day. Another constraint is the limit set upon the number of allowable weekends within a planning period, and even the number of consecutive weekends could be restricted. Knust and Schumacher BIB071 combine the complete weekend constraint with the restriction that no single active shift is allowed in the shift scheduling for tank trucks. When a worker has Tuesday off, (s)he is not allowed to work on Monday, i.e., an enlarged weekend off is enforced. Task are often scheduled by adding hard or soft constraints that create a time window during which the execution is allowed. One could also add a soft constraint to minimize the makespan or to make sure that all jobs are finished before a given deadline. Workers or jobs may require specific resources, which are not always available. Zhu and Sherali BIB056 have to schedule workers on the basis of a limited number of desks. In other scheduling instances, restrictions correspond to the number of resources BIB049 , the number of machines BIB010 , the available tools BIB016 , etc. A special constraint is used in the personnel scheduling approach of Yaoyuenyong and Nanthavanij BIB017 which emphasizes the health and safety issues of workers. Depending on the energy costs of required tasks, the number of workers who can be safely assigned to perform the tasks on a rotational basis might have to be greater than the number of tasks. The energy-based personnel scheduling arrangement is intended to find the minimum number of workers and their daily work assignments such that their working energy capacities are not exceeded. In some situations, ratios between groups of workers are added as a constraint to make sure that the relative share of the workforce does not become too large. In the nurse scheduling problem of Wright and Bretthauer BIB065 , the number of float nurses is restricted as compared to the regular workforce. Heimerl and Kolisch BIB066 add a constraint to ensure that a minimum ratio exists between the work performed by internal and by external resources. Besides minimizing crew costs and ensuring fairness to all regular crew members regarding the workload, the aircrew rostering problem in Maenhout and Vanhoucke  also takes into account crew members' preferences for certain roster attributes. The crew members not only express their preferences for specific pairings and reserve duties, but also for more general scheduling preferences such as the moment (day/time) they want to be scheduled. Aside from the soft constraints or performance measures illustrated so far, researchers have defined many others, such as the minimization of the possibility of getting injured from doing a specific job sequence  , profit maximization BIB059 , the maximization of the net present value BIB011 , the minimization of the (mean) lateness of the completion of tasks BIB050 BIB037 , minimizing the permitted number of distinct shift types   BIB038 BIB012 BIB013 BIB018 , maximizing employee satisfaction BIB007 , minimizing service criteria (e.g., waiting time and probability of waiting in a call center environment BIB051 , length of stay of patients in a hospital BIB039 ), minimizing travel distance BIB040 BIB067 , maximizing fleet availability BIB073 , etc. It is noteworthy that most authors develop a multi-objective model for the personnel scheduling problem. When developing a personnel schedule, one has to consider a group of stakeholders, each with their own priorities. The organization itself, for instance, wants to cover the workload at minimum cost. The operations manager could insist on limiting the number of casual workers to ensure continuity and the availability of knowhow. The importance of every priority has to be determined in order to combine them all into one objective function by assigning a weight factor to all of them. In this section, we have shown that personnel scheduling problems come in many variations regarding the hard and soft constraints. The effect of those constraints on the complexity, however, has barely been studied. Brucker et al.  present mathematical models which cover specific aspects in the personnel scheduling literature and address complexity issues by identifying polynomial solvable and NP-hard special cases. Nevertheless, the effect on the complexity of many characteristics is still unclear. We think a dedicated theoretic exploration benefits the development of well-suited algorithms to deal with the numerous constraints.