Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB001 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> We describe a method to find low cost shift schedules with a time-varying service level that is always above a specified minimum. Most previous approaches used a two-step procedure: (1) determine staffing requirements and (2) find a minimum cost schedule that provides the required staffing in every period. Approximations in the first step sometimes cause the two-step approach to find infeasible or suboptimal solutions. Our method iterates between a schedule evaluator and a schedule generator. The schedule evaluator calculates transient service levels using the randomization method and identifies infeasible intervals, where the service level is lower than desired. The schedule generator solves a series of integer programs to produce improved schedules, by adding constraints for every infeasible interval, in an attempt to eliminate infeasibility without eliminating the optimal solution. We present computational results for several test problems and discuss factors that make our approach more likely to outperform previous approaches. <s> BIB002 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Abstract This paper presents a review of staff scheduling and rostering, an area that has become increasingly important as business becomes more service oriented and cost conscious in a global environment. Optimised staff schedules can provide enormous benefits, but require carefully implemented decision support systems if an organisation is to meet customer demands in a cost effective manner while satisfying requirements such as flexible workplace agreements, shift equity, staff preferences, and part-time work. In addition, each industry sector has its own set of issues and must be viewed in its own right. There are many computer software packages for staff scheduling, ranging from spreadsheet implementations of manual processes through to mathematical models using efficient optimal or heuristic algorithms. We do not review software packages in this paper. Rather, we review rostering problems in specific application areas, and the models and algorithms that have been reported in the literature for their solution. We also survey commonly used methods for solving rostering problems. <s> BIB003 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper describes a problem faced by CS Energy's Swanbank Power Station in the Australian state of Queensland. It involved the personnel scheduling (rostering) of staff with multiple skill levels at the power station. Such a problem can be classified using the six stage construction process proposed by Ernst et al. We assume that the three processes of ‘demand modelling,’ ‘shift starting times’ and ‘task scheduling’ are specified. We are concerned with the essential processes of ‘day off scheduling,’ ‘line of work construction’ and ‘shift assignment to staff’ with requirements to maintain multiple skills. Several other authors have reported results for staff with hierarchical skills while the methods proposed in this paper are for non-hierarchical skill sets. The paper describes a set covering approach to the multi-skilled rostering problem. We propose a number of solution strategies for the set covering approach and give a comparison of the results. Copyright Kluwer Academic Publishers 2004 <s> BIB004 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> We consider a generic workforce scheduling problem, where employees are characterized by qualifications. Given a set of shifts for each day, we have to determine for each employee his working days as well as a specific shift for each working day. The overall objective is to find a set of feasible schedules with respect to hard and soft restrictions. We propose an integer multi-commodity network flow formulation for the problem under consideration and show how branch-and-price can be used to solve this problem. <s> BIB005 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this paper we formulate and efficiently solve staff scheduling problems for large organizations that provide continuous services to customers. We describe an integer programming approach for a class of such problems, where solutions have to obey a number of constraints related to workload balancing, shift compatibility, and distribution of days off. The formulation of the constraints is general and can be extended to different personnel management problems where staff members must cover shifts, and management must assign a fixed number of days off per week. The model maximizes staff satisfaction, expressed by positive weights for pairs of shifts in consecutive days. We consider the associated polytope and study its structure, determining some classes of inequalities that are facet inducing for special subproblems and other valid classes. We also identify a particular subproblem whose solution can be used to determine strong cuts for the complete problem. In addition, we design special branching rules that break the symmetries that arise in the solution space and have a large impact in the efficiency of the method. The validity of this approach has been ascertained by extensive computational tests; moreover, the operations research (OR) department of an airline has implemented the method to solve ground staff management problems. <s> BIB006 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> The problem of rerostering nurse schedules arises in hospitals when at least one nurse informs that she will be unable to perform the shifts assigned to her on one or more future work days. As a result, the current roster must be rebuilt in accordance with labour contract rules and institutional requirements. All such restraints are regarded as hard constraints. However, major alterations in the previously assigned nurse schedules must be avoided. This paper is based on a case study of a public hospital in Portugal. It presents two new integer multicommodity flow formulations for the rerostering problem, besides a computational experiment performed using real data. The first model is based on a directed multilevel acyclic network. The aggregation of nodes in this network led to the second model. The results obtained show that the second integer multicommodity flow formulation outperforms the first, both in terms of solution quality, as well as in computational time. <s> BIB007 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> A practical nurse rostering problem, which arises at a ward of an Italian hospital, is considered. The nurse rostering problem is a typical employee timetabling problem, where each month it is required to generate the nursing staff shifts subject to various contractual and operational requirements. These requirements may be in conflict especially for those months in which manpower is reduced due to seasonal holidays. It is required to consider both holidays planning and parametric contractual constraints, but no cyclic schedules and corresponding weekly patterns. A local search approach is introduced which is based on a neighborhood operating on partial solutions completed by means of a greedy procedure so as to avoid the generation of infeasible solutions. Both a tabu search procedure and an iterated local search procedure are proposed. The solutions computed by the proposed procedures compare well with respect to a straightforward lower bound and strongly outperform those manually generated in the hospital ward. The proposed approach is now currently used on site. <s> BIB008 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this paper, we present and evaluate a neural network model for solving a typical personnel-scheduling problem, i.e. an airport ground staff rostering problem. Personnel scheduling problems are widely found in servicing and manufacturing industries. The inherent complexity of personnel scheduling problems has normally resulted in the development of integer programming-based models and various heuristic solution procedures. The neural network approach has been admitted as a promising alternative to solving a variety of combinatorial optimization problems. While few works relate neural network to applications of personnel scheduling problems, there is great theoretical and practical value in exploring the potential of this area. In this paper, we introduce a neural network model following a relatively new modeling approach to solve a real rostering case. We show how to convert a mixed integer programming formulation to a neural network model. We also provide the experiment results comparing the neural network method with three popular heuristics, i.e. simulated annealing, Tabu search and genetic algorithm. The computational study reveals some potential of neural networks in solving personnel scheduling problems. <s> BIB009 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Rotating work schedules are encountered in several industries and public sector organizations where work is carried out 24 h a day, 7 days a week. This article first provides a classification of the main constraint classes governing the design of rotating schedules. A novel constraint programming algorithm is then developed that can handle a wider variety of constraints than other algorithms from the literature. Computational results on several real-life examples confirm the efficiency and robustness of the proposed approach. <s> BIB010 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB011 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB012 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper explores the issue of choosing the best data to use when running a scheduling model to select a permanent workforce for a service facility. Because demand is assumed to vary over the day and throughout the week, the choice of the input data is crucial. If a week of low volume is selected, the solution might call for an insufficient number of workers; if a week of high volume is chosen, excessive idle time might be the result. Staff scheduling at mail processing and distribution centers (P&DCs) in the United States provides the backdrop. In operating these facilities, a critical objective is to manage overtime, part-time workers, and temporaries so that when volumes are high, additional costs are kept to a minimum, and when volumes are low the permanent workforce is almost never idle. In quantitative terms, this means selecting the size and composition of the workforce so that over the year, no more than a total number of overtime hours, part-time hours and temporary worker hours are used when demand exceeds some baseline and absenteeism is taken into account. To solve the problem, an engineering approach is proposed in which estimates of productivity are made based on a single run of the optimization model and the final data set is chosen to satisfy a small error tolerance. The full methodology is illustrated with data provided by the Dallas P&DC. <s> BIB013 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper discusses the problem of scheduling a multi-skilled workforce in service organizations where demand varies throughout the day, 7 days a week. The goal is to determine the optimal complement of workers so that demand is met without violating labor rules, union agreements, and company policies. It is assumed that each member of the workforce possesses a particular type of skill and can be categorized as either full-time, part-time, or temporary. Demand is specified by skill type, and in the downgrading analysis, a person in a higher skill category can be assigned a job in a lower skill category, but at the original rate of pay. We develop a mixed-integer linear programming model for this problem based on staffing requirements at US Postal Service mail Processing and Distribution Centers (P&DCs). The solution methodology involves the use of a commercial code to find daily shifts, and post-processing heuristics to construct 5-day a week schedules, allocate lunch breaks, and assign workers to jobs during the day. Results are presented for the Dallas P&DC where it is seen that considerable savings are possible when downgrading is implemented. <s> BIB014 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB015 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB016 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB017 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Motivated by difficult staff scheduling problems arising in healthcare institutions, we have developed an implicit tour scheduling model which includes full and part-time tour types as well as intra-tour start time flexibility. Potential benefits of intra-tour start time flexibility are demonstrated through a computational experiment. The model has been embedded in a decision support system at a large tertiary care hospital and has been used in numerous studies to help estimate staffing needs and to analyze the impact of scheduling policies and practices. <s> BIB018 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB019 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Abstract Designing shifts is one of the important stages in the general workforce scheduling process. In this paper we consider solving the shift design problem by using local search methods. First we propose a set of move types that give rise to a composite neighbourhood relation. In the move selection process, we make use of the basic prohibition mechanisms of tabu search. In addition, in order to avoid having to explore the whole neighbourhood which could be prohibitively large, we evaluate the moves in decreasing order of their promise to yield some improvement. Furthermore, we propose an algorithm for generating a good initial solution, which also exploits knowledge about requirements and shift structure. Experimental results on both real-life and randomly-generated instances show the advantages of these ingredients. The solver is part of a commercial product and has shown to work well in practical cases. <s> BIB020 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB021 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Airline crew scheduling is a comparably well-studied field in operations research. An increasing demand for higher crew satisfaction arises; especially after most relevant cost factors have been optimized to their greatest extent, mostly with secondary or little regard on quality-of-life criteria for the involved crew members. One such criterion is team orientation. Independent from the chosen assignment strategy (bidline systems, personalized rostering or preferential bidding), current approaches do not consider frequently occurring changes within daily or day-by-day team compositions. By this, crew members rarely know with whom they work for the next flight(s) and/or day(s), respectively. In case of overnight stays outside their individual home base, crew members easily experience themselves having to find their ways to the booked hotels on their own. The avoidance of both aspects is highly appreciated by the crew as well as by the airlines, and will be addressed in the Team-oriented Rostering Problem. In this work we present a first interpretation of Team-oriented Rostering for cockpit crew, namely captains and first officers which can be implemented via two dedicated optimization models: Extended Rostering Model and Roster Combination Model. Due to the high combinatorial complexity, certain strategies are applied during roster generation and roster combination in order to solve mid-sized instances based on a European tourist airline setting. As a result, the implied trade-off curve between operational cost and the number of team changes will be discussed. <s> BIB022 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB023 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Consider an assignment problem in which persons are qualified for a subset of the jobs; assume the persons to belong to given seniority classes. Seniority constraints impose that the solution is such that no free person can be given a job unless an assigned person with the same or higher seniority becomes free. Similarly, jobs can belong to priority classes for which priority constraints must hold. It is shown that the assignment problem with both types of constraints can be solved by successively reoptimizing a (rectangular) linear assignment problem of increasing size. The related complexity is lower than for a known coefficient scaling approach. A further advantage of this approach is that it is easy to modify to solve the problem under the bottleneck criterion. <s> BIB024 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> We present an iterative cutting plane method for minimizing staffing costs in a service system subject to satisfying acceptable service level requirements over multiple time periods. We assume that the service level cannot be easily computed, and instead is evaluated using simulation. The simulation uses the method of common random numbers, so that the same sequence of random phenomena is observed when evaluating different staffing plans. In other words, we solve a sample average approximation problem. We establish convergence of the cutting plane method on a given sample average approximation. We also establish both convergence, and the rate of convergence, of the solutions to the sample average approximation to solutions of the original problem as the sample size increases. The cutting plane method relies on the service level functions being concave in the number of servers. We show how to verify this requirement as our algorithm proceeds. A numerical example showcases the properties of our method, and sheds light on when the concavity requirement can be expected to hold. <s> BIB025 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB026 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB027 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB028 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> We describe the development and implementation of a decision support system for the optimization of passenger flow by trading off service quality and labour costs at an airport. The system integrates a simulation module with an optimization module that requires that Dantzig's labour scheduling problem be solved in the order of thousands of times. We developed a customized scatter search to give the system the capability of finding high-quality solutions to the labour scheduling problems in short computational times. Our experiments verify that our scatter search implementation meets the needed requirements. <s> BIB029 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> A hyperheuristic is a high level procedure which searches over a space of low level heuristics rather than directly over the space of problem solutions. The sequence of low level heuristics, applied in an order which is intelligently determined by the hyperheuristic, form a solution method for the problem. In this paper, we consider a hyperheuristic-based methodology where a large set of low level heuristics is constructed by combining simple selection rules. Given sufficient time, this approach is able to achieve high quality results for a real-world personnel scheduling problem. However, some low level heuristics in the set do not make valuable contributions to the search and only slow down the solution process. We introduce learning strategies into hyperheuristics in order to select a fit subset of low level heuristics tailored to a particular problem instance. We compare a range of selection approaches applied to a varied collection of real-world personnel scheduling problem instances. <s> BIB030 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this research, we introduce a dual-purpose simulation model that integrates two decision support systems used by the US Postal Service to configure and staff their mail processing and distribution centers (P&DCs). The first system is designed to optimize the daily equipment schedules and the second to optimize the size and composition of the permanent workforce. Large-scale integer programs are solved in both cases. Because some compromise is needed in the time granularity, it is important to have an independent means of validating the results. This is the first purpose of our simulation model. The second involves the generation and validation of labor requirements for a category of workers known as mail handlers. While there is a one-to-one relationship between machine operators and the equipment schedule derived from the mail arrival profiles, no such relationship exists for those responsible for moving the mail between workstations. Neither productivity measures nor formal work rules exist. To resolve this shortcoming, we use simulation again, but this time to estimate mail handler requirements and then to determine whether the weekly schedules derived from the staff optimizer are adequate to meet the facility's service standards. Holistically speaking, the simulation serves as a bridge between the two optimization systems. The procedure is demonstrated with data provided by the Dallas P&DC. <s> BIB031 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Call centers usually handle several types of calls, but it is usually not possible or cost effective to have every agent be able to handle every type of call. Thus, the agents tend to have different skills, in different combinations. In such an environment, it is challenging to route calls effectively and determine the staff requirements. This paper addresses both of these routing and staffing problems by exploiting limited cross-training. Consistent with the literature on flexible manufacturing, we find that minimal flexibility can provide great benefits: Simulation experiments show that when (1) the service-time distribution does not depend on the call type or the agent and (2) each agent has only two skills, in appropriate combinations, the performance is almost as good as when each agent has all skills. We apply this flexibility property to develop an algorithm for both routing and staffing, aiming to minimize the total staff subject to per-class performance constraints. With appropriate flexibility, it suffices to use a suboptimal routing algorithm. Simulation experiments show that the overall procedure can be remarkably effective: The required staff with limited cross-training can be nearly the same as if all agents had all skills. Hence, the overall algorithm is nearly optimal for that scenario. <s> BIB032 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this study, a computerized nurse-scheduling model is developed. The model is approached through a 0-1 linear goal program. It is adapted to Riyadh Al-Kharj hospital Program (in Saudi Arabia) to improve the current manual-made schedules. The developed model accounts both for hospital objectives and nurses' preferences, in addition to considering some recommended policies that are displayed in the literature. Hospital objectives include ensuring a continuous service with appropriate nursing skills and staffing size, while avoiding additional costs for unnecessary overtime. Nurses preferences, which are deduced from a survey conducted on-purpose for the sake of this study, include mainly fairness considerations, in terms of ratio of night shifts and weekends off, in addition to avoiding isolated days on and off. The model is implemented in an experimental phase of six-month period using LINGO and is considered to perform reasonably well, based both on some quality criteria displayed in the literature and on the feedback obtained from a second survey, that has been developed to assess the scheduling system performance. <s> BIB033 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB034 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB035 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this paper, we first provide an MIP formulation of a selection/assignment problem and then we discuss a solution method based both on the use of a commercial general-purpose scatter-search and a simple implementation of tabu search. This optimization problem is related to a research project supported by the Office of Naval Research where sailors need to be selected to perform a set of jobs that require specific skill levels. The results of our computational experiments indicate the usefulness of the software system for workforce planning that we have developed. <s> BIB036 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB037 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB038 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This article considers the overall crew management problem arising from the daily operation of an urban transit bus company that serves the metropolitan area of the city of Belo Horizonte, Brazil. Due to its intrinsic complexity, the problem is divided in two distinct subproblems:crew scheduling andcrew rostering. We have investigated each of these problems using mathematical programming (MP) and constraint logic programming (CLP) approaches. In addition, we developed hybrid column generation algorithms for solving these problems, combining MP and CLP. The hybrid algorithms always performed better, when obtaining optimal solutions, than the two previous isolated approaches. In particular, they proved to be much faster for the scheduling problem. All the proposed algorithms have been implemented and tested over real-world data obtained from the aforementioned company. The coefficient matrix of the linear program associated with some instances of the scheduling problem contains tens of millions of columns; this number is even larger for the rostering problem. The analysis of our experiments indicates that it was possible to find high-quality, and many times optimal, solutions that were suitable for the company's needs. These solutions were obtained within reasonable computational times on a desktop PC. <s> BIB039 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> We consider the problem of minimizing staffing costs in an inbound call center, while maintaining an acceptable level of service in multiple time periods. The problem is complicated by the fact that staffing level in one time period can affect the service levels in subsequent periods. Moreover, staff schedules typically take the form of shifts covering several periods. Interactions between staffing levels in different time periods, as well as the impact of shift requirements on the staffing levels and cost, should be considered in the planning. Traditional staffing methods based on stationary queueing formulas do not take this into account. We present a simulation-based analytic center cutting-plane method to solve a sample average approximation of the problem. We establish convergence of the method when the service-level functions are discrete pseudoconcave. An extensive numerical study of a moderately large call center shows that the method is robust and, in most of the test cases, outperforms traditional staffing heuristics that are based on analytical queueing methods. <s> BIB040 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB041 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Scheduling emergency medicine residents (EMRs) is a complex task, which considers a large number of rules (often conflicting) related to various aspects such as limits on the number of consecutive work hours, number of day and night shifts that should be worked by each resident, resident staffing requirements according to seniority levels for the day and night shifts, restrictions on the number of consecutive day and night shifts assigned, vacation periods, weekend off requests, and fair distribution of responsibilities among the residents. Emergency rooms (ERs) are stressful workplaces, and in addition shift work is well-known to be more demanding than regular daytime work. For this reason, preparing schedules that suit the working rules for EMRs is especially important for reducing the negative impact on shift workers physiologically, psychologically, and socially. In this paper, we present a goal programming (GP) model that accommodates both hard and soft constraints for a monthly planning horizon. The hard constraints should be adhered to strictly, whereas the soft constraints can be violated when necessary. The relative importance values of the soft constraints have been computed by the analytical hierarchy process (AHP), which are used as coefficients of the deviations from the soft constraints in the objective function. The model has been tested in the ER of a major local university hospital. The main conclusions of the study are that problems of realistic size can be solved quickly and the generated schedules have very high qualities compared to the manually prepared schedules, which require a lot of effort and time from the chief resident who is responsible for this duty. <s> BIB042 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Abstract Labour cost represents a huge portion of total cost in many industries. This paper looks at the novel idea of using compressed workweeks to save labour cost. While the idea is quite simple and applicable, it appears to be unknown. We give examples to show that savings in labour cost can be more than trivial, making the idea useful. We also provide formulae for computing workforce sizes and show how to construct schedules under a variety of scenarios. <s> BIB043 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> The purpose of this paper is to investigate the problem of assigning tasks to workers during their daily shifts. For a homogeneous workforce, a given set of workstation groups, and a corresponding demand for labor, the objective is to develop a disaggregated schedule for each worker that minimizes the weighted sum of transitions between workstation groups. In the formulation of the problem, each day is divided into 48 1/2-hour time periods and a multi-commodity network is constructed in which each worker corresponds to a unique commodity and each node represents a workstation group-time period combination. Lunch breaks and idle time are also included in the model. ::: ::: Initial attempts to solve large instances with a commercial code indicated a need for a more practical approach. This led to the development of a reduced network representation in which idle periods are treated implicitly, and a sequential methodology in which the week is decomposed into 7 daily problems and each solved in turn. To gain more computational efficiency, a tabu search procedure was also developed. ::: ::: All procedures were tested using data obtained from a U.S. Postal Service mail processing and distribution center. Depending on the labor category, anywhere from 3 to 28 workstation groups and up to 311 full-time and part-time workers had to be scheduled together. The results were mixed. While small problems could be solved to near-optimality with the integer programming approaches, tabu search was the best alternative for the very large instances. However, the excessive number of swaps needed to gain marginal improvements, undermined its effectiveness.Combining the two provided a good balance in most cases. <s> BIB044 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this paper, we present a scatter search algorithm for the well-known nurse scheduling problem (NSP). This problem aims at the construction of roster schedules for nurses taking both hard and soft constraints into account. The objective is to minimize the total preference cost of the nurses and the total penalty cost from violations of the soft constraints. The problem is known to be NP-hard. The contribution of this paper is threefold. First, we are, to the best of our knowledge, the first to present a scatter search algorithm for the NSP. Second, we investigate two different types of solution combination methods in the scatter search framework, based on four different cost elements. Last, we present detailed computational experiments on a benchmark dataset presented recently, and solve these problem instances under different assumptions. We show that our procedure performs consistently well under many different circumstances, and hence, can be considered as robust against case-specific constraints. <s> BIB045 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Different approaches in the hybridization of constraint programming and local search techniques have been recently proposed in the literature. In this paper we investigate two of them, namely the employment of local search to improve a solution found by constraint programming and the exploitation of a constraint model to perform the exploration of the local neighborhood. We apply the two approaches to a real-world personnel rostering problem arising at the department of neurology of the Udine University hospital and we report on computational studies on both real-world and randomly generated structured instances. The results highlight the benefits of the hybridization approach w.r.t. their component algorithms. <s> BIB046 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Constraint Programming (CP) offers a rich modeling language of constraints embedding efficient algorithms to handle complex and heterogeneous combinatorial problems. To solve hard combinatorial optimization problems using CP alone or hybrid CP-ILP decomposition methods, costs also have to be taken into account within the propagation process. Optimization constraints, with their cost-based filtering algorithms, aim to apply inference based on optimality rather than feasibility. This paper introduces a new optimization constraint, cost-regular. Its filtering algorithm is based on the computation of shortest and longest paths in a layered directed graph. The support information is also used to guide the search for solutions. We believe this constraint to be particularly useful in modeling and solving Column Generation subproblems and evaluate its behaviour on complex Employee Timetabling Problems through a flexible CP-based column generation approach. Computational results on generated benchmark sets and on a complex real-world instance are given. <s> BIB047 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> AbstractThis paper presents a three-day workweek scheduling problem with four types of days-off scheduling constraints: (1) out of the four off days given to each employee per week, at least two must be consecutive, (2) two alternative types of constraints are imposed to ensure that employees get a sufficient proportion of weekends off, (3) the maximum work stretch is four consecutive workdays for each employee, and (4) the maximum number of successive weeks with weekend work is specified. A mathematical model of this problem is formulated and efficiently solved by introducing a bound on workforce size. First, the problem structure is used to determine the minimum workforce size. Subsequently, a workforce-size constraint is added to the integer programming model in order to facilitate solution. Finally, multiple-week rotation schedules are produced to satisfy all constraints and limit or minimize the number of successive weeks with weekend work. <s> BIB048 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Personnel rostering problems are highly constrained resource allocation problems. Human rostering experts have many years of experience in making rostering decisions which reflect their individual goals and objectives. We present a novel method for capturing nurse rostering decisions and adapting them to solve new problems using the Case-Based Reasoning (CBR) paradigm. This method stores examples of previously encountered constraint violations and the operations that were used to repair them. The violations are represented as vectors of feature values. We investigate the problem of selecting and weighting features so as to improve the performance of the case-based reasoning approach. A genetic algorithm is developed for off-line feature selection and weighting using the complex data types needed to represent real-world nurse rostering problems. This approach significantly improves the accuracy of the CBR method and reduces the number of features that need to be stored for each problem. The relative importance of different features is also determined, providing an insight into the nature of expert decision making in personnel rostering. <s> BIB049 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Scheduling trainees (graduate students) is a complicated problem that has to be solved frequently in many hospital departments. We will describe a trainee-scheduling problem encountered in practice (at the ophthalmology department of the university hospital Gasthuisberg, Leuven). In this problem, a department has a number of trainees at its disposal, which assist specialists in their activities (surgery, consultation, etc.). For each trainee one has to schedule the activities in which (s)he will assist during a certain time horizon, usually one year. Typically, this kind of scheduling problem is characterized by four types of constraints: work covering constraints, formation requirements, non-availability constraints and setup restrictions. In this paper, we will describe an exact branch-and-price method to solve the problem to optimality. <s> BIB050 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB051 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Abstract The health care system in Sweden and many other countries is facing increasing costs. The major reason is the changing age distribution of the population with more elderly people in need of support. At the same time, health care systems are often very labor and staff intensive. In this paper, we focus on a staff planning problem arising in Sweden where people receive home care from the local authorities. The objective is to develop visiting schedules for care providers that incorporate some restrictions and soft objectives. Each visit has a particular task to be performed, for example: cleaning, washing, personal hygiene and/or nursing activities. Each staff member has skills and each client should, if possible, be visited by the same contact person. The operational situation is continuously changing and planning is done each day. We describe the development of a decision support system L aps C are to aid the planners. The system consists of a number of components including information data bases, maps, optimization routines, and report possibilities. We formulate the problem using a set partitioning model and, for a solution method, we make use of a repeated matching algorithm. The system is currently in operation at a number of home care organizations. We report on the practical impact of the system in the health care organization which was involved in the development. The savings are considerably in terms of saved planning time and in the quality of the routes, as well as the measured quality for the clients. Numerical experiments of the system are presented. <s> BIB052 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this paper, we present an applied study commissioned by Metro Bilbao on how to establish a more egalitarian annual allocation of work to drivers. Task allocation is mixed, with some tasks allocated on a rotating basis and others not. The model proposed is solved as a sequence of four types of integer programming problem. The solution obtained is quasi-optimal: all drivers carry out practically the same tasks over the full year. The main contribution of this paper is its method for combining semi-rotating allocation with a planning time frame divided into five periods of three different types with a workload distributed in a non uniform fashion over the days of the week, and with constraints agreed with employees to obtain an egalitarian solution. This method is being implemented at Metro Bilbao, and Eusko Tren has commissioned a study into a similar method by the authors. <s> BIB053 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Abstract A new model called MPS-T is presented for the scheduling of temporary workers in mixed model flow lines with both skilled and unskilled workstations. We classify workers in two dimensions: (i) permanent or temporary, and (ii) skilled or unskilled. While all permanent workers are skilled, temporary workers can be either skilled or unskilled. Two workstation restrictions are modeled in the MPS-T: (i) some workstations may be limited to only skilled workers if there is a significant operational complexity, (ii) each workstation is limited to a minimum ratio of permanent to temporary workers. Such workforce models are commonly seen in labor intensive export oriented factories located in the Far East. These factories experience an order behavior that is characterized by high variance and short lead times. Distinguishing between worker types, permits management to limit their fixed workforce costs and also rapidly access a cheaper labor pool to meet demand surges. MPS-T is modeled as a mixed integer program and the key decisions are: (i) What type of temporary workers to hire or layoff in each period, (ii) the number of workers to hire or layoff in each period, (iii) the assignment of the work time of workers to the work stations, and (iv) the usage of overtime hours. A case study example to study model behavior under different parametric conditions is reported. <s> BIB054 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Abstract In order to reduce cost and to optimize the use of resources, hospitals are prompted to regroup facilities and human resources, especially in the surgical suite. This paper focuses on the anaesthesiology nurse scheduling problem (ANSP of a French public hospital, where the anaesthesiology nurses constitute one of the most shared resources. They work in a cross way over surgical specialities and assume various activities. Two methods are proposed to solve the ANSP based on integer programming and constraint programming. The objective is to maximize the fairness of the schedule. Theses two techniques are tested in order to be compared. <s> BIB055 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB056 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB057 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In a multi-project environment, we sometimes need to periodically schedule the tasks for each project and assign staff to the tasks. Such a decision-making problem has been studied in literature; however, learning effect of staff has not been considered in previous studies. This research formulates a mixed nonlinear program for project scheduling and staff allocation problems, which considers learning effect of staff. The objective function is to minimize outsourcing costs. A genetic algorithm (GA) is proposed to solve the problem. Experiments for solving various sizes of test problems has been carried out to validate the proposed GA. <s> BIB058 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Four strategic models, combining different manpower supply principles, flexible management strategies and related operating constraints, are developed to help an air cargo terminal manage its long-term manpower supply more effectively. The models are formulated as integer/mixed integer linear programs, which are solved using a mathematical programming solver. To evaluate how the models perform in practice, a case study, utilizing the operating data of a domestic air cargo terminal in Taiwan, is conducted. The preliminary test results show that the four models are efficient and effective, and could be applied to actual operations. <s> BIB059 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Objectives: Significant variation in emergency department (ED) patient arrival rates necessitates the adjustment of staffing patterns to optimize the timely care of patients. This study evaluated the effectiveness of a queueing model in identifying provider staffing patterns to reduce the fraction of patients who leave without being seen. ::: ::: Methods: The authors collected detailed ED arrival data from an urban hospital and used a Lag SIPP queueing analysis to gain insights on how to change provider staffing to decrease the proportion of patients who leave without being seen. The authors then compared this proportion for the same 39-week period before and after the resulting changes. ::: ::: Results: Despite an increase in arrival volume of 1,078 patients (6.3%), an average increase in provider hours of 12 hours per week (3.1%) resulted in 258 fewer patients who left without being seen. This represents a decrease in the proportion of patients who left without being seen by 22.9%. Restricting attention to a four-day subset of the week during which there was no increase in total provider hours, a reallocation of providers based on the queueing model resulted in 161 fewer patients who left without being seen (21.7%), despite an additional 548 patients (5.5%) arriving in the second half of the study. ::: ::: Conclusions: Timely access to a provider is a critical dimension of ED quality performance. In an environment in which EDs are often understaffed, analyses of arrival patterns and the use of queueing models can be extremely useful in identifying the most effective allocation of staff. <s> BIB060 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper considers the problem of developing workforce schedules using groups of employees having different productivity. We show that the existing linear representation of this problem is often inaccurate for high-contact service organizations because it ignores the stochastic nature of customer arrivals. Specifically, the existing representation commonly overestimates the number of less productive employees necessary to deliver a specified, waiting time-based customer service level. We present a new, nonlinear representation of this staffing problem that captures its nonlinear nature and demonstrate its superiority via an extensive set of labor tour scheduling problems for the two-group case. <s> BIB061 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB062 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> We present a new methodology for solving large-scale employee tour scheduling problems. An integer programming model is proposed where tours are decomposed into shifts and start times. This formulation can model complex shift and start time rules for both continuous and discontinuous scheduling problems. A branch-and-price approach is devised to solve this model efficiently. The methodology was tested on the largest tour scheduling problems found in the open literature. In comparison with an alternative implicit model, our approach showed superior computational performance. Copyright Springer Science+Business Media, LLC 2007 <s> BIB063 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this paper a comparison is made between two decomposition techniques to solve a staff scheduling problem with column generation. In the first approach, decomposition takes place on the staff members, whereas in the second approach decomposition takes place on the activities that have to be performed by the staff members. The resulting master LP is respectively a set partitioning problem and a capacitated multi-commodity flow problem. Both approaches have been implemented in a branch-and-price algorithm. We show a trade-off between modeling power and computation times of both techniques. <s> BIB064 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In complex logistic systems, such as transportation systems, dealing with personnel scheduling is a non-trivial task. Duties have to be created and assigned to workers in a way to optimize a certain objective function. In this paper, in particular, we consider the case of scheduling train drivers on a railway subnetwork. Train driver scheduling involves the construction of feasible duties from a set of trips to be carried out by a number of train drivers. Each duty consists of a sequence of trips to be carried out by a single train driver on a single day. The duties should be such that: each trip is covered by at least one duty, each duty satisfies feasibility constraints, additional constraints involving the complete schedule are satisfied, one or several objectives are met. In this paper we focus on minimizing the number of duties and on maximizing the robustness of the obtained schedule for outside disruptions. We present an implicit column generation solution approach. We describe a heuristic procedure to find an initial feasible solution together with a heuristic branch-and-price algorithm based on a dynamic programming algorithm for the pricing-out of columns. We tested our approach on the timetable of the Intercity train series 500, 700, 1600 and 1700 of NS Reizigers, the largest Dutch operator of passengers trains. <s> BIB065 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB066 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB067 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB068 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper describes the staffing and scheduling of IT help desk operators for a large petrochemical company. The objective is to reduce the labour cost by determining the best staffing level and employee weekly tour schedules required to meet the workload that varies over a 24-hr operating period. Several steps are taken for the staffing and tour scheduling of an IT help desk agents. First, data on the number of calls is used to estimate hourly labour requirements. Next, new scheduling options are proposed to better match these requirements. An Integer Programming (IP) model is then formulated and solved to determine tour scheduling assignments. Finally, alternative schedules are evaluated in terms of tradeoffs between workforce size and cost, service level and employee utilisation. The chosen tour schedules provide better service with a lower cost and a smaller number of employees.[Received 10 November 2006; Revised 23 April 2007; Accepted 18 June 2007] <s> BIB069 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB070 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB071 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB072 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB073 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this paper we present a framework that balances the significant tradeoffs and helps managers in crafting a strategy for the induction of contingent workers in a complex assembly environment. The key issues we have considered in this paper include distinct manufacturing sub-processes, hierarchical or nested workforce skills, regular and overtime capacity, and impact of learning. We report a real life case study pertaining to the Singapore operations of a global computer manufacturer that served as the backdrop of this research and provided us with several intuitions. A linear programming model is presented to help determine the optimal allocation of permanent and contingent workers to all sub-processes. Our numerical study comprising more than 165 distinct experiments indicates that both the firm's cost performance and the number of contingent workers inducted are significantly affected by key parameters such as cost of induction, overtime premium cost, and overtime capacity. We highlight the impact of ... <s> BIB074 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Abstract In the context of manpower planning, goal programming (GP) is extremely useful for generating shift duties of fixed length. A fixed-length duty consists of a fixed number of contiguous hours of work in a day, with a meal/rest break somewhere preferably around the middle of these working hours. It is such properties that enable the straightforward, yet flexible GP modeling. We propose GP models for an integrated problem of crew duties assignment, for baggage services section staff at the Hong Kong International Airport. The problem is solved via decomposition into its duties generating phase—a GP planner, followed by its GP scheduling and rostering phase. The results can be adopted as a good crew schedule in the sense that it is both feasible, satisfying various work conditions, and “optimal” in minimizing idle shifts. <s> BIB075 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB076 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB077 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB078 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB079 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB080 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB081 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Labour scheduling plays an important and critical role in Sainsburys day to day operations and profitability. The integrated workforce management solution for Sainsburys is an intelligent solution for the operational deployment of human resources, integrated business forecasting, generation and calculation of workload and staff scheduling. The workforce management technology has provided Sainsburys with a fully web-based and centralised system that produces optimised schedules for all employees satisfying the forecasted demand of work with granularity of fifteen minutes. The system is configured to respect all operational and business requirements as well as employee contractual constraints. This paper introduces the workforce management solution system designed, developed and implemented for Sainsburys. We concentrate on two modelling structures, namely the work pattern model and optimisation model, and briefly discuss the optimisation process. Copyright Springer Science+Business Media, LLC 2007 <s> BIB082 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Abstract The nurse rerostering problem occurs when one or more nurses cannot work in shifts that were previously assigned to her or them. If no pool of reserve nurses exists to replace those absent, then the current roster must be rebuilt. This new roster must comply with the labour rules and institutional constraints. Moreover, it must be as similar as possible to the current one. The present paper describes constructive heuristics, besides several versions of genetic algorithms based on specific encoding and operators for sequencing problems applied to the nurse rerostering problem, defined with hard constraints. In the genetic algorithms described, each individual in the population is associated with a pair of chromosomes, representing permutations of tasks and nurses. Those permutations are used as input to a procedure that generates rosters. The fitness of individuals is given by the similarity between the roster generated from the permutations and the current one. The authors developed several versions of the genetic algorithm, whose difference lay in the encoding of permutations and in the genetic operators used for each encoding. These heuristics were tested with real data from a Lisbon hospital and yielded good quality solutions. Scope and purpose The research reported is part of a project designed to develop a system for the management of nurse schedules for implementation in Portuguese public hospitals. The specific problem of rebuilding nurse schedules is addressed when unexpected staff absences arise. The complexity of the problem led the authors to design heuristic procedures. The tests performed so far with real data have shown that the algorithms attain good quality solutions at a computing time within the bounds stipulated by the hospital. <s> BIB083 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> High demand but limited staffs within some services of a hospital require a proper scheduling of staff and patients. In this study, a hierarchical mathematical model is proposed to generate weekly staff scheduling. Due to computational difficulty of this scheduling problem, the entire model is broken down into manageable three hierarchical stages: (1) selection of patients, (2) assignment of patients to the staff, (3) scheduling of patients throughout a day. The developed models were tested on the data collected in College of Medicine Research Hospital at Cukurova University using GAMS and MPL optimization packages. From the results of the case study, the presented hierarchical model provided a schedule that ensures to maximize the number of selected patients, to balance the workload of physiotherapist, and to minimize waiting time of patients in their treatment day. <s> BIB084 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB085 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Abstract In this paper, an integer programming model for the hierarchical workforce problem under the compressed workweeks is developed. The model is based on the integer programming formulation developed by Billionnet [A. Billionnet, Integer programming to schedule a hierarchical workforce with variable demands, European Journal of Operational Research 114 (1999) 105–114] for the hierarchical workforce problem. In our model, workers can be assigned to alternative shifts in a day during the course of a week, whereas all workers are assigned to one shift type in Billionnet’s model. The main idea of this paper is to use compressed workweeks in order to save worker costs. This case is also suitable for the practice. The proposed model is illustrated on the Billionnet’s example problem and the obtained results are compared with the Billionnet’s model results. <s> BIB086 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> A real-world planned maintenance scheduling problem that exists at several business units within United Technologies Corporation (UTC) is addressed in this paper. The scheduling problem is formulated as a multiple tour maximum collection problem with time-dependent rewards and an adaptive memory tabu search heuristic is developed to solve it. The effectiveness of the proposed solution approach is examined using real-world problem instances supplied by UTC. Relevant upper bounds are derived for the application. Results of numerical experiments indicate that the proposed tabu search heuristic is able to obtain near optimal solutions for large-size (i.e., actual) problem instances in reasonable computation time. <s> BIB087 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Abstract This paper focuses upon employee rest breaks, or reliefs, in workforce scheduling. Historically, the workforce scheduling literature has largely ignored reliefs, as less than 18% of the 64 papers we surveyed scheduled reliefs. The argument has been that one need not schedule reliefs in advance, since they can easily be scheduled in real-time. We find this argument to be flawed. We show that failing to schedule reliefs in advance will have one of two undesirable outcomes. First, there will be a less profitable deployment of labor should all reliefs actually be taken in real-time. Second, if some reliefs are never assigned or if relief-timing restrictions are relaxed so that more reliefs may be assigned in real-time, there will be a disgruntled and less productive workforce and perhaps violations of contractual obligations. Our findings are supported by anecdotal evidence drawn from commercial labor scheduling software. <s> BIB088 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB089 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper addresses the weekly adjustment problem for staff scheduling when movement restrictions exist between workstation groups (WSGs). In practice, it is common for employees to be organized into physical or logical groups to match the layout of a facility or to facilitate managerial oversight. A complication in the problem arises when each employee is required to spend more time at his or her assigned home base during the week than at any other WSG. This conflicts with a common strategy of reassigning employees to different WSGs when idle time exists in their schedules. Ordinarily, the full problem is tackled with a two-phase approach, where optimal shifts and overtime allocations are first derived and then tasks are assigned. When movement restrictions exist in a facility, this approach is no longer practical or even possible for all but the smallest instances. Alternatively, a new model is proposed that integrates WSG restrictions with the shift scheduling and task assignment constraints. The model takes the form of a large-scale integer program and is solved with one of two decomposition heuristics. The first splits the movement restrictions network into manageable pieces; the second uses column generation to identify good individual schedules that are used to construct a set-covering-type master problem. A solution to the master problem provides a feasible solution to the original integer program. Extensive testing was done with data obtained from the U.S. Postal Service mail processing and distribution center in Dallas. The results show that good feasible solutions can be obtained in less than an hour. <s> BIB090 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> We examine and compare simulation-based algorithms for solving the agent scheduling problem in a multiskill call center. This problem consists in minimizing the total costs of agents under constraints on the expected service level per call type, per period, and aggregated. We propose a solution approach that combines simulation with integer or linear programming, with cut generation. In our numerical experiments with realistic problem instances, this approach performs better than all other methods proposed previously for this problem. We also show that the two-step approach, which is the standard method for solving this problem, sometimes yield solutions that are highly suboptimal and inferior to those obtained by our proposed method. <s> BIB091 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB092 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB093 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this paper we develop a two stage algorithm for scheduling call centers with strict SLAs and arrival rate uncertainty. The first cut schedule can be developed in less than a minute using a constructive heuristic. The schedule is then refined via a simulation based optimization approach. We find that when allowed to run for five minutes or less this two stage process can create a schedule with a total expected cost within a few percentage points of schedules generated using much more computationally intensive methods. This rapid scheduling process is designed to support front line managers who wish to evaluate multiple scheduling options in a what if analysis mode. <s> BIB094 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper describes a spreadsheet model that MBA students enrolled in an MS course constructed to replace the manual method of assigning medical residents in radiology to on-call and emergency rotations at the University of Vermont's College of Medicine. Although it contains more than 10,000 variables, the model was easy to build and solve by practitioners who are “lightly educated” in OR/MS. Based on this group's work, we discuss an approach that end-user practitioners can take to create spreadsheet optimization models. We also provide several observations and argue that spreadsheet models can provide an alternative scheduling method for problems of a smaller scope. Despite the major advances in personnel-scheduling methodologies and software, manual scheduling is still the predominant method used for such smaller-scope problems. <s> BIB095 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB096 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB097 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB098 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB099 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> The aim of this research is twofold: Firstly, to model and solve a complex nurse scheduling problem with an integer programming formulation and evolutionary algorithms. Secondly, to detail a novel statistical method of comparing and hence building better scheduling algorithms by identifying successful algorithm modifications. The comparison method captures the results of algorithms in a single figure that can then be compared using traditional statistical techniques. Thus, the proposed method of comparing algorithms is an objective procedure designed to assist in the process of improving an algorithm. This is achieved even when some results are non-numeric or missing due to infeasibility. The final algorithm outperforms all previous evolutionary algorithms, which relied on human expertise for modification. <s> BIB100 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB101 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this paper we present a novel Case-Based Reasoning (CBR) system called CABAROST (CAsed-BAsed ROSTering) which was developed for personnel scheduling problems. CBR is used to capture and store examples of personnel manager behaviour which are then used to solve future problems. Previous examples of constraint violations in schedules and the repairs that were used to solve the violations are stored as cases. The sequence in which violations are repaired can have a great impact on schedule quality. A novel memetic algorithm is proposed which evolves good quality sequences of repairs generated by CABAROST. The algorithm was tested on instances of the real-world nurse rostering problem at the Queens Medical Centre NHS Trust in Nottingham. <s> BIB102 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> The evaluation of workforce staffing and scheduling policies is of paramount importance for meeting the challenge of simultaneously providing good customer service and low operational costs. Policy studies are particularly critical in workforce environments plagued by staffing shortages. The cross-utilization of employees among different departments or work centers is a well-recognized staffing policy for coping with shortages. We revisit a non-linear assignment problem for allocating cross-trained workers so as to maximize overall utility, which is measured using a quadratic function of labor shortages. We develop a branch-and-bound algorithm that efficiently provides optimal solutions for problems of practical size. This algorithm is then used to conduct a computational investigation of cross-training policies. Among the most critical factors affecting utility improvement are the coefficient of variation for demand, worker absenteeism, the percentage of cross-trained workers and cross-training breadth. Several important interactions among these and other factors are also identified. <s> BIB103 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Abstract Nurse rostering is a complex problem. We propose a new heuristic using a competitive agent-based negotiation that focuses on nurse preferences called competitive nurse rostering (CNR). Unlike the existing literature, CNR models each nurse's preference functions separately and separates the cost minimization and preference maximization problems. CNR produces quality nurse rosters even though it cannot leverage extra staffing. As an agent system, CNR can distribute computational requirements over several computer systems, include other solution methods at various points in of the rostering problem, and act as a real-time scheduling system. These benefits are not naturally inherent in centralized heuristic solutions. <s> BIB104 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB105 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Assigning tasks to employees is a difficult task. Errors committed in such assignments can have far-reaching consequences, such as reduced efficiency due to absenteeism, lack of job satisfaction, formal grievances, and generally deteriorating labor relations. This paper approaches the problem from a spatial point of view. First, the employees and the relevant tasks are mapped in a skill space. After feasible task assignments are determined, tasks are assigned to employees so as to minimize employee-task distances in order to avoid boredom, and minimize disequity between the individual employees' workloads, and minimize costs. Computational results are provided for an engineering department of the Pontificia Universidad Catolica de Chile in Santiago, Chile. <s> BIB106 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper presents a dynamic programming (DP) algorithm for solving a labor scheduling problem with several realistic days-off scheduling constraints and a cost structure that depends on the work sequence for each employee. The days-off scheduling constraints include the following: (1) each employee is assigned no more than three workdays per week, (2) each employee is assigned at least two consecutive off days per week, and (3) any work stretch cannot exceed four consecutive workdays. The sequence-dependent cost structure assumes that the daily wage of each employee depends on two factors: (1) whether the given workday is weekend or a regular workday, and (2) the sequence of work patterns assigned in previous days. A DP algorithm suited to instances of moderate size is used to determine the optimum work assignments that minimize the total labor cost, while satisfying the work demand under the stated constraints. <s> BIB107 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB108 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB109 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB110 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB111 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Nurse rerostering arises when at least one nurse announces that she will be unable to undertake the tasks previously assigned to her. The problem amounts to building a new roster that satisfies the hard constraints already met by the current one and, as much as possible, fulfils two groups of soft constraints which define the two objectives to be attained. A bi-objective genetic heuristic was designed on the basis of a population of individuals characterised by pairs of chromosomes, whose fitness complies with the Pareto ranking of the respective decoded solution. It includes an elitist policy, as well as a new utopic strategy, introduced for purposes of diversification. The computational experiments produced promising results for the practical application of this approach to real life instances arising from a public hospital in Lisbon. <s> BIB112 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB113 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> A good air cargo terminal manpower supply plan helps terminals deal efficiently with their cargos and reduces their operating costs. To design a good air cargo terminal manpower supply plan, a terminal has to consider not only its operating costs, but also the uncertainty of the manpower demand in actual operations. However, most air cargo terminals in Taiwan currently depend on staff experience with a fixed demand when establishing the manpower supply plan, which is neither effective nor efficient. We have developed two stochastic-demand manpower supply plan models for air cargo terminals that can resolve stochastic demands occurring in practice. The objectives of both models are to minimize the total man-hour cost, subject to the related operating constraints. The models are formulated as integer/mixed integer linear programs. To evaluate the two stochastic-demand models under stochastic demands, we have also developed two deterministic-demand manpower supply plan models, by suitably modifying two stochastic-demand models, respectively, and an evaluation method. Here, we perform a case study using real operating data from a Taiwan air cargo terminal. The preliminary results are good, showing that the models could be useful for planning air cargo terminal manpower supply. <s> BIB114 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper introduces a new method for shift scheduling in multiskill call centers. The method consists of two steps. First, staffing levels are determined, and next, in the second step, the outcomes are used as input for the scheduling problem. The scheduling problem relies on a linear programming model that is easy to implement and has short computation times, i.e., a fraction of a second. Therefore, it is useful for different purposes and it can be part of an iterative procedure: for example, one that combines shifts into rosters. <s> BIB115 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> We study an iterative cutting-plane algorithm on an integer program for minimizing the staffing costs of a multiskill call center subject to service-level requirements that are estimated by simulation. We solve a sample average version of the problem, where the service levels are expressed as functions of the staffing for a fixed sequence of random numbers driving the simulation. An optimal solution of this sample problem is also an optimal solution to the original problem when the sample size is large enough. Several difficulties are encountered when solving the sample problem, especially for large problem instances, and we propose practical heuristics to deal with these difficulties. We report numerical experiments with examples of different sizes. The largest example corresponds to a real-life call center with 65 types of calls and 89 types of agents (skill groups). <s> BIB116 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> The annualisation of working hours (i.e., the irregular distribution of the total number of working hours over the course of a year) makes it possible to adapt production capacity to fluctuations in demand. The required capacity, which is an essential data for the optimal planning of working time, usually depends on several complex factors. Often, it is impossible to reliably predict the required capacity or it is unrealistic to adjust it to a probability distribution. In some cases, it is possible to determine a set of required-capacity scenarios, each with a related probability. This paper presents a multistage stochastic optimisation model that provides a robust solution (i.e., feasible for any possible scenario) and minimises the expected total capacity shortage. <s> BIB117 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> We study a simple method for staffing in multiskill call centers. The method has short computation times and determines nearly optimal staffing levels. It is in both views competitive to other methods from the literature. Because of the fast and accurate performance of the method, many different scenarios can be analyzed, and our method can be used for both tactical and strategic capacity management decisions. <s> BIB118 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this research, based on two deterministic-demand planning models, we established two long-term stochastic-demand planning models by incorporating the stochastic disturbances of manpower demands that occur in actual operations. The models are formulated as mixed integer linear programs that are solved using a mathematical programming solver. To compare the performance of the two stochastic-demand and two deterministic-demand planning models under the stochastic demands that occur in actual operations, we further develop a simulation-based evaluation method. Finally, we perform numerical tests using real operating data from a Taiwan air cargo terminal. The preliminary results show that the stochastic models could be useful for planning air cargo terminal manpower supply. Copyright © 2008 John Wiley & Sons, Ltd. <s> BIB119 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper addresses the problem of scheduling medical residents that arises in different clinical settings of a hospital. The residents are grouped according to different seniority levels that are specified by the number of years spent in residency training. It is required from the residents to participate in the delivery of patient care services directly by working weekday and weekend day shifts in addition to their regular daytime work. A monthly shift schedule is prepared to determine the shift duties of each resident considering shift coverage requirements, seniority-based workload rules, and resident work preferences. Due to the large number of constraints often conflicting, a multi-objective programming model has been proposed to automate the schedule generation process. The model is implemented on a real case in the pulmonary unit of a local hospital for a 6-month period using sequential and weighted methods. The results indicate that high quality solutions can be obtained within a few seconds compared to the manually prepared schedules expending considerable effort and time. It is also shown that the employed weighting procedure based on seniority levels performs much better compared to the preemptive method in terms of computational burden. <s> BIB120 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In workforce scheduling, the optimal schedule has traditionally been determined by minimizing the cost of labor subject to an acceptable service level, which is defined as the percentage of customers served within a predetermined time interval. We propose an alternative multidimensional paradigm, where cost minimization and service level maximization are considered simultaneously, together with other, complementary criteria. The ultimate goal of the proposed approach is to open a broader workforce scheduling paradigm that incorporates service quality into the analysis and provides the possibility to study the interaction between cost and service quality. Furthermore, the approach enables us to avoid strong assumptions. An example with real-world, empirical demand data is provided. <s> BIB121 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB122 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Motivated by an industrial application, we study a specific employee timetabling problem. Several investigations are being conducted: a lower bound by Lagrangian relaxation, a heuristic based on a cut generation process and an exact method by Benders decomposition. Experimental results on real and generated instances are reported. <s> BIB123 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This research addresses a shift scheduling problem in which physicians at a German university hospital are assigned to demand periods over a planning horizon that can extend up to several weeks. When performing the scheduling it is necessary to take into account a variety of legal and institutional constraints that are imposed by a national labor agreement, which governs all physicians in German university hospitals. Currently, most medical departments develop their staff schedules manually at great cost and time. To solve the problem, a new modeling approach is developed that requires shifts to be generated implicitly. Rather than beginning with a predetermined number of shift types and start times, shifts are allowed to start at every pre-defined period in the planning horizon and extend up to 13 h with an hour-long break included. The objective is to find an assignment such that the total hours that have to be paid out as overtime are minimal under the restrictions given by the labor agreement. The problem is formulated as a mixed-integer program and solved with CPLEX. During the solution process individual lines-of-work are constructed for each physician. Using data from an anesthesia department, computational results indicate that high quality schedules can be obtained much more quickly than by current practice. <s> BIB124 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper presents an exact decomposition approach for an employee days-off scheduling problem of an homogeneous workforce under serval realistic days-off scheduling constraints. These constraints include the following: (1) each employee is assigned to three or four consecutive days-off per week, (2) each employee is assigned at least four consecutive days-off per month and (3) each employee is assigned at least a weekend off per month. A three-step decomposition method is used to obtain the work assignments while respecting the labor demands and the stated constraints. <s> BIB125 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> The current paper uses a scenario from logistics to show that modern heuristics, and in particular particle swarm optimization (PSO) can significantly add to the improvement of staff scheduling in practice. Rapid, sub-daily planning, which is the focus of our research offers considerable productivity reserves for companies but also creates complex challenges for the planning software. <s> BIB126 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper is concerned with the application of a GRASP approach to a nurse-scheduling problem in which the objective is to optimise a set of preferences subject to a set of binding constraints. The balance between feasibility and optimality is a key issue. This is addressed by using a knapsack model to ensure that the solutions produced by the construction heuristic are easy to repair. Several construction heuristics and neighbourhoods are compared empirically. The best combination is further enhanced by a diversification strategy and a dynamic evaluation criterion. Tests show that it outperforms previously published approaches and finds optimal solutions quickly and consistently. <s> BIB127 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper approaches the problem of modeling optimization problems containing substructures involving constraints on sequences of decision variables. Such constraints can be very complex to express with Mixed Integer Programming (MIP). We suggest an approach inspired by global constraints used in Constraint Programming (CP) to exploit formal languages for the modeling of such substructures with MIP. More precisely, we first suggest a way to use automata, as the CP regular constraint does, to express allowed patterns for the values taken by the constrained sequence of variables. Secondly, we present how context-free grammars can contribute to formulate constraints on sequences of variables in a MIP model. Experimental results on both approaches show that they facilitate the modeling, but also give models easier to solve by MIP solvers compared to compact assignment MIP formulations. <s> BIB128 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In developing work schedules, the job assignment flexibility exploits the variety of available skills, thus enabling the assignment of workers to perform different jobs. In this study, we investigate the problem of finding the mix of primary and secondary jobs in short term work schedules to meet, at minimum cost, the daily service requirements of an inter-city bus transit firm in Andra Pradesh India operating multiple fleet types. We formulate the problem as a set covering model with resource allocation constraints. We develop a branch-and-price procedure to solve the model. Computational results are provided. <s> BIB129 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Abstract : This paper presents a model and procedure for determining crew composition for a new technology like the Navy's DDX. Here the prototype DDX manpower scheduling problem is modeled as a project scheduling problem with multi-purpose resources (PSMPR) where multi-skilled sailors form teams to accomplish interrelated onboard tasks. A hybrid decomposition algorithm that incorporates constraint programming (CP) and a tabu search (TS) metaheuristic is developed for solving this NP-hard problem. In computational experiments, the performance of our hybrid algorithm is tested and compared with solutions found using mixed-integer linear programming (MILP) with CPLEX and with lower bounds obtained from a bin packing problem with conflicts (BPC). <s> BIB130 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> The quest for robust heuristics that are able to solve more than one problem is ongoing. In this paper, we present, discuss and analyze a technique called Evolutionary Squeaky Wheel Optimization and apply it to two different personnel scheduling problems. Evolutionary Squeaky Wheel Optimization improves the original squeaky wheel optimization's effectiveness and execution speed by incorporating two additional steps (selection and mutation) for added evolution. In the evolutionary squeaky wheel optimization, a cycle of analysis-selection-mutation-prioritization-construction continues until stopping conditions are reached. The aim of the analysis step is to identify below average solution components by calculating a fitness value for all components. The selection step then chooses amongst these underperformers and discards some probabilistically based on fitness. The mutation step further discards a few components at random. Solutions can become incomplete and thus repairs may be required. The repair is carried out by using the prioritization step to first produce priorities that determine an order by which the following construction step then schedules the remaining components. Therefore, improvements in the evolutionary squeaky wheel optimization is achieved by selective solution disruption mixed with iterative improvement and constructive repair. Strong experimental results are reported on two different domains of personnel scheduling: bus and rail driver scheduling and hospital nurse scheduling. <s> BIB131 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB132 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Elder care systems are facing increased costs, primarily because the elderly constitute a growing percentage of the population. Sweden publicly finances such systems; in 2005, the cost to taxpayers on a national level was 8.8 billion euros ($13 billion). The many customized aspects of scheduling home care workers to assist elderly and disabled citizens with their varying needs contribute to these costs. Laps Care, a system that was developed in 2002, uses operations research modeling to eliminate the manual planning of home care unit assignments. More than 200 units/organizations in Swedish municipalities use Laps Care each day to plan staff scheduling and routing for 4,000 home care workers. The system has increased operational efficiency by 10--15 percent; this corresponds to an annual savings of 20--30 million euros ($30--$45 million). In addition, the quality of home care for elderly citizens has improved. The City of Stockholm, with its 800,000 inhabitants, adopted Laps Care in 2006 and started a full implementation and rollout during 2008, thus adding 800 units and 15,000 home care workers to the system. The savings for the City of Stockholm will be 20--30 million euros ($30--$45 million). <s> BIB133 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> The creation of staff rosters for emergency shifts for doctors is a complex task. To construct good rosters, many restrictions (e.g. holydays and workload) have to be taken into account. These restrictions have been mathematically specified for a concrete case in order to solve the problem afterwards with a straightforward genetic algorithm. Thereby the main focus lays on two different mutation methods and the combination of them. The results of this procedure will be discussed in this work. <s> BIB134 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this paper we discuss a real-life problem in rail crew rostering. Specific emphasis is placed on the requirements of advanced approaches in rostering and the usage of optimization-based decision support. The modeling of the rostering problems is discussed including the treatment of constraints, the consideration of preferences, and the formulation of several objective functions. The specific solving method of the problem using an evolutionary algorithm and visualization and navigation tools for decision support are sketched briefly and some preliminary results are shown. Finally, some conclusions are presented. <s> BIB135 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Linear programming techniques can be used in constructing schedules but their application is not trivial. This in particular holds true if a trade-off has to be made between computation time and solution quality. However, it turns out that - when handled with care - mixed integer linear programs may provide effective tools. This is demonstrated in the successful approach to the benchmark constructed for the 2007 ROADEF computation challenge on scheduling problems furnished by France Telecom. <s> BIB136 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Organising shifts, or work rosters, is a problem that affects a large number of businesses where employees are subject to some kind of work rotation. Researchers in the fields of Operations Research and Artificial Intelligence have resorted to several different optimisation systems to solve the problem. The motivation for the medical-staff shift-rotation research presented in this paper stems from the needs of an actual hospital emergency department (HED) and from the observed growing staff of these services in Spain. The problem approach, which has been hardly dealt with in the literature, intends to automate the creation of time-tables by applying genetic algorithms (GAs) in an actual HED. HEDs work organisation becomes different because of the combination of shifts and 24-h duties. After knowing the HED workers' requirements (which will allow to identify the hard and soft constraints imposed to the problem) and after defining the adequate encoding to be used in the solutions, a heuristic-schedule builder -designed ad hoc to satisfy the hard constraints - produces an initial population of feasible solutions. Afterwards, iteratively, GA obtains new generations of feasible individuals, thanks to the use of a specific crossover operator, based in the exchange of whole work weeks, that operates together with a repair function. Once the optimum is reached, the results obtained are discussed as a function of the degree of satisfaction of the constraints under which the system operates and of the adaptability of the system as the constraints vary. <s> BIB137 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB138 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB139 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> The crew pairing problem (CPP) is one step of the airline crew scheduling process. The CPP consists of determining a minimum cost set of feasible pairings such that each flight is covered exactly once and side constraints are satisfied. In the industry, this problem has been traditionally solved by a heuristic three-phase (TP) approach that solves sequentially a daily, a weekly, and a monthly problem. The contribution of this paper is to show that the traditional approach is less efficient to solve the crew pairing problem when the flights schedule is not regular. In fact, we show that to obtain better quality solutions in less computational time it is better to skip the first two phases and directly solve the monthly problem using a rolling horizon (RH) approach based on column generation method. All experiments are tested on real data provided by a major airline company. <s> BIB140 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this paper, workload coverage is the problem of identifying a pattern of days worked and days off, along with the number of hours worked on each work day. This pattern must satisfy certain work-related constraints and fit best to a predefined workload. In our study, we formulate the problem of workload coverage as an optimization problem. We propose a number of models which take into consideration various staffing constraints. For each of these models, our study aims to find a compromise between an accurate workload coverage and the ability to solve the corresponding optimization problems in a reasonable time. Numerical experiments on each model are carried out and the results are presented. Interestingly, the nonlinear programming approaches are found to be competitive with linear programming ones. <s> BIB141 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This study develops a two-stage mathematical modeling for a nurse scheduling system wherein hospital management requirements, government regulations, and nursing staffs' shift preferences are incorporated. In the first stage, the nurse work and vacation schedules are arranged and genetic algorithm (GA) is used to solve for the optimal schedules and to check for any violation of government regulations, hospital management requirements, and the scheduling fairness. In the second stage, the nurse roster schedule is arranged and GA is further adopted to solve the optimal schedule. An empirical case study is performed and the results show that GA can be an efficient tool for solving the nurse scheduling problem. In addition, it can also be easily modified to suit different cases encountered in hospitals. <s> BIB142 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> The Skilled Workforce Project Scheduling Problem (SWPSP) is a complex problem of task scheduling and resource assignment that comes up in the daily management of many company Service Centres (SC). The SWPSP considers many real characteristics faced daily by the SC: client-company service quality agreements that establish maximum dates for the beginning and the end of tasks with penalties for delays, criticality levels indicating the client-priority in processing each task, generalized precedence relationships that can produce cycle structures, time period and percentage time lags and variable task durations depending on the worker executing the task. Furthermore, the SC workforce is made up of specialist workers characterised by efficiency levels showing their efficiency and speed executing the several types of tasks. Each worker has his or her own timetable. The main objective of the SWPSP is to quickly obtain a feasible plan of action satisfying maximum established dates and timetable worker constraints. Secondary objectives deal with the urgency levels imposed by the criticality task levels, to obtain well-balanced worker workloads and an efficient assignment of specialists to tasks. In this paper an efficient and quick hybrid genetic algorithm that combines local searches with genetic population management techniques is presented to manage the model. <s> BIB143 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Many rostering methods first create shifts from some given staffing levels, and after that create rosters from the set of created shifts. Although such a method has some nice properties, it also has some bad ones. In this paper we outline a method that creates rosters directly from staffing levels. We use a Branch-and-Price (B\&P) method to solve this rostering problem and compare it to an ILP formulation of the subclass of rostering problems studied in this paper. The two methods perform almost equally well. Branch-and-Price, though, turns out to be a far more flexible approach to solve rostering problems. It is not too hard to extend the Branch-and-Price model with extra rostering constraints. However, for ILP this is much harder, if not impossible. Next to this, the Branch-and-Price method is more open to improvements and hence, combined with the larger flexibility, we consider it better suited to create rosters directly from staffing levels in practice. <s> BIB144 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> A multi-skill staffing problem in a call center where the agent skill sets are exogenous and the call routing policy has well-specified features of overflow between different agent types is addressed. Constraints are imposed on the service level for each call class, defined here as the steady-state fraction of calls served within a given time threshold, excluded. An approximation of these service levels is developed that allows an arbitrary overflow mechanism and customer abandonment. A two-stage heuristic that finds good solutions to mathematical programs with such constraints is developed. The first stage uses search methods supported by the approximation. Because service level approximation errors may be substantial, the solution is adjusted in a second stage in which performance is estimated by simulation. Realistic problems of varying size and routing policy are solved. The proposed approach is shown to be competitive with (and often better than) previously available methods. [Supplementary materials... <s> BIB145 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> We consider the issue of call center scheduling in an environment where arrivals rates are highly variable, aggregate volumes are uncertain, and the call center is subject to a global service level constraint. This paper is motivated by work with a provider of outsourced technical support services where call volumes exhibit significant variability and uncertainty. The outsourcing contract specifies a Service Level Agreement that must be satisfied over an extended period of a week or month. We formulate the problem as a mixed-integer stochastic program. Our model has two distinctive features. Firstly, we combine the server sizing and staff scheduling steps into a single optimization program. Secondly, we explicitly recognize the uncertainty in period-by-period arrival rates. We show that the stochastic formulation, in general, calculates a higher cost optimal schedule than a model which ignores variability, but that the expected cost of this schedule is lower. We conduct extensive experimentation to compare the solutions of the stochastic program with the deterministic programs, based on mean valued arrivals. We find that, in general, the stochastic model provides a significant reduction in the expected cost of operation. The stochastic model also allows the manager to make informed risk management decisions by evaluating the probability that the Service Level Agreement will be achieved. <s> BIB146 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB147 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB148 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Previously published work has described the development of a hospital capacity simulation tool, PROMPT. PROMPT has now been adopted by a number of hospitals in the UK and is used for both strategic and operational planning and management of key hospital resources. The work, as presented here, extends the PROMPT functionality to consider in more detail workforce issues. In particular, working with some of the current hospital users, the research has focussed on detailed planning for calculating the size and skill-mix of inpatient nursing teams. The chosen methodology utilizes both simulation and optimization. Outputs from the PROMPT three-phase discrete event simulation are fed into a stochastic programme which suggests the optimal number of nurses to employ (whole time equivalents) by skill-mix and the corresponding numbers by shift. A novel feature of the tool is the ability to predict and compare nursing needs based on different methods of capturing patient-to-nurse ratios as currently adopted across the UK National Health Service. Illustrative results from one hospital demonstrate that although the overall sizes of nursing teams on different wards are of an acceptable level and comparable to the outputs from the simulation phase of the work, often the number of nurses employed at different grades is not well matched to patient needs and the skill-mix should be reconsidered. Results from the optimization phase of the work suggest that it is cost beneficial to increase the number of permanently employed nurses to account for fluctuations in demand and corresponding high costs of temporary (agency) nurses. The scenario functionality of the tool permits for the study of changing size and skill-mix as a consequence of changes in patient volumes, patient case-mix, numbers of beds and length of stay. <s> BIB149 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Nurse rostering is an important search problem with many constraints. In the literature, a number of approaches have been investigated including penalty function methods to tackle these constraints within genetic algorithm frameworks. In this paper, we investigate an extension of a previously proposed stochastic ranking method, which has demonstrated superior performance to other constraint handling techniques when tested against a set of constrained optimization benchmark problems. An initial experiment on nurse rostering problems demonstrates that the stochastic ranking method is better at finding feasible solutions, but fails to obtain good results with regard to the objective function. To improve the performance of the algorithm, we hybridize it with a recently proposed simulated annealing hyper-heuristic (SAHH) within a local search and genetic algorithm framework. Computational results show that the hybrid algorithm performs better than both the genetic algorithm with stochastic ranking and the SAHH alone. The hybrid algorithm also outperforms the methods in the literature which have the previously best known results. <s> BIB150 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB151 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB152 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> An important challenge within hyper-heuristic research is to design search methodologies that work well, not only across different instances of the same problem, but also across different problem domains. This article conducts an empirical study involving three different domains in combinatorial optimisation: bin packing, permutation flow shop and personnel scheduling. Using a common software interface (HyFlex), the same algorithms (high-level strategies or hyper-heuristics) can be readily run on all of them. The study is intended as a proof of concept of the proposed interface and domain modules, as a benchmark for testing the generalisation abilities of heuristic search algorithms. Several algorithms and variants from the literature were implemented and tested. From them, the implementation of iterated local search produced the best overall performance. Interestingly, this is one of the most conceptually simple competing algorithms, its advantage as a robust algorithm is probably due to two factors: (i) the simple yet powerful exploration/exploitation balance achieved by systematically combining a perturbation followed by local search; and (ii) its parameter-less nature. We believe that the challenge is still open for the design of robust algorithms that can learn and adapt to the available low-level heuristics, and thus select and apply them accordingly. <s> BIB153 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB154 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper proposes a construction heuristic and an adaptive large neighborhood search heuristic for the technician and task scheduling problem arising in a large telecommunications company. This problem was solved within the framework of the 2007 challenge set up by the French Operational Research Society (ROADEF). The paper describes the authors' entry in the competition which tied for second place. <s> BIB155 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper presents, formalizes and classifies working time accounts (WTAs), a means of achieving flexible production capacity through the flexible organization of working time. We propose linear programming models to plan working time, using WTA, at companies in the service industry. A computational experiment shows that the models can be solved for any capacity planning problems of reasonable size. <s> BIB156 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> We present a new implicit formulation for shift scheduling problems, using context-free grammars to model regulation in the composition of shifts. From the grammar, we generate an integer programming (IP) model allowing the same set of shifts as Dantzig’s set covering model. When solved by a state-of-the- art IP solver on problems allowing a small number of shifts, our model, the set covering formulation and a typical implicit model from the literature yield comparable solving times. Moreover, on instances where many shifts are allowed, our model is superior and can encode a wider variety of constraints. Among others, multi-activity cases, which cannot be modeled by existing implicit formulations, can easily be captured with grammars. <s> BIB157 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Operations management of subway systems is associated with combinatorial optimization problems (i.e. crew and train scheduling and rostering) which belong to the np-hard class of problems. Therefore, they are generally solved heuristically in real situations. This paper considers the problem of duty generation, i.e. identifying an optimal trips set that the conductors should complete in one workday. With regard to operational and labor conditions, the problem is to use the lowest possible number of conductors and minimize total idle time between trips. The problem is modeled and solved using a constructive hybrid approach, which has the advantage of visualizing a solution construction similar to the manual approach typically used. Our approach takes advantage of the benefits offered by evolutionary methods, which store a candidate solutions population in each stage, thus controlling the combinatorial explosion of possible solutions. The results thus obtained for problems similar to those that are solved manually in the Santiago Metro System were compared with two alternative approaches, based on tabu search and a greedy method. The hybrid method produced solutions with the minimum number of duties in six of the ten problems solved. However, the tabu search method provided better results in terms of idle time than either the hybrid method or the greedy method. <s> BIB158 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper addresses the problem of scheduling ambulance crews in order to maximize the coverage throughout a planning horizon. The problem includes the subproblem of locating ambulances to maximize expected coverage with probabilistic response times, for which a tabu search algorithm is developed. The proposed tabu search algorithm is empirically shown to outperform previous approaches for this subproblem. Two integer programming models that use the output of the tabu search algorithm are constructed for the main problem. Computational experiments with real data are conducted. A comparison of the results of the models is presented. <s> BIB159 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper is concerned with the problem of nurse rostering within hospitals. We analyse a class of four benchmark instances from the nurse rostering literature to provide insight into the nature of the problem. By highlighting the structure of the problem we are able to reduce the relevant solution space. A mixed integer linear programme is then able to find optimal solutions to all four instances of this class of benchmark problems, each within half an hour. Our second contribution is to extend current mathematical approaches to nurse rostering to take better account of the practical considerations. We provide a methodology for handling rostering constraints and preferences arising from the continuity from one scheduling period to the next. <s> BIB160 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Workforce management is comprised of several phases, such as working time model generation and personnel scheduling. The combination of these phases has significant potential, especially for volatile personnel demand. This article shows that the concepts for the automatic generation of working time models already used in retail can be transferred to personnel scheduling in the logistics industry. Through this, the assignment of personnel can be accurately adapted to personnel demand. The results suggest the use of heuristics, especially meta-heuristics such as the evolution strategy or constructive methods which are adapted to the problem at hand. <s> BIB161 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper investigates the integration of the employee timetabling and production scheduling problems. At the first level, we manage a classical employee timetabling problem. At the second level, we aim at supplying a feasible production schedule for a set of interruptible tasks with qualification requirements and time-windows. Instead of hierarchically solving these two problems as in the current practice, we try here to integrate them and propose two exact methods to solve the resulting problem. The former is based on a Benders decomposition while the latter relies on a specific decomposition and a cut generation process. The relevance of these different approaches is discussed here through experimental results. <s> BIB162 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Flexibility in workforce planning is one of the best ways to respond to fluctuations of the demand. This paper proposes a flexible mixed integer linear programming (MILP) model to solve a multiple-shift workforce planning problem under annualized working hours. The model takes into account laws and collective agreements that impose constraints on overtime and holidays. We consider possible gradual hiring of full time and partial time workers. Several objectives are pursued such as balancing the workload of the employees or minimizing the workforce size. Computational experiments on a real life problem demonstrate the effectiveness of the model. <s> BIB163 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> I consider the problem of weekly assignment of shifts to operators. The shifts are to be assigned by seniority (or by any other employee hierarchy), but every employee is guaranteed to receive at least one shift. I propose a practical solution method to this problem that guarantees a feasible solution. As an application, the solution method is applied to the data provided in the literature on weekly shift assignment of the operators of the New Brunswick Telephone company. The solution method is also applied to 100 randomly generated problems. The results show that the solution method produces close-to-optimal solutions. <s> BIB164 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB165 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Numerous papers based on various search methods across a wide variety of applications have appeared in the literature over recent years. Most of these methods apply the following same approach to address the problems at hand: at each iteration of the search, they first apply their search methods to generate new solutions, then they calculate the objective values (or costs) by taking some constraints into account, and finally they use some strategies to determine the acceptance or rejection of these solutions based upon the calculated objective values. However, the premise of this paper is that calculating the exact objective value of every resulting solution is not a must, particularly for highly constrained problems where such a calculation is costly and the feasible regions are small and disconnected. Furthermore, we believe that for newly-generated solutions, evaluating the quality purely by their objective values is sometimes not the most efficient approach. In many combinatorial problems, there are poor-cost solutions where possibly just one component is misplaced and all others work well. Although these poor-cost solutions can be the intermediate states towards the search of a high quality solution, any cost-oriented criteria for solution acceptance would deem them as inferior and consequently probably suggest a rejection. To address the above issues, we propose a pattern recognition-based framework with the target of designing more intelligent and more flexible search systems. The role of pattern recognition is to classify the quality of resulting solutions, based on the solution structure rather than the solution cost. Hence, the general contributions of this work are in the line of "insights" and recommendations. Two real-world cases of the assignment problem, i.e. the hospital personnel scheduling and educational timetabling, are used as the case studies. For each case, we apply neural networks as the tool for pattern recognition. In addition, we present our theoretical and experimental results in terms of runtime speedup. <s> BIB166 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Retail is traditionally labour-intensive. Demand-oriented workforce management has great significance due to the amount of competition which enforces a strict cost management while keeping a good service level. Thus, highly flexible working time models are of particular importance. Our project addresses the question how to automatically and simultaneously assign staff to workstations and generate optimised working time models under constraints and on the basis of fluctuating personnel demand. The planning is completed for an entire year in order to assess adapted versions of the evolution strategy and particle swarm optimisation. A commercial constructive method is used as benchmark. <s> BIB167 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB168 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB169 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Unlike manufacturing, where standard shifts and days off are the rule, the service industry operates every day of the week across a month and a year. To maintain the morale and productivity of the workers in the service industry, the weekend off requirements, one of the important work preferences for the workers, should be respected and balanced for a longer planning horizon beyond a week. This paper deals with the monthly tour scheduling problem with mixed skills considering the weekend off requirements in contrast to the weekly planning horizon that is typical in most literature. The objective is to obtain the most economical mix of types of workers satisfying the patterns of demands for the workers and desired work characteristics. Two model formulations are developed based on implicit programming techniques. One model uses a general integer programming (GIP) formulation and assigns the lunch break hours aggregately to the workers based on the worker types. The other one adopts a binary integer programming (BIP) formulation and assigns the lunch break hours explicitly to the individual workers. The effectiveness of the two models is illustrated by the numerical tests and the results show that the BIP formulation is more efficient than the GIP formulation. <s> BIB170 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB171 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper addresses operation models for workforce planning for check-in systems at airports. We characterize different tasks of the hierarchical workforce planning problem with time-dependent demand. A binary linear programming formulation is developed for the fortnightly tour scheduling problem with flexible employee contracts. This binary programming model is solved for optimality by CPLEX for real-world demand scenarios with different workforce sizes. The numerical study analyzes the impact of the degree of flexibility and economies of scale. The model formulation is extended to generate convenient tours with regard to employee preferences. <s> BIB172 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB173 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this study, a mathematical programming model is proposed for scheduling problem of nurses' labor shifts. The developed mathematical programming model's aim is to minimize nurses' total idle waiting time during a week planning horizon. In this model, investigated constraints are as follows: (1) Maximum total working time a week for each nurse must not be exceeded. (2) After a nurse works a shift, the nurse can be assigned to another shift after two shifts at least. This constraints-set ensures resting of the nurse after the nurse works a shift. (3) Total number of nurses worked for each shift must be controlled with maximum and minimum bounds given for number of nurses for each shift. In this manner, total number of nurses worked for each shift is between maximum and minimum limit-values given for each shift. This constraint ensures flexibility to the user to determine number of nurses for each shift. (4) The decision variable that shows nurse-shift assignment pairs is 0 or 1. In this study, maximum total working time a week for a nurse, total number of nurses in a health service, maximum and minimum numbers of nurses worked a shift are user-specified parameters. In this way, this model can be adapted for the studies with different values of these parameters. In this study, the developed model is illustrated using a numerical example and then LINGO8.0 software is used to ensure the global optimum solution of the developed model. Results and also sensitivity analysis carried out for this example are presented in the study. <s> BIB174 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB175 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB176 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB177 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> We present a strategic model to solve the long-term staffing problem of physicians in hospitals using flexible shifts. The objective is to minimize the total number of staff subject to several labor agreements. A wide range of legal restrictions and facility-specific staffing policies are considered. In general, the model is capable to incorporate different experience levels. In the simplest version the model decides about the number of staff for two experience levels, i.e. the number of residents (low experience) versus specialists (high experience). Shifts are constructed implicitly by the model and may have different starting times and several lengths. This allows more flexibility in the scheduling process. We formulate the problem as a mixed-integer program and solve it applying a column generation based heuristic. Using data provided by an anesthesia department of an 1100-bed hospital, computational results demonstrate the usage of the model as decision supporting tool when staffing decision are made by hospital management. <s> BIB178 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> A common practice in personnel tour scheduling is to limit the number of permissible daily shift starting times. Accordingly, an important subproblem that arises in tour-scheduling problems is the selection of those starting times that are conducive to efficient satisfaction of labour requirements. A previously published heuristic for this problem is sequential in nature, whereby a subset of starting times is selected in the first stage and tours are constructed using the chosen starting times in the second stage. We propose an integrative procedure that overcomes many of the limitations inherent in the sequential approach. Our procedure, which uses tabu search for starting time selection and a cutting plane method for tour construction, was compared to integer programming and the previously published heuristic in two experiments using test conditions from the airport staffing literature. Although all methods performed well when the labour requirement patterns were consistent across days of the week, the new procedure yielded the best performance when such patterns were inconsistent. <s> BIB179 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Scheduling of heterogeneous, part-time, service employees with limited availability is especially challenging because employees have different availability and skills, and work different total work hours in a planning period, e.g., a week. The constraints typically are to meet employee requirements during each hour in a planning period with shifts which have a minimum & maximum length, and do not exceed 5 work days per week for each employee. The objectives typically are to minimize over staffing and to meet the target total work hours for each employee during the planning period. We decompose this problem into (a) determining good shifts and then (b) assigning the good shifts to employees, and use a set of small integer linear programs to solve each part. We apply this method to the data given in a reference paper and compare our results. Also, several random problems are generated and solved to verify the robustness of our solution method. <s> BIB180 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB181 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB182 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> We examine a workforce assignment problem arising in the multi-project environment of companies. For a given set of workers and for a given set of projects, we want to find one team of workers for each project that is able to satisfy the project workload during each period of project execution. The aim is to minimize average team size. We outline two mixed integer linear programming (MIP) formulations and introduce two heuristic approaches to this problem. A numerical study indicates the performance of the approaches and provides managerial insights into flexibility issues. <s> BIB183 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> A practical spreadsheet-based scheduling method is developed to determine the optimal allocation of service agents to candidate tour types and start times in an inbound call center. A stationary Markovian queueing model with customer abandonment is employed to determine required staffing levels for a sequence of time intervals with varying call volumes, handling times, and relative agent availabilities. These staffing requirements populate a quadratic programming model for determining the distribution of agent tours that will maximize the fraction of offered calls beginning service within a target response time, subject to side constraints on tour type quantities. The optimal distribution is scaled to reflect the total number of scheduled agents, and a near-optimal integer solution is derived using rounding thresholds found by successive one-dimensional searches. This novel approach has been successfully implemented in large service centers at Qwest Communications and could easily be adapted to other operational environments. <s> BIB184 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Abstract This paper presents a new mixed integer nonlinear stochastic staff scheduling model, where the workforce demands are under uncertainty, with a general probability distribution. To validate the proposed model, a simulation technique is employed and an optimization technique is used to solve the resulted model. As the problem is combinatorial, a meta-heuristic approach, i.e. a genetic algorithm, is implemented with tuned parameters, using the Taguchi design of experiment method. The preliminary results indicate that the proposed method of this paper can be effectively used to manage staff schedules for many real-world applications. <s> BIB185 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB186 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Job rotation is an organizational strategy increasingly used in manufacturing systems as it provides benefits to both workers and management in an organization. Job rotation prevents musculoskeletal disorders, eliminates boredom and increases job satisfaction and morale. As a result, the company gains a skilled and motivated workforce, which leads to increases in productivity, employee loyalty and decreases in employee turnover. A multi-criteria genetic algorithm is employed to generate job rotation schedules, with considering the most adequate employee-job assignments to prevent musculoskeletal disorders caused by accumulation of fatigue. The algorithm provides the best adequacy available between workers and the competences needed for performing the tasks. The design of the rotation schedules is based not only on ergonomic criteria but also on issues related to product quality and employee satisfaction. The model includes the workers’ competences as a measure for the goodness of solutions. <s> BIB187 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> A novel nurse rostering model is developed to represent real world problem instances more accurately. The proposed model is generic in the sense that it allows modelling of essentially different problem instances. Novel local search neighbourhoods are implemented to take advantage of the problem properties represented by the model. These neighbourhoods are used in a variable neighbourhood search and in an adaptive large neighbourhood search algorithm. The performance of the solution method is evaluated empirically on real world data. The proposed model is open to further extensions for covering personnel planning problems in different sectors and countries. <s> BIB188 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper introduces an original planning model which integrates production, human resources and cash management decisions, taking into account the consequences that decisions in one area may have on other areas and allowing all these areas to be coordinated. The most relevant characteristics of the planning problem are: (1) production capacity is a non-linear function of the size of the staff; (2) firing costs may depend on the worker who is fired; (3) working time is managed under a working time account (WTA) scheme, so positive balances must be paid to workers who leave the company; (4) there is a learning period for hired workers; and (5) cash management is included. A mixed integer linear program is designed to solve the problem. Despite the size and complexity of the model, it can be solved in a reasonable time. A numerical example, the main results of a computational experiment and a sensibility analysis illustrate the performance and benefits of the model. <s> BIB189 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper deals with scheduling complex tasks with an inhomogeneous set of resources. The problem is to assign technicians to tasks with multi-level skill requirements. Here, the requirements are merely the presence of a set of technicians that possess the necessary capabilities. An additional complication is that a set of combined technicians stays together for the duration of a work day. This typically applies to scheduling of maintenance and installation operations. We build schedules by repeated application of a flexible matching model that selects tasks to be processed and forms groups of technicians assigned to combinations of tasks. The underlying mixed integer programming (MIP) model is capable of revising technician-task allocations and performs very well, especially in the case of rare skills. <s> BIB190 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In September 2008 new regulations for managing heavy vehicle driver fatigue entered into force in Australia. According to the new regulations there is a chain of responsibility ranging from drivers to dispatchers and shippers and thus, carriers must explicitly consider driving and working hour regulations when generating truck driver schedules. This paper presents and studies the Australian Truck Driver Scheduling Problem (AUS-TDSP) which is the problem of determining whether a sequence of locations can be visited within given time windows in such a way that driving and working activities of truck drivers comply with Australian Heavy Vehicle Driver Fatigue Law. Highlights? We present a model of the Australian Heavy Vehicle Driver Fatigue Law which regulates driving and working hours of truck drivers in Australia. ? We present an exact solution approach for the Australian Truck Driver Scheduling Problem which is guaranteed to find a truck driver schedule complying with the regulation if such a schedule exists. ? We present fast heuristics which require only a small fraction of the computational effort required by the exact algorithm. ? The most effective heuristic can find a feasible schedule for almost all of the instances for which a feasible schedule exists; only in rare cases a feasible schedule can only be found by the exact algorithm. ? The technology developed and discussed in this paper can form the foundation for a successful application for accreditation required in order to operate according to the Basic Fatigue Management or the Advanced Fatigue Management option of the regulation. <s> BIB191 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper presents our investigations on a hybrid constraint programming based column generation (CP-CG) approach to nurse rostering problems. We present a complete model to formulate all the complex real-world constraints in several benchmark nurse rostering problems. The hybrid CP-CG approach is featured with not only the effective relaxation and optimality reasoning of linear programming but also the powerful expressiveness of constraint programming in modeling the complex logical constraints in nurse rostering problems. In solving the CP pricing subproblem, we propose two strategies to generate promising columns which contribute to the efficiency of the CG procedure. A Depth Bounded Discrepancy Search is employed to obtain diverse columns. A cost threshold is adaptively tightened based on the information collected during the search to generate columns of good quality. Computational experiments on a set of benchmark nurse rostering problems demonstrate a faster convergence by the two strategies and justify the effectiveness and efficiency of the hybrid CP-CG approach. <s> BIB192 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> An empirical crew rostering problem drawn from the customer service section of a department store in southern Taiwan is addressed in this paper. The service section established relevant service facilities and functions to provide services for customers as well as distinguished guests and visitors. The crew rostering task is concerned with assigning multi-functional workers to different types of job and scheduling working shifts for each worker within a given time horizon, where the available and demand workforce vary from one shift to another. The current crew rostering method is a seniority orientation method. In developing the roster under current method, lines of job are generated and then bids are taken in order of decreasing seniority. The most senior worker has the widest range of job lines from which to select so as to best satisfy his/her preference. Successive crew members bid for the remaining lines of job. The current method has some drawbacks. To overcome the drawbacks, this paper develops a problem-specific approach with three stages to deal with the crew rostering problem, making it more equitable and personalized for workers by considering the management goals concerning worker-job suitability, worker-worker compatibility and worker-shift fondness. Due to the vagueness of job characteristics and the personal attributes, fuzzy method is used to improve the evaluation results of suitability, compatibility and fondness. The utility similarities of fuzzy assessments with the linguistic grade of very good are used to measure the fitness grade for the management goals. A linear goal programming model is proposed to fulfill the ''efficient assignment/match from the right'' policy. The proposed approach ensures the right workers are assigned to the right jobs, the right workers are placed together in a job and the pleasing working shifts are given to the workers. An illustrative application demonstrates the implementation of the proposed approach. <s> BIB193 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Scheduling IT projects and assigning the project work to human resources are an important and common tasks in almost any IT service company. It is particularly complex because human resources usually have multiple skills. Up to now only little work has considered IT-specific properties of the project structure and human resources. In this article, we present an optimization model that simultaneously schedules the activities of multiple IT projects with serial network structures and assigns the project work to multiskilled internal and external human resources with different efficiencies. The goal is to minimize costs. We introduce a metaheuristic that decomposes the problem into a binary scheduling problem and a continuous staffing problem where the latter is solved efficiently by exploiting its underlying network structure. For comparison, we solve the mixed–binary linear program with a state–of–the–art commercial solver. The impacts of problem parameters on computation time and solution gaps between the metaheuristic and the solver are assessed in an experimental study. Our results show that the metaheuristic provides very favorable results in considerable less time than the solver for midsize problems. For larger problems, it shows a similar performance while the solver fails to return feasible solutions. © 2012 Wiley Periodicals, Inc. Naval Research Logistics 59: 111–127, 2012 <s> BIB194 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In this paper we introduce the Personnel Task Scheduling Problem (PTSP) and provide solution algorithms for a variant of this problem known as the Shift Minimisation Personnel Task Scheduling Problem (SMPTSP). The PTSP is a problem in which a set of tasks with fixed start and finish times have to be allocated to a heterogenous workforce. Personnel work in shifts with fixed start and end times and have skills that enable them to perform some, but not all tasks. In other words, some personnel are qualified to only perform a subset of all tasks. The objective is to minimise the overall cost of personnel required to perform the given set of tasks. In this paper we introduce a special case in which the only cost incurred is due to the number of personnel (shifts) that are used. This variant of the PTSP is referred to as the Shift Minimisation Personnel Task Scheduling Problem (SMPTSP). While our motivation is a real-life Personnel Task Scheduling Problem, the formulation may also be applied to machine shop scheduling. We review the existing literature, provide mathematical formulations, and develop a heuristic approach for the SMPTSP. <s> BIB195 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB196 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Staff rostering is a major challenge in the service sector, where exploitation costs are essentially made up of staffing costs. Searching for an optimum has direct economic returns but the rosters must satisfy numerous legal constraints. This paper presents work on an exact approach using branch-and-price methods on a concrete situation. We develop three MILP models and extend them with valid inequalities to two cases. Their computation results on a set of 960 tests covering several scenarios will then be compared and analyzed. <s> BIB197 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB198 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Real applications in shift scheduling often require handling rules such as multiple breaks, flexible shift lengths, overtime, multiple activities, among others. Because these rules demand a high level of flexibility, we model the problem as a Multi-Activity Shift Scheduling Problem (MASSP), where multiple activities can be scheduled in a shift. To solve the MASSP, we propose a column generation-based approach. The auxiliary problem is modeled as a Shortest Path Problem with Resource Constraints (SPPRC), where most difficult constraints are embedded in the underlying graph. To illustrate the solution approach, we present our experience solving a real-world problem from a large parking lot operator that schedules security staff and cashiers among several parking lots in Bogota (Colombia). The results show a significant reduction on the staffing total costs and on man-hours used. <s> BIB199 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB200 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB201 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Stability describes the grade of the ability of a plan to remain feasible and cost efficient under variations of the operating environment without major modifications to the plan. In airline traffic delays often lead to additional delays, because of interdependencies between different resources such as ai rcraft, crews and airport facilities. In this paper we focus on reactionary delays that result from crews changing aircraft. Based on a stochastic model for delay propagation we propose an indicator for stability of airline crew and aircraft schedules. This indicator is used to generate more robust aircraft and crew schedules. An integrated formulation for the aircraft and crew scheduling problem results in a non-linear stochastic recourse function. We decompose this formulation into separate linear problems connected by the objective function. The decomposed stochastic problem may be solved using a heuristic iterative approach based on column generation and dynamic programming for the recourse functions. In order to evaluate the robustness of the generated schedules and to compare with a deterministic approach for robust scheduling we use an also presented simulation model. <s> BIB202 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB203 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> This paper addresses the problem of flexible shift scheduling of service employees at mail processing and distribution centers. Our main objective is to determine staffing levels for different worker categories subject to a host of union restrictions and general labor regulations. The problem is modeled as a mixed-integer linear program and solved with branch and price algorithm. Using real data provided by a US Postal Service a variety of computational experiments are performed to quantify the benefits of scheduling flexibility. These include different shift starting times, different shift lengths, a lunch break allowance, and different days-off assignments. In addition, the ratio between regular and flexible workers is varied to investigate its effect on costs. The results show the efficiency of the proposed procedure. Finally, we offer some managerial insights gained from the analysis. <s> BIB204 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> The efficient and effective management of nursing personnel is of critical importance in a hospital's environment comprising a vast share of the operational costs. The adopted nurse workforce practices and policies highly affect the nurses' working conditions and the provided quality of care. Policy decisions on the staffing level have an impact on the outcome of the scheduling level and vice versa. Isolated reasoning typically leads to suboptimal decisions often resulting in ineffective outcomes of care. In order to overcome these inefficiencies, we propose in this paper a new integrative nurse staffing and shift scheduling approach. We test and assess the benefits of our approach in a reallife environment. Moreover, we examine the impact of several personnel policies on the staffing decision. <s> BIB205 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> Manpower scheduling is a complicated problem to solve that strives to satisfy employers’ objectives and employees’ preferences as much as possible by generating fairly desirable schedules. But sometimes, objectives and preferences may not be determined precisely. This problem causes manpower scheduling takes the fuzzy nature. This paper presents a new fuzzy multi-objective mathematical model for a multi-skilled manpower scheduling problem considering imprecise target values of employers’ objectives and employees’ preferences. Hence, a fuzzy goal programming model is developed for the presented mathematical model and two fuzzy solution approaches are used to convert the fuzzy goal programming model to two single-objective models. Since the complexity of a manpower scheduling problem is NP-hard, the single-objective models are solved by two meta-heuristics, namely particle swarm optimization and elite tabu search. Eventually, the performance of the proposed algorithms is verified and the results are compared with each other to select the best schedules. <s> BIB206 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <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> BIB207 </s> Personnel scheduling: A literature review <s> Solution method and uncertainty incorporation <s> In practice nurse rostering problems are often too complex to be expressed through available academic models. Such models are not rich enough to represent the variegated nature of real world scenarios, and therefore have no practical relevance. This article focuses on two particular modelling issues that require careful consideration in making academic nurse rostering approaches re-usable in a real world environment. First: introducing several complex problem characteristics, resulting in a rich, generic model. A detailed description is provided for researchers interested in using this new model. We also present a novel benchmark dataset based on this rich model. Second: the consideration of a consistent evaluation procedure that corresponds to realistic quality measurement. These contributions will enable faster implementation of academic nurse rostering achievements in real hospital environments. A suite of hyper-heuristics is presented. These are capable of solving these rich personnel rostering problems using the presented evaluation procedures. Their performance is compared to that of another meta-heuristic. <s> BIB208
The literature on personnel scheduling exhibits a wide range of research methodologies that combine a certain type of analysis with some solution or evaluation technique. A large number of papers are classified into mathematical programming categories such as integer programming, linear programming, dynamic programming, goal programming, etc., or as constructive or improvement heuristics (Table 13 ). Other categories are simulation, constraint programming and queuing. In "Other", we classify the less frequent solution methods such as piecewise linear approximation BIB094 , analytical hierarchy process (AHP) BIB062 BIB042 BIB120 , spreadsheet models BIB095 , DEA BIB121 , etc. Usually they are used to find the minimal staff size in solving small problems, to analyze demand patterns or to roster personnel members by hand after the optimal shift patterns have been computed. Other 34, BIB121  BIB096 BIB043  BIB062 BIB122 BIB176 BIB095 BIB146 BIB042 BIB120 Mathematical programming approaches group most of the considered solution methods. In these approaches, the personnel scheduling problem is modeled as a linear, integer or mixed integer program. The set covering formulation for the general shift scheduling problem, introduced by Dantzig (Section 1), is still very popular among researchers. This formulation permits researchers to add a number of constraints based on their own particular needs. Many of these variations to the set-covering model tend to create linear integer programs with a huge number of variables. As discussed by Ernst et al. BIB003 , researchers are used to trying to overcome these large scale formulations by decomposition techniques and heuristic algorithms. Several large-scale problems benefit from a decomposition method in solving the problem. Decomposition methods essentially consider the problem in two parts, one with the "easy" and one with the more "complicating" constraints. Detienne et al. BIB123 present two cut generation based approaches for a particular employee timetabling problem. One cut generation scheme is used for heuristic resolution and the other for exact resolution. The exact cut generation scheme is based on applying Benders' decomposition, where the relaxed master problem is a multi-dimensional multichoice knapsack problem and every sub-problem is a b-matching problem. Bard and Wan BIB097 develop a multi-stage approach to determining the optimal size and composition of a permanent workforce needed to run a facility. One of the alternatives is based on the idea of partitioning the workstation groups into manageable clusters and then solving them in series. In a second paper BIB044 , they study the task assignment problem and develop a solution method that decomposes the full problem into seven daily IP sub-problems in order to obtain greater computational tractability. A similar approach is followed by Brunner et al. BIB124 , who decompose the shift scheduling problem of physicians into weekly segments. When column generation is applied, large linear programming models can be solved to optimality without holding all columns (variables) in the model at once. Column generation establishes a lower limit to the solution which is guaranteed to be LP optimal. In each iteration, a linear program with only a small subset of the decision variables, known as the restricted master problem, is created. Using the current dual vector, a pricing sub-problem is solved to identify variables that may potentially improve the current solution based on their reduced costs. Branch-and-price algorithms combine an LP-based branch-and-bound algorithm with a column generation algorithm to solve each LP relaxation. To take advantage of the column generation approach, the pricing sub-problems should be easy to solve quickly and branching rules should not destroy the structure of the pricing sub-problem BIB063 . Beliën and Demeulemeester BIB098 show how the column generation technique, often employed for solving nurse scheduling problems, can easily be extended to integrate building both nurse and surgery schedules. The approach involves the solution of two types of pricing problems. In a second paper, Beliën and Demeulemeester BIB064 present two ways of decomposing a staff scheduling problem by using column generation. In the first approach, decomposition takes place on the staff members, whereas in the second approach decomposition takes place on the activities that have to be performed by the staff members. In BIB004 , Eitzen et al. present a model for the generation of personnel rosters for a very general class of non-hierarchical skill level situations. Since the number of possible tours may exceed memory capacity requirements, they compare a branch-and-price method with a reduced column subset and column expansion method in order to generate cost-effective solutions. Branch-and-price methods have also been applied to schedule feasible trips carried out by train drivers BIB065 , general personnel scheduling problems BIB005 , nurse scheduling problems  , etc. In addition to these decomposition methods, authors have used other exact methods to tackle the difficult (mixed) integer programming problem. Adding strong valid inequalities can be very effective in reducing the optimality gap BIB006 . Besides adding cutting plane inequalities, it can be worth the effort to design special branching rules BIB006 or tighter LP-bounds BIB147 through problem reformulation or cutting plane inequalities. Not all problems related to personnel scheduling are modeled with a set-covering formulation. Jarray BIB125 presents an exact decomposition approach for an employee days off scheduling problem in relation to a homogeneous workforce. A three-step decomposition method is used to obtain the work assignments, while respecting the labor demands and a pre-specified number of workdays per employee over the planning horizon. The rests assignment corresponds to the feasible flow problem on a bipartite network. Moz and Pato BIB007 solve the problem of rerostering nurse schedules with a new multi-commodity flow model, a model shared by Cappanera and Gallo  in order to find a work assignment for airline crew members within a given time horizon. Other maximum flow problems can be found in   . Metaheuristics form an important class of solution methods used to solve the personnel scheduling problem. Metaheuristics are designed to tackle complex optimization problems where other optimization methods have failed to be either effective or efficient. The practical advantage of metaheuristics lies in both their effectiveness and their general applicability. The effectiveness lies in the production of reasonably good feasible solutions within a limited amount of running time, whereas mathematical programming techniques run the risk of not returning any feasible solution for a long time. However, using metaheuristics also results in a number of drawbacks, since they cannot demonstrably produce optimal solutions nor can they demonstrably reduce the search space  . Researchers tend to prefer tabu search and genetic algorithms to the use of simulating annealing algorithms. In addition to these three general classes, a lot of alternative heuristics have been developed for dealing with the personnel scheduling problem: scatter search BIB148 BIB029 BIB045  , iterated local search BIB008  , variable neighborhood search   , particle swarm optimization BIB066  BIB126 , memetic algorithms  , electromagnetic meta-heuristics  , neural networks BIB009 , ant colony optimization BIB067 , greedy random adaptive search procedure (GRASP) BIB127 , hill-climbing BIB046 , hyper-heuristics BIB030 , etc. When simulation is used in personnel scheduling problems, researchers favor discrete event simulation (DES) over Monte Carlo simulation. Simulation methods can help researchers to validate their deterministic optimization approaches, to estimate labor requirements, etc. Harper et al. BIB149 use both simulation and optimization to define the size and skill-mix of nursing teams. Outputs from the three-phase discrete event simulation are fed into a stochastic program which suggests the optimal number of nurses to employ (whole time equivalents) according to skill-mix and the corresponding numbers according to shift. Qi and Bard BIB031 present a workforce simulation system designed to help management understand both the flow of mail through a mail processing work center and the consequent need for labor. The system couples simulation with optimization in an iterative fashion. Yang et al. BIB068 examine an environment where both cross training and flexible workdays are available to respond to workload variability. They use Monte Carlo simulation in order to simulate the operation of a job shop with both cross training and flexible workdays. The highly constrained personnel scheduling problem offers an ideal framework for the use of constraint programming methods. These methods originate from Artificial Intelligence research and are exact methods that guarantee feasible solutions for constraint satisfaction problems or optimal solutions for constraint optimization problems. Côté et al.  use constraint programming and integrate it with mixed integer programming models in order to express constraints over sequences of decision variables, represented as a network flow problem. Other formal languages for integer programming formulations of shift scheduling problems are presented in BIB128 . In BIB047 , constraint programming is combined with column generation and a new optimization constraint is introduced. Qu and He  apply a hybrid constraint programming approach to a nurse rostering problem. They decompose the problem into weekly sub-problems, modeled as a constraint satisfaction problem. Then an iterative forward search is used to extend the sub-solutions to form complete solutions. In the second stage, a variable neighborhood search is used to further improve the solution. Constraint programming algorithms can also be used for the construction of rotating schedules BIB010 . Queuing methods mainly occur in call center applications BIB069 BIB121 BIB096 BIB032 , where they are used to determine call center staffing levels to satisfy specific service-level criteria. Wallace and Whitt BIB032 develop an algorithm based on queuing methods and simulation for both routing and staffing, aiming to minimize the total staff. Alfares BIB069 prefers a queuing model over simulation methods to estimate hourly staffing demands. An IP model is then constructed to find the optimum employee tour schedules that satisfy labor requirements with minimum cost. The considered solution techniques can also be combined to increase the efficiency of the approach. A nice example is given in the paper of de Matta and Peters BIB129 . They study the problem of finding the mix of primary and secondary jobs in short term work schedules to meet, at minimum cost, the daily service requirements of an inter-city bus transit firm in India. The problem is formulated as a set-covering model with resource allocation constraints. The number of columns (integer variables) representing all potential feasible work schedules can be extremely large. By employing the column generation method, the linear programming relaxation of the master problem can be solved optimally. The pricing problem, used to generate new columns, is a resource-constrained shortest path problem. They decompose the pricing problem into a number of sub-problems, one per driver category. The procedure used to solve the pricing problem is a heuristic procedure, combining Lagrangian relaxation and tabu search. Burke et al.  present a hybrid model of integer programming and variable neighborhood search (VNS) for highly-constrained nurse rostering problems. The IP is used to solve a sub-problem including all hard constraints and a subset of soft constraints. The VNS is then used as a post-processing improvement procedure. The satisfaction of the constraints that are not included in the subset would be the major concern in designing the VNS's neighborhood structures. Li and Womer BIB130 describe a hybrid decomposition algorithm that incorporates constraint programming and a tabu search metaheuristic for solving the NP-hard project scheduling problem with multi-purpose resources where multi-skilled sailors form teams to accomplish interrelated onboard tasks. One classification field that has not been discussed in any of the review papers is the incorporation of uncertainty. Deterministic staffing and scheduling approaches ignore every form of uncertainty, whereas stochastic approaches try to incorporate it. In our classification, we define three main categories of uncertainty: • Uncertainty of demand: indicates the unpredictable workload. For example, in a maintenance division, one does not know upfront how long it will take to fix a certain problem. Other examples are the length of calls in a call center, the number of patients in a hospital, etc.; • Uncertainty of arrival: points at the unpredictable arrival pattern of the workload. This includes, for instance, the distribution of failures over time of a specific machine (part) or the arrival of calls; • Uncertainty of capacity: represents deviations between the planned and the actual manpower. In Table 14 , we list the relevant manuscripts based on their uncertainty incorporation. Deterministic 2, BIB131 BIB099 BIB100  BIB066 BIB070 BIB071 BIB101 BIB048 BIB065 BIB187 BIB207 BIB177 BIB033 BIB011 BIB012 BIB150 BIB034 BIB013 BIB014 BIB035 BIB001 BIB072 BIB044 BIB097 BIB102 BIB049 BIB050 BIB064 BIB098 BIB008 BIB073 BIB074 BIB188  BIB151  BIB204 BIB124 BIB152 BIB178 BIB103 BIB179   BIB153  BIB148      BIB154  BIB030 BIB104 BIB132 BIB075 BIB046 BIB155 BIB189 BIB015 BIB076 BIB156  BIB157 BIB128  BIB129 BIB047 BIB123 BIB077 BIB105 BIB106 BIB004 BIB158 BIB107 BIB159 BIB051 BIB052 BIB133  BIB006 BIB190 BIB108 BIB134 BIB016 BIB160 BIB191 BIB127 BIB017 BIB161   BIB162  BIB135 BIB009 BIB192 BIB147 BIB163  BIB164 BIB180 BIB078 BIB193 BIB043 BIB136  BIB018  BIB125   BIB181 BIB194 BIB195  BIB029 BIB036 BIB010  BIB053 BIB079 BIB165 BIB130  BIB166    BIB062 BIB080 BIB196 BIB081 BIB045     BIB182 BIB205  BIB082 BIB109 BIB019 BIB007 BIB083 BIB037 BIB020 BIB197 BIB063 BIB126 BIB167 BIB110  BIB084 BIB095  BIB168 BIB111 BIB112 BIB137 BIB085  BIB169 BIB198 BIB021 BIB199 BIB170 BIB138 BIB171 BIB139 BIB113 BIB140 BIB086 BIB206 BIB208 BIB005 BIB172 BIB200 BIB141 BIB087 BIB054 BIB022 BIB088 BIB089 BIB042 BIB120 BIB023 BIB055 BIB142 BIB143 BIB201 BIB144 BIB056 BIB024 BIB183 BIB090 BIB173 BIB057 BIB058 BIB114 BIB059 BIB038 BIB174 BIB039 306 Stochastic Demand 14,  BIB025 BIB040 BIB091 BIB145  BIB026 BIB092 BIB115  BIB121 BIB116  85, BIB184 BIB202 BIB096 BIB027  BIB060 BIB067 BIB149 BIB175 BIB002 BIB041  BIB203 BIB122 BIB117 BIB176 BIB028  BIB118 BIB031 BIB094 BIB146 BIB185 BIB186 BIB093 BIB061 BIB032 BIB119 BIB068 305 Arrival 14,  BIB025 BIB040 BIB091 BIB145  BIB026 BIB115  BIB121 BIB116  85, BIB184 BIB202 BIB096 BIB027  BIB060 BIB067 BIB175 BIB002 BIB203 BIB122 BIB176 BIB118 BIB031 BIB185 BIB186 BIB093 BIB061 BIB032 BIB119 301 Capacity 14, BIB026 BIB176  BIB068 The vast majority of the manuscripts ignores all types of uncertainty and uncertainty in capacity in particular. This does not mean that one considers the workload to be constant over periods. In a large number of the included manuscripts, the workload is estimated based on historical data. These estimation methods have received much attention in the literature as well. However, when studying personnel scheduling problems, the stochastic component is often dropped. One way to deal with a variable workload in a deterministic environment is by adding capacity buffers to make personnel rosters more robust. Another frequently applied method is the creation of a set of test instances with different parameters (number of skills per person, demand, capacity) which are used to perform a sensitivity analysis on those parameters (see for example BIB048 and BIB147 ). Researchers hardly ever take into account the unpredictable presence of workers due to illness, arrival delay or the loss of capacity caused by a resource that is out of service BIB028 , when scheduling employees. In Yang et al. BIB068 , the availability of skilled workers is uncertain in the sense that they can decide whether they want to replace a day off by a day of overtime. They model the decision by presuming a 50% chance that a worker says yes (or no). Uncertainty of arrival is mainly of interest in call center systems and is always coupled with uncertainty in demand (or duration). An example of a problem that uses these two sources of uncertainty is given by Campbell  . He develops a two-stage stochastic program for scheduling and allocating cross-trained workers in a multi-department service environment with random demands. The two stages correspond to two different planning periods. In the first stage a worker gets assigned days off over a time horizon of a week or a month. The second stage deals with allocating available workers at the beginning of a day to accommodate realized demands. Yan et al. BIB119 use a stochastic model to incorporate the disturbances of manpower demands that occur in actual operations. They deal with the uncertainty by solving a mixed integer linear program and evaluating its performance with a simulation-based method. In fact, in more than 65% of the manuscripts with a stochastic component, a simulation-based method is used.