A stochastic programming model for scheduling call centers with global Service Level Agreements

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.     

A shift scheduling model for employees with different seniority levels and an application in healthcare

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.     

Selecting and adapting weekly work schedules with working time accounts: A case of a retail clothing chain

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.     

Profit-maximization generation maintenance scheduling through bi-level programming

This paper addresses the generation maintenance scheduling (GMS) dilemma in a deregulated power system. At first, under a centralized cost minimization framework, a GMS is formulated and set as the benchmark (cost-minimization GMS). Then, the cost-minimization is changed into a profit-maximization problem of generation companies (GENCOs) and the GMS is developed as a bi-level optimization. Karush–Kuhn–Tucker conditions are applied to transform the bi-level into a single-level mixed-integer linear problem and subsequently, Nash equilibrium is obtained as the final solution for the GMS under a deregulated market (profit-maximization GMS). Moreover, to incorporate reliability and economic regulatory constraints, two rescheduling signals (incentive and penalty) are considered as coordination processes among GENCOs and independent system operators. These signals are based on energy-not-supplied and operation cost, and ensure that the result of profit-maximization GMS is in the given reliability and social cost limits, respectively. These limits are obtained from the cost-minimization GMS. Lastly, the model is evaluated on a test system. The results demonstrate applicability and challenges in GMS problems.     

Branch-and-price for staff rostering: An efficient implementation using generic programming and nested column generation

We present a novel generic programming implementation of a column-generation algorithm for the generalized staff rostering problem. The problem is represented as a generalized set partitioning model, which is able to capture commonly occurring problem characteristics given in the literature. Columns of the set partitioning problem are generated dynamically by solving a pricing subproblem, and constraint branching in a branch-and-bound framework is used to enforce integrality. The pricing problem is formulated as a novel three-stage nested shortest path problem with resource constraints that exploits the inherent problem structure. A very efficient implementation of this pricing problem is achieved by using generic programming principles in which careful use of the C++ pre-processor allows the generator to be customized for the target problem at compile-time. As well as decreasing run times, this new approach creates a more flexible modeling framework that is well suited to handling the variety of problems found in staff rostering. Comparison with a more-standard run-time customization approach shows that speedups of around a factor of 20 are achieved using our new approach. The adaption to a new problem is simple and the implementation is automatically adjusted internally according to the new definition. We present results for three practical rostering problems. The approach captures all features of each problem and is able to provide high-quality solutions in less than 15 minutes. In two of the three instances, the optimal solution is found within this time frame.     

Solving a manpower scheduling problem for airline catering using metaheuristics

We study a manpower scheduling problem with job time windows and job-skills compatibility constraints. This problem is motivated by airline catering operations, whereby airline meals and other supplies are delivered to aircrafts on the tarmac just before the flights take-off. Jobs (flights) must be serviced within a given time-window by a team consisting of a driver and loader. Each driver/loader has the skills to service some, but not all, of the airline/aircraft/configuration of the jobs. Given the jobs to be serviced and the roster of workers for each shift, the problem is to form teams and assign teams and start-times for the jobs, so as to service as many flights as possible. Only teams with the appropriate skills can be assigned to a flight. Workload balance among the teams is also a consideration. We present model formulations and investigate a tabu search heuristic and a simulated annealing heuristic approach to solve the problem. Computational experiments show that the tabu search approach outperforms the simulated annealing approach, and is capable of finding good solutions.     

The U.S. Navy explores detailing cost reduction via Data Envelopment Analysis

In this paper we show how a variation of Data Envelopment Analysis, the Generalized Symmetric Weight Assignment Technique, is used to assign sailors to jobs for the U.S. Navy. This method differs from others as the assignment is a multi-objective problem where the importance of each objective, called a metric, is determined by the decision-maker and promoted within the assignment problem. We explore how the method performs as the importance of particular metrics increases. Finally, we show that the proposed method leads to substantial cost savings for the U.S. Navy without degrading the resulting assignments’ performance on other metrics.     

Optimal patient and personnel scheduling policies for care-at-home service facilities

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.     

The value of competitive information in forecasting FMCG retail product sales and the variable selection problem

Sales forecasting at the UPC level is important for retailers to manage inventory. In this paper, we propose more effective methods to forecast retail UPC sales by incorporating competitive information including prices and promotions. The impact of these competitive marketing activities on the sales of the focal product has been extensively documented. However, competitive information has been surprisingly overlooked by previous studies in forecasting UPC sales, probably because of the problem of too many competitive explanatory variables. That is, each FMCG product category typically contains a large number of UPCs and is consequently associated with a large number of competitive explanatory variables. Under such a circumstance, time series models can easily become over-fitted and thus generate poor forecasting results.     

Time-indexed formulations for scheduling chains on a single machine: An application to airborne radars

Airborne radars are widely used to perform a large variety of tasks in an aircraft (searching, tracking, identifying targets, etc.) Such tasks play a crucial role for the aircraft and they are repeated in a “more or less” cyclic fashion. This defines a scheduling problem that impacts a lot on the quality of the radar output and on the overall safety of the aircraft.     

Behavioural modelling of career progression in the European Commission

Though manpower planning models have been part of OR for many years, and simulation has always been acknowledged as a potential approach, there are few reported applications of its use. In this case-based study we report on a micro-simulation model that exploits the structure of the European Commission’s appraisal and promotion rules, and includes regression-based sampling schemes which allow for non-Normal error terms to represent behavioural factors that led to the need for a new system. With a suitably parsimonious formulation the 20,000 person model runs very effectively, and the transparency associated with simulation proves an important factor in the successful use of the model as the basis for designing a promotion box system that was implemented across the Commission in 2009. The simulation modelling incorporates many Markov-type elements, and we reflect on important lessons learned from this combined use of micro-simulation and Markov-based approaches to manpower modelling.     

A branch-and-price approach for integrating nurse and surgery scheduling

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.     

Workforce routing and scheduling for electricity network maintenance with downtime minimization

We investigate a combined routing and scheduling problem for the maintenance of electricity networks. In electricity networks power lines must be regularly maintained to ensure a high quality of service. For safety reasons a power line must be physically disconnected from the network before maintenance work can be performed. After completing maintenance work the power line must be reconnected. Each maintenance job therefore consists of multiple tasks which must be performed at different locations in the network. The goal is to assign each task to a worker and to determine a schedule such that the downtimes of power lines and the travel effort of workers are minimized. For solving this problem, we combine a Large Neighborhood Search meta-heuristic with mathematical programming techniques. The method is evaluated on a large set of test instances which are derived from network data of a German electricity provider.     

Generating,scheduling and rostering of shift crew-duties: Applications at the Hong Kong International Airport

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.     

Approximate solution of a resource-constrained scheduling problem

This paper is devoted to the approximate solution of a strongly NP-hard resource-constrained scheduling problem which arises in relation to the operability of certain high availability real time distributed systems. We present an algorithm based on the simulated annealing metaheuristic and, building on previous research on exact solution methods, extensive computational results demonstrating its practical ability to produce acceptable solutions, in a precisely defined sense. Additionally, our experiments are in remarkable agreement with certain theoretical properties of our simulated annealing scheme. The paper concludes with a short discussion on further research. This research was supported in part by Association Nationale de la Recherche Technique grant CIFRE-121/2004.     

An exact branch-and-price algorithm for scheduling rescue units during disaster response

In disaster operations management, a challenging task for rescue organizations occurs when they have to assign and schedule their rescue units to emerging incidents under time pressure in order to reduce the overall resulting harm. Of particular importance in practical scenarios is the need to consider collaboration of rescue units. This task has hardly been addressed in the literature. We contribute to both modeling and solving this problem by (1) conceptualizing the situation as a type of scheduling problem, (2) modeling it as a binary linear minimization problem, (3) suggesting a branch-and-price algorithm, which can serve as both an exact and heuristic solution procedure, and (4) conducting computational experiments – including a sensitivity analysis of the effects of exogenous model parameters on execution times and objective value improvements over a heuristic suggested in the literature – for different practical disaster scenarios. The results of our computational experiments show that most problem instances of practically feasible size can be solved to optimality within ten minutes. Furthermore, even when our algorithm is terminated once the first feasible solution has been found, this solution is in almost all cases competitive to the optimal solution and substantially better than the solution obtained by the best known algorithm from the literature. This performance of our branch-and-price algorithm enables rescue organizations to apply our procedure in practice, even when the time for decision making is limited to a few minutes. By addressing a very general type of scheduling problem, our approach applies to various scheduling situations.     

Decomposition approaches in permutation scheduling problems with application to the M-machine flow shop scheduling problems

In this article, we consider three decomposition techniques for permutation scheduling problems. We introduce a general iterative decomposition algorithm for permutation scheduling problems and apply it to the permutation flow shop scheduling problem. We also develop bounds needed for this iterative decomposition approach and compare its computational requirements to that of the traditional branch and bound algorithms. Two heuristic algorithms based on the iterative decomposition approach are also developed. extensive numerical study indicates that the heuristic algorithms are practical alternatives to very costly exact algorithms for large flow shop scheduling problems.     

The roster quality staffing problem – A methodology for improving the roster quality by modifying the personnel structure

Quantitative decision support on personnel planning is often restricted to either rostering or staffing. There exist some approaches in which aspects at the staffing level and the rostering level are treated in a sequential way. Obviously, such practice risks producing suboptimal solutions at both decision levels. These arguments justify an integrated approach towards improving the overall quality of personnel planning. This contribution constitutes (1) the introduction of the roster quality staffing problem and (2) a three-step methodology that enables assessing the appropriateness of a personnel structure for achieving high quality rosters, while relying on an existing rostering algorithm. Based on the rostering assessment result, specific modifications to the personnel structure can be suggested at the staffing level. The approach is demonstrated by means of two different hospital cases, which have it that they are subject to complex rostering constraints. Experimental results show that the three-step methodology indeed points out alternative personnel structures that better comply with the rostering requirements. The roster analysis approach and the corresponding staffing recommendations integrate personnel planning needs at operational and tactical levels.