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 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.     

Dynamic multi-appointment patient scheduling for radiation therapy

Seeking to reduce the potential impact of delays on radiation therapy cancer patients such as psychological distress, deterioration in quality of life and decreased cancer control and survival, and motivated by inefficiencies in the use of expensive resources, we undertook a study of scheduling practices at the British Columbia Cancer Agency (BCCA). As a result, we formulated and solved a discounted infinite-horizon Markov decision process for scheduling cancer treatments in radiation therapy units. The main purpose of this model is to identify good policies for allocating available treatment capacity to incoming demand, while reducing wait times in a cost-effective manner. We use an affine architecture to approximate the value function in our formulation and solve an equivalent linear programming model through column generation to obtain an approximate optimal policy for this problem. The benefits from the proposed method are evaluated by simulating its performance for a practical example based on data provided by the BCCA.     

A stochastic appointment scheduling system on multiple resources with dynamic call-in sequence and patient no-shows for an outpatient clinic

This research focuses on the stochastic assignment system motivated by outpatient clinics, especially the physical therapy in rehabilitation service. The aim of this research is to develop a stochastic overbooking model to enhance the service quality as well as to increase the utilization of multiple resources, like therapy equipment in a physical therapy room, with the consideration of patients’ call-in sequence. The schedule for a single-service period includes a fixed number of blocks of equal length. When patients call, they are assigned to an appointment time for that block, and an existing appointment is not allowed to be changed. In each visit, a patient might require more than one resource and a probability of no-show. Two estimation methods were proposed for the expected waiting and overtime cost with multiple resources: Convolution Estimation Method and Joint Cumulative Estimation Method for the upper and lower bound value; respectively. A numerical example based on a physical therapy room was used to show that this stochastic model was able to schedule patients for better profitability compared with traditional appointment systems based on four prioritization rules. The workload in each appointment slot was more balanced albeit more patients were assigned to the first slot to fill up the empty room.     

A flexible MILP model for multiple-shift workforce planning under annualized hours

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.     

Combining discrete-event simulation and system dynamics in a healthcare setting: A composite model for Chlamydia infection

This paper presents a composite model in which two simulation approaches, discrete-event simulation (DES) and system dynamics (SD), are used together to address a major healthcare problem, the sexually transmitted infection Chlamydia. The paper continues an on-going discussion in the literature about the potential benefits of linking DES and SD. Previous researchers have argued that DES and SD are complementary approaches and many real-world problems would benefit from combining both methods. In this paper, a DES model of the hospital outpatient clinic which treats Chlamydia patients is combined with an SD model of the infection process in the community. These two models were developed in commercial software and linked in an automated fashion via an Excel interface. To our knowledge this is the first time such a composite model has been used in a healthcare setting. The model shows how the prevalence of Chlamydia at a community level affects (and is affected by) operational level decisions made in the hospital outpatient department. We discuss the additional benefits provided by the composite model over and above the benefits gained from the two individual models.     

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.     

A multi-objective multi-period stochastic programming model for public debt management

While raising debt on behalf of the government, public debt managers need to consider several possibly conflicting objectives and have to find an appropriate combination for government debt taking into account the uncertainty with regard to the future state of the economy. In this paper, we explicitly consider the underlying uncertainties with a complex multi-period stochastic programming model that captures the trade-offs between the objectives. The model is designed to aid the decision makers in formulating the debt issuance strategy. We apply an interactive procedure that guides the issuer to identify good strategies and demonstrate this approach for the public debt management problem of Turkey.     

A multi-criteria model for auditing a Predictive Maintenance Programme

Auditing tools can play a key role in the continuous improvement of maintenance policies, in particular to enhance predictive maintenance (PM). This paper proposes a multi-criteria model for auditing a Predictive Maintenance Programme (PMP) developed and implemented in the General Hospital of Ciudad Real (GHCR) in Spain. The model has a two-level structure, with top level auditing areas specified by second level auditing criteria on which the performance of the PMP should be appraised. This structure resulted from the analysis and discussion of an internal questionnaire to the management, technical and consulting staff of GHCR. This also guided the association of a performance scale with each criterion, describing several reference levels of accomplishment. Using the MACBETH (Measuring Attractiveness by a Categorical Based Evaluation Technique) approach, a hierarchical additive value model was constructed, with criteria weights and value scales derived from staff judgments of comparison of different reference levels and profiles of performance. This model enables managers to measure the performance of the PMP and its added value for the hospital, not only against each audit criterion individually, but also on each area and in overall terms. Integrated in a management “tableau de bord”, the model outputs permit the identification of PMP deficiencies requiring urgent intervention and corrective measures for its continuous improvement.     

A cutting plane method for solving harvest scheduling models with area restrictions

We describe a cutting plane algorithm for an integer programming problem that arises in forest harvest scheduling. Spatial harvest scheduling models optimize the binary decisions of cutting or not cutting forest management units in different time period subject to logistical, economic and environmental restrictions. One of the most common constraints requires that the contiguous size of harvest openings (i.e., clear-cuts) cannot exceed an area threshold in any given time period or over a set of periods called green-up. These so-called adjacency or green-up constraints make the harvest scheduling problem combinatorial in nature and very hard to solve. Our proposed cutting plane algorithm starts with a model without area restrictions and adds constraints only if a violation occurs during optimization. Since violations are less likely if the threshold area is large, the number of constraints is kept to a minimum. The utility of the approach is illustrated by an application, where the landowner needs to assess the cost of forest certification that involves clear-cut size restrictions stricter than what is required by law. We run empirical tests and find that the new method performs best when existing models fail: when the number of units is high or the allowable clear-cut size is large relative to average unit size. Since this scenario is the norm rather than the exception in forestry, we suggest that timber industries would greatly benefit from the method. In conclusion, we describe a series of potential applications beyond forestry.     

A detailed workforce planning model including non-linear dependence of capacity on the size of the staff and cash management

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.     

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.     

A multicriteria accreditation system for information technology skills and qualifications

Employees must acquire new competences and qualifications throughout their lives, in order to be able to deal with the multiple changes in the labour market. The specific knowledge and competences, acquired either formally or non-formally, must be recognized so that they can be transferred and utilized. The existing titles of studies and accreditation mechanisms do not generally cover this need. This paper aims to propose an integrated approach for the evaluation of information technology knowledge and skills, regardless of where and how they have been acquired, so as to apply a continuous education and training policy. The proposed multicriteria methodology for the evaluation of qualifications and skills concerns candidates wishing to be accredited in an information technology specialization or profession. The methodology refers to the evaluation of the professional experience, studies and vocational training of the candidates for accreditation. It contains the analysis and modelling of the qualitative criteria as well as the implementation of multicriteria aggregation–disaggregation techniques attributing value to each criterion. Then, the candidates are classified in categories of professionals using the Electre Tri method, accepting as input data the multicriteria assessments on each criterion. The proposed evaluation approach has been adapted to the Greek educational system and is applied to a specific example of candidate.     

Mid-term and short-term planning support for home health care services

In this paper we are looking at routing and scheduling problems arising in the context of home health care services. Many small companies are working in this sector in Germany and planning is still done manually, resulting in long planning times and relatively inflexible solutions.     

Disaster preparedness in humanitarian logistics: A collaborative approach for resource management in floods

The logistical deployment of resources to provide relief to disaster victims and the appropriate planning of these activities are critical to reduce the suffering caused. Disaster management attracts many organisations working alongside each other and sharing resources to cope with an emergency. Consequently, successful operations rely heavily on the collaboration of different organisations. Despite this, there is little research considering the appropriate management of resources from multiple organisations, and none optimising the number of actors required to avoid shortages or convergence.This research introduces a disaster preparedness system based on a combination of multi-objective optimisation and geographical information systems to aid multi-organisational decision-making. A cartographic model is used to avoid the selection of floodable facilities, informing a bi-objective optimisation model used to determine the location of emergency facilities, stock prepositioning, resource allocation and relief distribution, along with the number of actors required to perform these activities.The real conditions of the flood of 2013 in Acapulco, Mexico, provided evidence of the inability of any single organisation to cope with the situation independently. Moreover, data collected showed the unavailability of enough resources to manage a disaster of that magnitude at the time. The results highlighted that the number of government organisations deployed to handle the situation was excessive, leading to high cost without achieving the best possible level of satisfaction. The system proposed showed the potential to achieve better performance in terms of cost and level of service than the approach currently employed by the authorities.     

A mixed integer programming model for advanced planning and scheduling (APS)

This paper presents a mixed integer programming (MIP) model which succeeds in a system integration of the production planning and shop floor scheduling problems. The proposed advanced planning and scheduling (APS) model explicitly considers capacity constraints, operation sequences, lead times and due dates in a multi-order environment. The objective of the model is to seek the minimum cost of both production idle time and tardiness or earliness penalty of an order. The output of the model is operation schedules with order starting time and finish time. Numerical result shows that the suggested APS model can favorably produce optimal schedules.     

A branch and bound based heuristic for makespan minimization of washing operations in hospital sterilization services

In this paper, we address the problem of parallel batching of jobs on identical machines to minimize makespan. The problem is motivated from the washing step of hospital sterilization services where jobs have different sizes, different release dates and equal processing times. Machines can process more than one job at the same time as long as the total size of jobs in a batch does not exceed the machine capacity. We present a branch and bound based heuristic method and compare it to a linear model and two other heuristics from the literature. Computational experiments show that our method can find high quality solutions within short computation time.     

A note on “A mixed integer programming model for advanced planning and scheduling (APS)”

In a recent paper, Chen and Ji [Chen, K., Ji, P., 2007. A mixed integer programming model for advanced planning and scheduling (APS). European Journal of Operational Research 181, 515–522] develop a mixed integer programming model for advanced planning and scheduling problem that considers capacity constraints and precedence relations between the operations. The orders require processing of several operations on eligible machines. The model presented in the above paper works for the case where each operation can be processed on only one machine. However, machine eligibility means that only a subset of machines are capable of processing a job and this subset may include more than one machine. We provide a general model for advanced planning and scheduling problems with machine eligibility. Our model can be used for problems where there are alternative machines that an operation can be assigned to.     

Dynamic job assignment: A column generation approach with an application to surgery allocation

We consider the assignment of jobs to heterogeneous agents in a dynamic system with a rolling time horizon. An example is a hospital operating theatre where the jobs are surgeries and the agents are the surgeons. The paper is presented in the context of surgery allocation and the system is characterized as follows: Patients are grouped into categories and they arrive continually following a stochastic process. Patients in each group have specific time limits within which they need treatment and if it cannot be accommodated then the patients are outsourced. The service level is the percentage of patients in each group treated within the time limit. Surgery durations are stochastic and depend on the surgeon conducting the surgeries. Each surgeon has limited time available and expected overtime is penalized by a non-decreasing convex function. We develop a column generation approach for the assignment of already arrived patients and tentative future patients to surgeons on specific days. It balances the conflicting objectives of including as many arrived patients as possible within their time limits, maximizing the service level of future patients, and minimizing the expected overtime of surgeons. A computational study is conducted with the model embedded in a rolling time horizon frame. The study indicates that the assignment of patients based on our model increases system performance in terms of service level and reduced overtime compared to a First-Come-First-Served (FCFS) policy when the arrival rates of patients are medium to high compared to the capacity of the system.