A resource type analysis of the integrated project scheduling and personnel staffing problem

Abstract

In the integrated project scheduling and personnel staffing problem the project activities are scheduled and simultaneously a staffing plan is composed to carry out a single project. In this way, the project schedule that leads to the staffing plan with minimum cost is determined. In this paper, we evaluate different scheduling policies and practices for different personnel resource types. We examine the impact on the staffing cost when the personnel resources are scheduled in a cyclic versus a non-cyclic manner for different (days on, days off)-patterns. Furthermore, the impact of introducing more flexible resource types, such as overtime and temporary help, is explored in relationship with the activity resource demand variability. Computational results show that non-cyclic scheduling leads to a considerable lower staffing cost under all circumstances compared to cyclic scheduling. However, despite the tractability of the resource requirements, flexible temporary resources are essential on top of the regular personnel resources to respond to the variability in demand. The addition of overtime on a strategic staffing level only marginally decreases the personnel cost.

Appendix: Mathematical problem formulation for the IPS&PSP

1.1 Decomposed problem formulation

In this appendix, we provide a mathematical problem formulation for the IPS&PSP. The formulation is based on the Dantzig-Wolfe decomposition. This formulation embodies an integer master program and a subproblem, for which the symbols and mathematical formulations are given below.

List of symbols

Sets

N :

The set of activities in the project network (index $i = 0,\ldots ,n$ with activity 0 (n) representing the dummy start (end) activity)

A :

The set of pairs (i, j) representing the direct precedence relationships in the project network

J :

The set of feasible personnel schedules (index j)

P :

The set of cyclic work patterns according to a specific (days on, days off) -pattern (index p)

T :

The time horizon (index t)

M :

The set of unit time periods over which the personnel schedule is evaluated

$T_m$ :

The time horizon of the unit time period m

R :

The set of renewable personnel resource types (index $r = RG, OT, TP$)

$W_p$ :

The set of working days according to pattern p ($W_p \subseteq T$)

Parameters

$d_i$ :

The duration of activity i

$r_i$ :

The required number of man units per time period to carry out activity i

$rt_i$ :

The ready time of activity i

$dd_i$ :

The due date of activity i

$\delta _n$ :

The maximum project duration

$c_j$ :

The cost associated with schedule j

$c^{r,v}$ :

The variable hiring cost for resource unit r per time period

$c^{r,f}$ :

The fixed hiring cost for resource unit r for the entire planning period

$c^{ID,v}$ :

The penalty cost per idle man unit per time period

$a_{jt}$ :

1, if personnel schedule j stipulates a working day for time period t, 0 otherwise

$b_j$ :

The number of overtime units for schedule j

$s_{pt}$ :

1, if cyclic work pattern p stipulates a working day for time period t, 0 otherwise

$w^{min}$ :

The minimum number of working assignments per period of 28 days

$w^{max}$ :

The maximum number of working assignments per period of 28 days

$n^{min}$ :

The minimum number of consecutive working assignments

$n^{max}$ :

The maximum number of consecutive working assignments

$\pi _t$ :

The dual price that is associated with constraint (3) of the master problem

Decision variables

$x_j$ :

The number of regular workers assigned to pattern j

$y_t$ :

The number of temporary personnel time units to be rented on time period t

$k_t$ :

The number of idle man units on time period t

$v_\textit{it}$ :

1, if activity i starts at the beginning of time period t, 0 otherwise

$u_t$ :

1, if a working day is assigned on time period t to an individual personnel member, 0 otherwise

$q_{m}$ :

the number of overtime units of the unit time period m assigned to an individual personnel member

$e_{p}$ :

1, if cyclic work pattern p is selected, 0 otherwise

Master problem formulation

$$\begin{aligned} \text {Minimise}&\quad Z = \sum _{j \in J}c_j \; x_{j} + \sum _{t \in T}c^{ID,v} \; k_t + \sum _{t \in T}c^{TP,v} \; y_t + \sum _{i \in N}\sum _{t \in T}c_\textit{it}^\textit{ACT} \; v_\textit{it} \end{aligned}$$

(2)

$$\begin{aligned} \text {subject to}&\quad \sum _{j \in J}a_{jt}\; x_{j} + y_t - k_t - \sum _{i \in N} r_i \sum _{t^* = t - d_i + 1}^t v_{it*} = 0 \qquad \forall t \in T \end{aligned}$$

(3)

$$\begin{aligned}&\quad \sum _{t = rt_i}^{t = dd_i} v_\textit{it} = 1 \qquad \forall i \in N \end{aligned}$$

(4)

$$\begin{aligned}&\quad \sum _{t \in T} t\; v_{jt} - \sum _{t \in T} t\; v_\textit{it} \ge d_i \qquad \forall (i,j) \in A \end{aligned}$$

(5)

$$\begin{aligned}&\quad \sum _{t \in T} t\; v_{nt} + d_n \le \delta _n \end{aligned}$$

(6)

$$\begin{aligned}&\quad x_j \ge 0 \; \text {and integer} \qquad \forall j \in J \nonumber \\&\quad k_t, \;y_t \ge 0 \; \text {and integer} \qquad \forall t \in T \nonumber \\&\quad v_\textit{it}\; \text {binary} \qquad \forall i \in N, \forall t \in T \end{aligned}$$

(7)

The objective (2) of the master problem embodies a non-regular measure of performance and aims to minimise the total resource scheduling cost over the limited set of personnel schedule columns and the activity scheduling cost. The penalty cost $c_j$ is defined by (the construction of) personnel schedule j and equals $c^{RG,f} + c^{RG,v} f_n + c^{OT,v} b_j$. As decision variables are included in this objective function coefficient, the objective function (2) is non-linear.

Constraint (3) embodies the staffing requirements for each time unit. As the requirements for man units per time unit are dependent on the start times of the activities, this constraint links the personnel and project scheduling decision variables. The possibility of hiring temporary workers and having crew idle days by the definition of the variables $y_t$ and $k_t$ allows that the number of regular personnel members differs from the required number of staff. Constraint (4) indicates that each activity is assigned to one particular start time, which lies in a pre-defined time window that is determined by the ready time and due date of the activity. Constraint (5) represents the direct precedence constraints with time lag 0, which stipulates that an activity cannot start before all its predecessors are finished. Activities are to be scheduled without pre-emption. Constraint (6) stipulates that the dummy end activity n should finish before $\delta _n$ or that the project should be finished before the project deadline. The non-negativity and integrality conditions on the personnel schedule and activity start time decision variables are stated in Eq. (7).

Personnel pricing subproblem formulation

$$\begin{aligned} \text {Minimise}&\quad \sum _{m \in M} c^{OT,v} q_{m} + c^{RG,f} + c^{RG,v} f_n - \sum _{t \in T} \pi _t u_{t} \end{aligned}$$

(8)

$$\begin{aligned} \text {subject to}&\quad \sum _{t \in T_m} u_t \ge w^{min} \qquad \forall m \in M \end{aligned}$$

(9)

$$\begin{aligned}&\quad \sum _{t \in T_m} u_t - q_m \le w^{max} \qquad \forall m \in M \end{aligned}$$

(10)

$$\begin{aligned}&\quad \sum _{t}^{t+n^{min}-1} u_t \ge n^{min}\; u_t \;(1 - u_{t-1}) \qquad \forall t \in T \end{aligned}$$

(11)

$$\begin{aligned}&\quad \sum _{t}^{t+n^{max}} u_t \le n^{max} \qquad \forall t \in T \end{aligned}$$

(12)

$$\begin{aligned}&\quad u_t \; \text{ binary } \qquad \forall t \in T \nonumber \\&\quad q_m\ge 0 \; \text{ and } \text{ integer } \qquad \forall m \in M \end{aligned}$$

(13)

The underlying personnel pricing problem for the regular workers is a manpower days-off scheduling problem with a homogeneous workforce. This problem assigns a single personnel member to specific days in a cyclic or non-cyclic manner. The objective (8) of this personnel scheduling pricing problem minimises the reduced cost of a new personnel schedule, which consists of the cost of a personnel schedule and the dual prices as input from the master problem. The feasibility of a line-of-work needs to conform to different (hard) case-specific time related constraints. A personnel member should work a number of working days that is between the minimum and maximum number of working assignments per unit period (resp. constraints (9), (10). Equation (10) defines the overtime personnel time units by penalising the number of days a personnel member works more than the standard number of working days $w^{max}$. The constraints minimum and maximum number of consecutive working assignment are formulated in Eqs. (11) and (12), respectively. The binary conditions on the original personnel assignment variables are stated in Eq. (13). Additional pattern constraints [cfr. Eq. (14)] are typically introduced in this subproblem when the personnel is scheduled in a cyclic manner.

$$\begin{aligned}&u_{t} - \sum _{p \in P} s_{pt} \; e_p \ge 0 \qquad \forall t \in T \end{aligned}$$

(14)

$$\begin{aligned}&\quad \quad \sum _{p \in P} e_p = 1 \end{aligned}$$

(15)

Constraint (14) enforces the working days to follow a strict pattern. The most commonly used (days-on, days-off)-pattern includes 5 consecutive working days followed by two consecutive days off, i.e. the (5, 2)-pattern. There are 7 such a patterns because of the cyclic nature of these patterns, i.e. the sequence of consecutive working days can start each day of the total pattern duration. Constraint (14) ensures that we select only one of the possible patterns.

These time-related constraints are typically evaluated over a personnel scheduling unit time period. The overall planning horizon can consist of multiple personnel scheduling unit time periods.

1.2 Formulation of the branching constraints

Personnel branching constraints

If the personnel scheduling variables are fractional, we apply the following two branching strategies, i.e.

(i) Branching on the sum of the personnel column variables

When the total number of regular crew members $\sum _{j \in \bar{J}} x_j = \beta$ is fractional, we add one of the following constraints to the restricted master problem formulation

$$\begin{aligned} \sum _{j \in \bar{J}} x_j \le \lfloor \beta \rfloor&\qquad \text {and} \qquad \sum _{j \in \bar{J}} x_j \ge \lceil \beta \rceil \end{aligned}$$

(16)

Each of these branching constraints will contribute an additional dual price that has to be subtracted from the objective of the personnel scheduling pricing problem [Eq. (8)] in order to calculate the reduced cost of a new column.

(ii) Personnel branching on the assignment variables

If the total number of personnel members is integer, the sum of personnel members assigned to a subset of time periods $\bar{T} \;(\bar{T} \subseteq T)$ is fractional, i.e. $\sum _{j \in \bar{J}: (a_{jt}) = 1, \forall t \in \bar{T}} x_j = \beta _{\bar{T}}$, and one of the following constraints is added to the restricted master problem

$$\begin{aligned} \sum _{j \in \bar{J}: (a_{jt}) = 1, \forall t \in \bar{T}} x_j \le \lfloor \beta _{\bar{T}}\rfloor&\qquad \text {and} \qquad \sum _{j \in \bar{J}: (a_{jt}) = 1, \forall t \in \bar{T}} x_j \ge \lceil \beta _{\bar{T}}\rceil \end{aligned}$$

(17)

Each of these branching constraints will give rise to an additional dual variable in the master problem, which complicates the calculation of the column with the most negative reduced cost in the pricing problem.

Project branching constraints

If the activity start time $v_\textit{it}$ is fractional for activity i on time period $t^*$, we add one of the following constraints to the restricted master problem formulation

$$\begin{aligned} \sum _{t \le t^*} v_\textit{it} = 1 \qquad \text {and} \qquad \sum _{t \ge {t}^* + 1} v_\textit{it} = 1 \end{aligned}$$

(18)