Keywords

1 Introduction

Staff scheduling is the process of deploying timetables for a set of workers within an organization so as to satisfy demand for various services, while simultaneously ensuring a distinctive level of employee satisfaction. Moreover, staff scheduling also needs to consider legal, organizational and contractual constraints [1]. In Emergency Medical Services (EMSs), staff scheduling is of paramount importance, since shortages in the number of required personnel directly impact the quality of care that patients receive. Furthermore, employee satisfaction cannot be neglected, as undesirable schedules can lead to increased staff turnover and to poorer on-job-performances.

Personnel scheduling problems arise in a wide variety of settings, such as transportation systems, call centers, and health care systems. Different reviews of the literature have been published and propose different classifications for staff scheduling problems [1,2,3]. In the health care sector, workforce scheduling have been largely dedicated to nurse and physician scheduling. Reviews of models and solution methods for nurse or physician scheduling are also available in the literature [4, 5]. Nevertheless, only few papers deal with staff scheduling in EMSs [6] and are usually dedicated to ambulances by combining the so-called crew scheduling and crew pairing problems. The domain of dispatch centers has not received much attention and is proposed as a potential future research area in [7].

Many solution techniques are applied to solve personnel scheduling problems. A straightforward approach is to model the problem as a standard integer programming (IP) formulation and solve it using a commercial solver [8]. Other researchers use branch-and-price [9], which uses column generation (CG) in each node in the branch-and-bound tree to solve the linear programming (LP) relaxation. Despite the vast improvements in computer hardware and commercial solvers, the high complexity of staff scheduling problems make them difficult to solve to optimality. The easy-to-implement feature of heuristics and the ability to deal with complex constraints or objectives make them well suited to personnel scheduling problems. Genetic algorithms are a popular type of metaheuristic in this field [10]. Recently, MixedIP-based heuristics have been succesfully applied to workforce scheduling [11]. These approaches combine the strengths of both mixed IP and (meta)heuristic approaches. Column generation is also used inside a heuristic framework instead of standard MixedIP approaches [12]. Diving heuristics can be used to obtain integer feasible solutions. Diving algorithms heuristically select branches in the branch-and-price tree using a certain rounding strategy until the first integer solution is found [13].

This paper addresses a staff scheduling problem motivated by the real-life context at Instituto Nacional de Emergência Médica (INEM). The aim is twofold. First, it intends to propose a novel solution approach for the staff scheduling problem at INEM that may be applied to other real-life settings. Second, it aims to enhance INEM productivity and profitability levels, by noticing and proposing solutions for their current scheduling conflicts.

The remainder of this paper is structured as follows. Section 2 introduces the staff scheduling problem and a standard IP model. Next, a column generation-based diving heuristic is proposed in Sect. 3. In Sect. 4, the heuristic is applied to a real-life dataset provided by INEM. Finally, Sect. 5 concludes the paper.

2 Staff Scheduling at an Emergency Medical Service

The EMS is organized in different services and each service is divided in several teams. Each team is responsible for a set of tasks and has a set of staff members with the required skills to perform those tasks. All staff members are assigned to one service and may belong to one or more teams. Preferably workers perform tasks in their own team(s), but it is possible to do tasks from other teams or services to meet the required demand. However, this should be avoided.

This personnel scheduling problem integrates the staffing of the set of services that may share the same workforce. Each service operates 7 days per week and 24 hours per day. Each day of the planning horizon is divided into shifts in which tasks are performed (night, morning and afternoon shifts) and the workload required to each shift (staff level) is known in advance. In this, the problem differs from most problems in the context of staff scheduling at an emergency service, where shift lengths and workload demands are usually not considered as fixed. The reason is that our model schedules only technical personnel for which the demand can be predicted in advance reasonably well.

Legal rules and organizational and contractual issues which need to be satisfied to obtain feasible schedules give rise to the following hard constraints. Legal rules require a minimum resting time between working shifts. Working time regulations set a maximum number of consecutive working days and of consecutive days off for each staff member. Workers must have a minimum number of Sundays off over the planning period. Furthermore, employees are only assigned to tasks for which they have the required skills. For reasons of equity between workers, every staff member needs to work a minimum number of each shift type.

The objective function of the schedules consists of two elements. The primary objective is to ensure functionality of the services. The workload demand should be satisfied as much as possible and is formulated as soft constraints. Thus understaffing and overstaffing are allowed at a penalization cost to be minimized. A second objective for this staff scheduling problem is to increase employee satisfaction and equity among the staff. Workers should have the entire weekend off instead of a single day. The contract hours of each staff member should preferably be met, meaning both overtime and undertime are undesirable. Finally, the number of tasks assigned to staff members belonging to other teams should be minimized.

A standard IP model for this staff scheduling problem is formulated in (1)–(14). The notation is summarized in Table 1. Functionality of the services is modeled by constraints (2)–(8) whereas equity among the staff is formulated by constraints (9)–(12).

$$\begin{aligned} \min &\sum _{d \in \mathrm {D}}\sum _{s \in \mathrm {S}} \sum _{j \in \mathrm {J}} \sum _{t \in \mathrm {T^J_ j }} \left( w^{RE+}_j \, Y^{RE+}_{tds} + w^{RE-}_j \, Y^{RE-}_{tds} \right) + w^{WO} \sum _{p \in \mathrm {P}}\sum _{w \in \mathrm {W}} \left( Y^{WO+}_{pw} + Y^{WO-}_{pw} \right) \nonumber \\&+ \sum _{p \in \mathrm {P}} \left( w^{H+} \, Y^{H+}_{p} + w^{H-} \, Y^{H-}_{p} \right) + \sum _{j \in \mathrm {J}} \sum _{g \in \mathrm {G_j}} w^{G}_j \, Y^{G}_{g} \end{aligned}$$
(1)
$$\begin{aligned} \text {s.t.:} &\sum _{p \in \mathrm {P}^{T}_{t}} x_{ptds} - Y^{RE+}_{tds} + Y^{RE-}_{tds} = R_{tds} \quad \forall t \in \mathrm {T}, d \in \mathrm {D}, s \in \mathrm {S} \end{aligned}$$
(2)
$$\begin{aligned}&\sum _{t \in \mathrm {T^P_ p }} \left( x_{ptd,\mathrm {N}} + x_{ptd,\mathrm {M}} +x_{ptd,\mathrm {A}} \right) \le 1 \quad \forall p \in \mathrm {P}, d \in \mathrm {D} \end{aligned}$$
(3)
$$\begin{aligned}&\sum _{t \in \mathrm {T^P_ p }} \left( x_{ptd,\mathrm {M}} + x_{ptd,\mathrm {A}} +x_{pt,d+1,\mathrm {N}} \right) \le 1 \quad \forall p \in \mathrm {P}, d \in \mathrm {D} \setminus \{|\mathrm {D}|\} \end{aligned}$$
(4)
$$\begin{aligned}&\sum _{t \in \mathrm {T^P_ p }} \left( x_{ptd,\mathrm {A}} + x_{pt,d+1,\mathrm {N}} +x_{pt,d+1,\mathrm {M}} \right) \le 1 \quad \forall p \in \mathrm {P}, d \in \mathrm {D} \setminus \{|\mathrm {D}|\} \end{aligned}$$
(5)
$$\begin{aligned}&\sum _{t \in \mathrm {T^P_ p }}\sum _{r \in \{d, d+1, ..., d+\theta ^{WD}\}}\sum _{s \in \mathrm {S}} x_{ptrs} \le \theta ^{WD} \nonumber \\&\qquad \qquad \forall p \in \mathrm {P}, d \in \mathrm {D} \setminus \{|\mathrm {D}|, |\mathrm {D}|-1, ...,|\mathrm {D}|-\theta ^{WD} + 1 \} \end{aligned}$$
(6)
$$\begin{aligned}&\sum _{t \in \mathrm {T^P_ p }}\sum _{r \in \{d, d+1, ..., d+\theta ^{DO}\}}\sum _{s \in \mathrm {S}} x_{ptrs} \ge 1 \nonumber \\&\qquad \qquad \forall p \in \mathrm {P}, d \in \mathrm {D} \setminus \{|\mathrm {D}|, |\mathrm {D}|-1, ...,|\mathrm {D}|-\theta ^{DO} + 1 \} \end{aligned}$$
(7)
$$\begin{aligned}&\sum _{t \in \mathrm {T^P_ p }}\sum _{d \in \{7 - \kappa , 7 - \kappa +7, ... \}}\sum _{s \in \mathrm {S}} x_{ptds} \le |W| - \theta ^{SO} \quad \forall p \in \mathrm {P} \end{aligned}$$
(8)
$$\begin{aligned}&\sum _{t \in \mathrm {T^P_ p }}\sum _{d \in \mathrm {D}} x_{ptds} \ge \theta ^{ST}_s \quad \forall p \in \mathrm {P}, \forall s \in \mathrm {S} \end{aligned}$$
(9)
$$\begin{aligned}&\sum _{t \in \mathrm {T^P_ p }}\sum _{s \in \mathrm {S}} \left( x_{pt,7(w-1) + 7 - \kappa ,s} - x_{pt,7(w-1)+ 6 - \kappa ,s} \right) - Y^{WO+}_{pw} + Y^{WO-}_{pw} = 0 \nonumber \\&\qquad \qquad \qquad \qquad \qquad \qquad \quad \forall p \in \mathrm {P}, w \in \mathrm {W} \end{aligned}$$
(10)
$$\begin{aligned}&\sum _{t \in \mathrm {T^P_ p }}\sum _{d \in \mathrm {D}}\sum _{s \in \mathrm {S}} L_{t} x_{ptds} - Y^{H+}_{p} + Y^{H-}_{p} = \varTheta _p \quad \forall p \in \mathrm {P} \end{aligned}$$
(11)
$$\begin{aligned}&\sum _{p \in \mathrm {P}^G_g}\sum _{t \in \mathrm {T^P_ p } \setminus \mathrm {T}^G_g}\sum _{d \in \mathrm {D}}\sum _{s \in \mathrm {S}} x_{ptds} - Y^{G}_{g} = 0 \quad \forall g \in \mathrm {G} \end{aligned}$$
(12)
$$\begin{aligned}&Y^{RE+}_{tds}, Y^{RE-}_{tds}, Y^{WO+}_{pw}, Y^{WO-}_{pw}, Y^{H+}_{p}, Y^{H-}_{p}, Y^{G}_{g} \ge 0 \nonumber \\&\qquad \qquad \qquad \qquad \forall p \in P, t \in T, d \in D, s \in S, w \in W, g \in G \end{aligned}$$
(13)
$$\begin{aligned}&x_{ptds} \in \{0,1\} \quad \forall p \in P, t \in \mathrm {T^P_ p }, d \in D, s \in S \end{aligned}$$
(14)

This is a goal programming model where undesired deviations to target values are penalized and minimized as the weighted sum objective function (1). Constraints (2) model the workload demand where understaffing and overstaffing are allowed at a penalty cost minimized in the first term of the objective function. Constraints (3), (4), and (5) force a minimum 2-shifts resting time between consecutive working shifts. Staff members must work a maximum of \(\theta ^{WD}\) consecutive days (6) and have at most \(\theta ^{DO}\) consecutive days off (7). Constraints (8) guarantee at least \(\theta ^{SO}\) Sundays off over the planning period. Constraints (9) set a minimum number of each shift type to be performed by each staff member. The soft requirements contributing for the equity among staff are formulated in (10)–(12), respectively: full weekends off; contract hours; and tasks of other teams performed by members of team g. Deviations to the corresponding target values are penalized, respectively, in the last three terms of the objective function.Regarding the penalization scheme for full weekends off (constraints (10)), the requirements outlined by INEM were followed: a penalty is incurred if a staff member has to work exactly one day in the weekend; and no penalty is incurred if a staff member has to work both weekend days or has both weekend days-off. Thus, as we have a minimization problem, \(Y^{WO+}_{pw}\) equals one if staff member p has to work Sunday but not Saturday, while \(Y^{WO-}_{pw}\) equals one if staff member p has to work Saturday but not Sunday. Constraints (13) represent the domain for the deviation variables, and constraints (14) model the binary domain for the decision variables.

Table 1 Sets, parameters and variables for the IP model
Full size table

3 Column Generation-Based Diving Heuristic

Staff scheduling problems are highly complex and commercial solvers are not able to solve these problems effectively when there are a large number of staff using standard IP models. This paper proposes a hybrid approach combining CG and a diving heuristic.

The column generation is first presented in Sect. 3.1 and the diving heuristic is proposed in Sect. 3.2.

3.1 Column Generation

The standard IP model (1)–(14) is reformulated in terms of work patterns (or columns) for each staff member consisting on the tasks to be perfomed during the planning period. The model can be reformulated in (15)–(19) using the additional notation in Table 2.

$$\begin{aligned} \min &\sum _{p \in \mathrm {P}}\sum _{k \in \mathrm {K}_p} \left( c_{pk} \, z_{pk} \right) + \sum _{d \in \mathrm {D}}\sum _{s \in \mathrm {S}} \sum _{j \in \mathrm {J}} \sum _{t \in \mathrm {T^J_ j }} \left( w^{RE+}_j \, Y^{RE+}_{tds} + w^{RE-}_j \, Y^{RE-}_{tds} \right) \end{aligned}$$
(15)
$$\begin{aligned} \text {s.t.:} &\sum _{p \in \mathrm {P}} \sum _{k \in \mathrm {K}_p} a_{pktds} \, z_{pk} - Y^{RE+}_{tds} + Y^{RE-}_{tds} = R_{tds} \quad \forall t \in \mathrm {T}, d \in \mathrm {D}, s \in \mathrm {S} \end{aligned}$$
(16)
$$\begin{aligned}&\sum _{k \in \mathrm {K}_p} z_{pk} = 1 \quad \forall p \in \mathrm {P} \end{aligned}$$
(17)
$$\begin{aligned}&z_{pk} \in \{0,1\} \quad \forall p \in P, k \in \mathrm {K}_p \end{aligned}$$
(18)
$$\begin{aligned}&Y^{RE+}_{tds}, Y^{RE-}_{tds} \ge 0 \quad \forall t \in T, d \in D, s \in S \end{aligned}$$
(19)

Objective function (15) minimizes the cost of the work patterns assigned to each staff member measured by the deviations to the target values of the soft requirements contributing for the equity among staff, and the penalty associated with understaffing and overstaffing. Constraints (16) model the workload demand. Constraints (17) enforce the assignment of one work pattern to each staff member. The variables’ domain are defined in constraints (18) and (19).

Table 2 New sets, parameters and variables
Full size table

In the CG approach, the LP relaxation of model (15)–(19) (master problem) is initialized with a limited set of work patterns. New promising work patterns (columns) are iteratively added into the master problem. These promising work patterns are generated by the subproblems (pricing problems) solved for each staff member in each iteration of the algorithm. These subproblems consider the constraints related to each staff member individually. The process is repeated until no more promising work patterns (i.e. columns with negative reduced cost) are obtained by solving the subproblems for all the staff. The reduced cost (RC) of a new work pattern k for staff member p is then given by:

$$\begin{aligned} \begin{aligned} \text {RC} = c_{pk} - \sum _{t \in \mathrm {T}}\sum _{d \in \mathrm {D}}\sum _{s \in \mathrm {S}} a_{pktds} \, \lambda _{tds} - \mu _p \end{aligned} \end{aligned}$$
(20)

where \(\lambda _{tds}\) and \(\mu _p\) represent the dual costs associated with constraints (16) and (17), respectively.

The objective function of the pricing problem for each staff member p can then be defined in (21) while the set of constraints consists of Eqs. (3)–(13) with the new defined variables \(a_{tds}\) instead of variables \(x_{ptds}\).

$$\begin{aligned} \begin{aligned} \min \quad \sum _{t \in \mathrm {T}}\sum _{d \in \mathrm {D}}\sum _{s \in \mathrm {S}} \left( -\lambda _{tds} \, a_{tds} \right) + \sum _{w \in \mathrm {W}} \left( w^{WO} \, Y^{WO+}_{w} + w^{WO} \, Y^{WO-}_{w} \right) \\ + w^{H+} \, Y^{H+} + w^{H-} \, Y^{H-} + \sum _{j \in \mathrm {J}} \sum _{g \in \mathrm {G}_j} w^{G}_j \, Y^{G}_{g} \end{aligned} \end{aligned}$$
(21)

The column generation loop can be implemented in two different ways. Strategy E solves a pricing problem for every staff member in each iteration of the column generation. Thus, in each iteration the number of subproblems solved equals the number of available staff and all the work patterns with negative reduced cost are added to the master problem. Strategy P solves only one pricing problem for a given staff member and a work pattern is added to the master problem in each iteration of the column generation if it has a negative reduced cost.

3.2 Diving Heuristic

The solution obtained by the column generation might fail integrality and thus not represent a feasible staff schedule. A diving heuristic allows to traverse a branch-and-price tree in a depth-first manner until finding a feasible solution, thus speeding up the search for a good integer solution. In the diving heuristic, some integer variables are fixed and the linear program is resolved. The fixing and resolving is iterated until either an integral solution is found or the linear program becomes infeasible.

Two strategies are considered for the branching scheme. Strategy L fixes the largest fractional variable to one while strategy T fixes to one all the fractional variables above a threshold value \(\delta \). Each iteration of the heuristic defines the schedule for at least one staff member and the corresponding variables can be removed from the problem. The algorithm ends when a work pattern has been assigned for every staff member.

4 Case Study at INEM

4.1 Case Study

The column generation-based diving heuristic is applied in the context of the staff scheduling problem at INEM. This EMS is organized in two main services: the dispatch center (Centro de Orientação de Doentes Urgentes, CODU), and the Emergency Vehicles (EVs). CODU receives the emergency calls, delivers assistance and instructions, and dispatches the convenient EV. EVs move to the scene, the technicians provide assistance and care on scene, and transport the victims to the hospital if required. The scope of the study is the Lisbon region which includes neighborhood areas coordinated by the Lisbon center (Almada, Amadora, Cascais, Elvas, Estremoz, Ponte de Sôr, Sacavém, Seixal, Setúbal, Tomar and Torres Novas). The workforce at INEM consists of Técnicos de Emergência Pré-Hospitalar (TEPHs). Each TEPH is assigned to one service, although they can also perform tasks at other service. Within a service, TEPHs may belong to more than one team. The assignment of TEPHs to teams depends on the required skills and on the place of residence.

Work rules at INEM state that staff: cannot work more than 6 consecutive days (\(\theta ^{WD} = 6\)); cannot have more than 5 consecutive days-off (\(\theta ^{DO} = 5\)); must have at least one Sunday off every four weeks (\(\theta ^{SO} = 1\)). For equity concerns, it is required that each staff member works at least 2 shifts of each type (\(\theta ^{ST}_s = 2, \forall s \in S\)). Finally, a standard contract specifies a monthly working time of 140 hours (\(\varTheta _p = 140, \forall p \in P\)). All tasks have a duration of 8 h, except for a single type of tasks, emergency motorcylces, which has a duration of 12 hours. Table 3 shows the penalty values used in the objective function (1). The most important objective is to ensure functionality of the services. This means that understaffing is worse than overstaffing. Moreover, the call center (CODU) can still function if there is some understaffing, while the emergency vehicles (EV) are more sensitive to understaffing. Therefore, \(w^{RE-}_\mathrm {CODU} = 100\), \(w^{RE-}_\mathrm {EV} = 1000\), and \(w^{RE+}_\mathrm {CODU} = w^{RE+}_\mathrm {EV} = 10\). The second objective is that every staff member works the amount of hours stipulated in his or her contract (\(w^{H+}\) and \(w^{H-}\)), that staff members receive full weekends off (\(w^{WO}\)), and that tasks are assigned to members of the own team as much as possible (\(w^{G}_\mathrm {CODU}\) and \(w^{G}_\mathrm {EV}\)). Therefore, the values for these weights are smaller. The different weights are measured in different units or dimensions, and thus e.g. \(w^{H+}\) and \(w^{H-}\) are equal to 1, while \(w^{WO}\) is set equal to 10. The INEM dataset includes 289 TEPHs which are organized in 22 teams (5 in CODU and 17 in EVs), and need to be assigned to 61 tasks (10 in CODU and 51 in EVs) within a 4-weeks planning period.

Table 3 Penalty values used in the computational tests
Full size table

4.2 Results

The standard IP model and the column generation-based diving heuristic were coded in C++14 and compiled with Microsoft Visual Studio 2015 using the callable library of ILOG CPLEX 12.6.2. All tests ran on a PC with an Intel Core i5-5200U CPU of 2.20 GHz and 8 GB of RAM under Windows 10.

The following notation is used to refer to the different combination of strategies for the column generation-based diving heuristic: A/B/C-D, where A is the column generation loop strategy (E or P), B is the diving strategy (L or T with threshold \(\delta = 0.6\)), and C-D refer to the stopping criteria used for the column generation (respectively, the number of iterations for the root node, \(\beta ^{\mathrm {root}}\), and for each node on the diving, \(\beta ^{\mathrm {diving}}\)).

The results for the INEM instance are shown in Table 4. In this table, BFS is the objective function value of the best found solution, \(\text {Time}_\mathrm {total}\) is the total computation time (in seconds), \(\mathrm {COLS_{total}}\) is the total number of columns added, ‘Obj. root’ is the objective value of the LP relaxation of the root node, \(\text {Time}_\mathrm {root}\) is the computation time (in seconds) of the root node, \(\mathrm {COLS_{root}}\) is the number of columns added in the root node, and ‘Gap’ is an upper bound on the optimality gap in percent based on the LP relaxation solved by CPLEX. Since the optimal solution is not known, the optimality gap is calculated relative to the objective value LP relaxation, which is never worse than the objective value of the IP problem. Therefore, this gives an upper bound on the optimality gap. Compared to the standard IP approach, the column generation-based diving heuristic with configuration P/T/10-1 finds a solution almost 27 times better in significantly less time (7852 s).

Table 4 Results for INEM
Full size table

From the results of Table 4, three observations can be made. First, branching on the largest fractional variable (L) is much slower than branching on all variables (T) with a value above threshold \(\delta \). The former branching method is not able to find any solution within the 5 h time limit, irrespective of the column generation scheme and the values for \(\beta ^{\mathrm {root}}\) and \(\beta ^{\mathrm {diving}}\). The only exception is E/L/2-2, but this is a very poor solution. Second, the column generation strategy has an important impact on the solution quality. The strategy where a subproblem is solved for every staff member p (E) is much less efficient. The reason for this is the high level of symmetry in the data as most people have the skills to do most of the tasks. As such, given the same dual vector, for almost every staff member the same work pattern is generated. However, in the master only one or a few of those work patterns are useful to meet the demand for a given set of tasks on the different days. On the other hand, in strategy P the dual variables are always updated after the addition of a single work pattern and thus the subproblems for the other staff generate work patterns with different activities. When the column generation phase is terminated prematurely, this leads to the quality of the solutions found by the former column generation strategy being worse as the available work patterns cannot be combined into a good solution. This can also be seen from the objective value obtained in the root node. Third, increasing \(\beta ^{\mathrm {root}}\) is more beneficial for the solution quality than increasing \(\beta ^{\mathrm {diving}}\).

4.3 Comparison with an Implemented Schedule

The best solution (configuration P/T/10-1) is compared with an implemented schedule at INEM. Some indicators, used for comparison, are summarized in Table 5.

Table 5 Comparison between the best solution found and an implemented schedule at INEM
Full size table

In the INEM schedule, TEPHs are working below their contractual hours. On the other hand, in the best solution a TEPH exceeds his/her working hours by only 3.61% on average. Indeed, in our approach failing to meet workload demands carries a higher penalty than overtime, and therefore overtime is being used to satisfy the workload demand as much as possible. More than one Sundays-off is considered on average, which is in line with hard constraints (8). The entire weekend off is modeled as a soft constraint and therefore this value is lower than in the INEM schedule. The INEM real case gives greater importance to this personnel preference, while the solution case schedule seeks primarily to satisfy the workload demand.

Therefore we may conclude that the column generation-based diving heuristic is an improvement over the time-consuming manual scheduling procedure currently in use at INEM.

5 Conclusions

This paper addresses a real-life staff scheduling at an EMS. A column generation-based diving heuristic is proposed, decomposing the problem on the staff members and diving to obtain integer solutions. Two column generation strategies and two branching schemes are implemented. The best configuration is the one that solves a single pricing problem for each staff member in each iteration of the column generation, and rounds to one all the variables above a certain threshold as branching scheme for the diving heuristic. The solution approach is tested on the case study of INEM, the Portuguese EMS, and obtains qood quality solutions in reasonable computation time. The best solution found is compared with an implemented schedule at INEM and shows good practical value and potential to be embedded in an expert system to support staff scheduling decisions. Moreover, this personnel problem integrates the scheduling of staff for several services which is a novelty in the literature of workforce scheduling at EMSs.

The performance of the algorithm in datasets with different dimensions (not described in this paper) shows that the solution approach can easily handle more staff and is robust for the level of problem symmetry (measured in terms of the number of staff members that can perform each task) but performs poorly when the planning period is extended. Together with the slow convergence of the column generation this suggests that the pricing problems are the bottleneck of the algorithm. Consequently, alternative solution approaches can be also explored such as constructive heuristics combined with a variable neighborhood search (VNS) method.