A two-stage heuristic for multi-activity and task assignment to work shifts

The multi-activity assignment problem consists of assigning interruptible activities to given work shifts so as to match as much as possible for each activity a demand curve in function of time. In this paper we consider an extension to this problem, called the multi-activity and task assignment problem, that additionally considers the assignment of uninterruptible pieces of work, called tasks. These possess properties such as worker qualifications, time windows for completion, fixed lengths and precedence relationships. We propose a mixed-integer programming formulation and a two-stage method to solve this problem. The first stage consists of an approximation mixed-integer programming model to assign tasks approximately taking into account the activities and the second involves a column generation heuristic for assigning activities and reassigning tasks at the same time. We suggest four different strategies for reassigning tasks. We conducted extensive computational tests on randomly generated instances in order to validate our method and to compare the various strategies. One strategy proved universally best when compared to the other three policies.     

A two-stage heuristic for multi-activity and task assignment to work shifts

The multi-activity assignment problem consists of assigning interruptible activities to given work shifts so as to match as much as possible for each activity a demand curve in function of time. In this paper we consider an extension to this problem, called the multi-activity and task assignment problem, that additionally considers the assignment of uninterruptible pieces of work, called tasks. These possess properties such as worker qualifications, time windows for completion, fixed lengths and precedence relationships. We propose a mixed-integer programming formulation and a two-stage method to solve this problem. The first stage consists of an approximation mixed-integer programming model to assign tasks approximately taking into account the activities and the second involves a column generation heuristic for assigning activities and reassigning tasks at the same time. We suggest four different strategies for reassigning tasks. We conducted extensive computational tests on randomly generated instances in order to validate our method and to compare the various strategies. One strategy proved universally best when compared to the other three policies.     

A two-phase mathematical-programming heuristic for flexible assignment of activities and tasks to work shifts

In the service industry, workers perform work shifts and are assigned to interruptible activities and uninterruptible tasks during their shifts. The work shifts of regular employees are often established several weeks in advance of the operations when the activity and task demands are still uncertain. Just a few days before the operations when these demands are unveiled with more certainty, the planned schedules can be slightly modified and on-call temporary employees can be scheduled to satisfy the demands as best as possible. As acceptable modifications, extending the planned shifts and moving workers’ meal breaks are considered. In this paper, we are interested in the scheduling problem encountered in this second step, which also involves assigning activities and tasks to the scheduled work shifts. To produce good-quality solutions in fast computational times for large-sized instances, we develop a two-phase heuristic. In the first phase, an approximate mixed-integer programming model is used to suggest temporary shifts and extensions to regular shifts and to schedule and assign tasks. In the second phase, a column-generation heuristic embedded in a rolling horizon procedure determines the final shifts and assigns activities to them. Computational results obtained on randomly generated instances are reported to evaluate the validity of the proposed solution method.     

A mixed integer programming approach to multi-skilled workforce scheduling

The potential benefits of using human resources efficiently in the service sector constitute an incentive for decision makers in this industry to intelligently manage the work shifts of their employees, especially those dealing directly with customers. In the long term, they should attempt to find the right balance between employing as few labor resources as possible and keeping a high level of service. In the short run (e.g., 1 week), however, contracted staff levels cannot be adjusted, and management efforts thus focus on the efficient assignment of shifts and activities to each employee. This article proposes a mixed integer program model that solves the short-term multi-skilled workforce tour scheduling problem, enabling decision makers to simultaneously design workers’ shifts and days off, assign activities to shifts and assign those to employees so as to maximize and balance coverage of a firm’s demand for on-duty staff across multiple activities. Our model is simple enough to be solved with a commercial MIP solver calibrated by default without recurring to complex methodologies, such as extended reformulations and exact and/or heuristic column generation subroutines. A wide computational testing over 1000 randomly generated instances suggests that the model’s solution times are compatible with daily use and that multi-skilling is a significant source of labor flexibility to improve coverage of labor requirements, in particular when such requirements are negatively correlated and part-time workers are a scarce resource.     

Reducing understaffing and shift work with Temporal Profile Optimization (TPO)

The ergonomic quality of shift schedules can be improved by reducing time periods with understaffing (resulting in work-pressure, poor quality, etc.) and evening, night and/or weekend work.Improving the quality of forecasts regarding future workforce requirements as well as the optimization of work processes by moving as much work as possible to more suitable time zones are two approaches to this.We introduce and propose Temporal Profile Optimization (TPO) as a systematic approach to question the demand as well as its translation to workforce planning. Temporal profiles describe the number of employees needed over time (e.g. for different days of the week, times of day, for different calendar days) as well as the shift-times and staffing levels planned to meet this workforce demand.With Temporal Profile Forecasts we introduce a forecasting method that is based on time-stamped historical data and methodologically supplements traditional time series models like SARIMA in many ways. With Temporal Profile Reengineering we use systematic and often participatory methods from business process reengineering to identify moveable work and streamline the load lines by (re-)distributing movable work such that shifts and schedules are improved.The approach is illustrated along two business cases. Using TP-Forecasts for air traffic controllers increased forecasting accuracy whereby a different shift design was possible resulting in 3–4% less shift work. In a warehouse of an Austrian freight carrier a TP-Forecast together with TP-Reengineering helped to rearrange work processes such that the resulting workforce requirements curve had a more even form. This allowed for shorter shifts than before (thereby decreasing overtime).Experiences made so far stress the potential of Temporal Profile Optimization.     

A constraint-based approach for the shift design personnel task scheduling problem with equity

This paper presents an industrial problem which arises in a company specialized in drug evaluation and pharmacology research. The aim is to build employee timetables covering the demand given by a set of fixed tasks. The optimality criterion concerns the equity of the workload sharing. A solution to this problem is the assignment of all tasks whose resulting working shifts respect tasks requirements as well as legal and organizational constraints. Scheduling problems usually consider a fixed set of shifts which have to be assigned to a given number of employees whereas in our problem shifts are not fixed and are deduced from the task assignment. In the following, we refer to this problem as the shift-design personnel task scheduling problem with an equity criterion (SDPTSP-E), in reference to the shift minimization personnel task scheduling problem (SMPTSP). Even if the SDPTSP-E is related to several problems, none of them allow to grasp its full complexity. Consequently, we propose a dedicated method based on constraint programming. Several branching and exploration strategies are proposed and tested.     

Rostering in a rail passenger carrier

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.     

Achieving full connectivity of sites in the multiperiod reserve network design problem

The conservation reserve design problem is a challenge to solve because of the spatial and temporal nature of the problem, uncertainties in the decision process, and the possibility of alternative conservation actions for any given land parcel. Conservation agencies tasked with reserve design may benefit from a dynamic decision system that provides tactical guidance for short-term decision opportunities while maintaining focus on a long-term objective of assembling the best set of protected areas possible. To plan cost-effective conservation over time under time-varying action costs and budget, we propose a multi-period mixed integer programming model for the budget-constrained selection of fully connected sites. The objective is to maximize a summed conservation value over all network parcels at the end of the planning horizon. The originality of this work is in achieving full spatial connectivity of the selected sites during the schedule of conservation actions.     

Improving production planning by utilizing stochastic programming

The effects of fluctuating demand on production and inventory levels are important in manufacturing resource planning. Thus, the focus of this presentation is on aggregate production planning of manufacturing resources in order to satisfy stochastic demand for a family of products to minimize total costs that include production and inventory holding costs over a rolling horizon.

If it is assumed that, in a commercial setting, the demands are fixed, then the production plans generated by a mathematical programming procedure are not responsive to the actual fluctuations of stochastic demand in each time period.

The situation discussed here considers the case where demands are normally distributed with means and variances that are sequentially revised as new observations of demand are received over time. This assumption allows the probabilistic constraint to be converted to an equivalent linearly-constrained deterministic model. Extensions to the normality assumption are discussed. Also other ideas such as optimal control theory, learning and adaptive signal processing extensions are discussed as well.     

A multi-objective programming model for scheduling emergency medicine residents

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.     

Supply chain planning for hurricane response with wind speed information updates

This paper introduces a stochastic inventory control problem that is relevant to proactive disaster recovery planning as it relates to preparing for potential hurricane activity. In particular, we consider a manufacturing or retail organization who experiences demand surge for items such as flashlights, batteries, and gas-powered generators, where the magnitude of demand surge is influenced by various characteristics of an ensuing storm. The planning horizon begins during the initial stages of storm development, when a particular tropical depression or disturbance is first observed, and ends when the storm dissipates. Since hurricane characteristics can be predicted with more accuracy during the later stages of the planning horizon relative to the earlier stages, the inventory control problem is formulated as an optimal stopping problem with Bayesian updates, where the updates are based on hurricane predictions. A dynamic programming algorithm is described to solve the problem, and several examples involving real hurricane wind speed data are presented to illustrate the methodology.     

A multi-objective customer orders assignment and resource leveling in make-to-order manufacturing

This paper presents integer programming formulations and compares two approaches – weighting and lexicographic – to the multi‐objective, long‐term production scheduling in make‐to‐order manufacturing, where both maximization of customer service level and best utilization of production resources are integrated in the objective function. The problem objective is to assign customer orders for various product types and with various due dates to planning periods and to select machines for assignment in every period to complete all the orders with minimum numbers of tardy and early orders and with a leveled machine assignment over a planning horizon. The two approaches are applied to optimize long‐term production schedules in a flexible flowshop with parallel machines. Numerical examples modeled after a real‐world flexible assembly line in the electronics industry are provided and some computational results are reported.     

Optimizing Blood Assignment in a Donation–Transfusion System

A multi-product, multi-period, multi-objective linear programming model has been built as a contribution to good management of a blood donation–transfusion system in order to determine the best assignment of blood resources to demand, which minimizes the quantity of blood imported from outside the system and stabilizes the quantities assigned daily. The model has been applied to the Italian Red Cross (CRI) blood donation–transfusion system in Rome and to each hospital belonging to such a system, producing interesting results.     

Rolling Horizon Path Planning of an Autonomous System of UAVs for Persistent Cooperative Service: MILP Formulation and Efficient Heuristics

A networked system consisting of unmanned aerial vehicles (UAVs), automated logistic service stations (LSSs), customer interface software, system orchestration algorithms and UAV control software can be exploited to provide persistent service to its customers. With efficient algorithms for UAV task planning, the UAVs can autonomously serve the customers in real time. Nearly uninterrupted customer service may be accomplished via the cooperative hand-off of customer tasks from weary UAVs to ones that have recently been replenished at an LSS. With the goal of enabling the autonomy of the task planning tasks, we develop a mixed integer linear programming (MILP) formulation for the problem of providing simultaneous. UAV escort service to multiple customers across a field of operations with multiple sharable LSSs. This MILP model provides a formal representation of our problem and enables use in a rolling horizon planner via allowance of arbitrary UAV initial locations and consumable reservoir status (e.g., battery level). As such, it enables automation of the orchestration of system activities. To address computational complexity, we develop efficient heuristics to rapidly derive near optimal solutions. A receding horizon task assignment (RHTA) heuristic and sequential task assignment heuristic (STAH) are developed. STAH exploits properties observed in optimal solutions obtained for small problems via CPLEX. Numerical studies suggest that RHTA and STAH are 45 and 2100 times faster than solving the MILP via CPLEX, respectively. Both heuristics perform well relative to the optimal solution obtained via CPLEX. An example demonstrating the use of the approach for rolling horizon planning is provided.     

Designing cellular manufacturing systems under dynamic and uncertain conditions

The paper proposes a fuzzy programming based approach to design a cellular manufacturing system under dynamic and uncertain conditions. The dynamic condition indicates a multi-period planning horizon, in which the product mix and demand in each period can be different. As a result, the best cells designed for one period may not be efficient cells for subsequent periods and some of reconfigurations are required. Uncertain condition implicates to the imprecise nature of the part demand and also the availability of the manufacturing facilities in each period planning. An extended mixed-integer programming model of dynamic cellular manufacturing system, in which some of the coefficients in objective function and constraints are fuzzy quantities, is solved by a developed fuzzy programming based approach. The objective is to determine the optimal cell configuration in each period with maximum satisfaction degree of the fuzzy objective and constraint. To illustrate the behavior of the proposed model and verify the performance of the developed approach, a number of numerical examples are solved and the associated computational results are reported.     

Sequential optimization and revision of production plans over time

Production plans generated by linear programming technique over the planning horizon are not responsive to the actual fluctuations of stochastic demand at each time period. The deterioation in the total-cost performance is due to absence of predicting-error feedback for sequential revision of the production targets. In this paper, a simple sequential optimization procedure using minimum mean-square-error recursive forecast is introduced. The total cost performance of this proposed technique is compared with the chance-constrained linear programming method for sequential production plan generation.     

Staff assignment with lexicographically ordered acceptance levels

Staff assignment is a compelling exercise that affects most companies and organizations in the service industries. Here, we introduce a new real-world staff assignment problem that was reported to us by a Swiss provider of commercial employee scheduling software. The problem consists of assigning employees to work shifts subject to a large variety of critical and noncritical requests, including employees’ personal preferences. Each request has a target value, and deviations from the target value are associated with integer acceptance levels. These acceptance levels reflect the relative severity of possible deviations, e.g., for the request of an employee to have at least two weekends off, having one weekend off is preferable to having no weekend off and thus receives a higher acceptance level. The objective is to minimize the total number of deviations in lexicographical order of the acceptance levels. Staff assignment approaches from the literature are not applicable to this problem. We provide a binary linear programming formulation and propose a matheuristic for large-scale instances. The matheuristic employs effective strategies to determine the subproblems and focuses on finding good feasible solutions to the subproblems rather than proving their optimality. Our computational analysis based on real-world data shows that the matheuristic scales well and outperforms commercial employee scheduling software.     

Close-optimal production and procurement policy for a X-network of added value using lexicographic linear goal programming

One of the main challenges of operation managers of firms is to setup feasible production and procurement plans. This is also the case of more complex structures such as supply chains. In almost all firms, specific tools like ERPs are used to support managers in their decision-making tasks. These tools manipulate huge amount of data such as the order backlog, or technical, marketing, suppliers and customers data. They work often based on the MRP principles and suggest production and procurement plans after a sequential procedure which begins by the material requirements calculation followed by the load balancing process. Very often, the load balancing is under the control of managers who try to take account of implicit constraints that cannot be modelled easily. This is a difficult and often risky task because the managers do not know what the best solution of the planning and procurement problem is. In other words, there is a lack of a kind of “the best feasible production and procurement target”. The main idea of this article is to suggest a complementary method for planning based on a specific mathematical programming approach which provides plans considering simultaneously all material and capacity constraints over the entire planning horizon. These plans can be considered as that necessary closed optimal production and procurement target for a company or a supply chain which uses an MRP-based planning tool. The lexicographic linear goal programming provides a suitable multi-criteria modelling paradigm for the production and procurement planning problems, especially for the supply chains. The study is focused on a common supply chain structure formed by several suppliers on one side and several customers on the other, connected together by a business-to-business relationship over a rolling horizon. The structure is modelled thanks to the Petri Nets supporting the definition of the global problem model. The model is then applied to a study case extracting from the car assembly industry.     

A linear programming formulation with integer solutions for solving an equipment replacement problem with multiple assets: the concave demand case

A linear programming formulation is presented for the deterministic equipment replacement problem in which multiple assets are required each period and a number of assets are available for replacement. Under common cost assumptions, the linear programming solutions are shown to be integer for certain demand constraints- This paper considers the case of concave demand over a finite horizon. The integer solutions allow for implementable decisions and the formulation allows for the solution of large replacement problems, such as vehicles in a fleet, without the computational effort of branch-and-bound procedures. Numerical solutions are provided for illustration of the formulation and its efficiency in solving large replacement problems.     

A branch-and-price algorithm for the multi-activity multi-task shift scheduling problem

The multi-activity multi-task shift scheduling problem requires the assignment of interruptible activities and uninterruptible tasks to a set of employees in order to satisfy a demand function. In this paper, we consider the personalized variant of the problem where the employees have different qualifications, preferences, and availabilities. We present a branch-and-price algorithm to solve this problem. The pricing subproblems in column generation are formulated with context-free grammars that are able to model complex rules in the construction of feasible shifts for an employee. We present results for a large set of instances inspired by real cases and show that this approach is sufficiently flexible to handle different classes of problems.