hmgt 320 week 4

Omega 95 (2020) 102057

Contents lists available at ScienceDirect

Omega

journal homepage: www.elsevier.com/locate/omega

Home healthcare integrated staffing and scheduling �

María I. Restrepo a , b , ∗, Louis-Martin Rousseau a , b , Jonathan Vallée c

a Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise, la Logistique et le Transport, CIRRELT, Montréal, Québec H3T 1J4, Canada b Département de Mathématiques et de Génie Industriel, Polytechnique Montréal, Montréal, Québec H3C 3A7, Canada c AlayaCare, 4200 St Laurent Blvd Suite 800, Montréal, Québec H2W 2R2, Canada

a r t i c l e i n f o

Article history:

Received 29 October 2018

Accepted 27 March 2019

Available online 16 April 2019

Keywords:

Staffing and scheduling

Home healthcare

Two-stage stochastic programming

Context-free grammars

a b s t r a c t

Workforce planning for home healthcare represents an important and challenging task involving complex

factors associated with labor regulations, caregivers’ preferences, and demand uncertainties. This task is

done manually by most home care agencies, resulting in long planning times and suboptimal decisions

that usually fail to meet the health needs of the population, to minimize operating costs, and to re-

tain current caregivers. Motivated by these challenges, we present a two-stage stochastic programming

model for employee staffing and scheduling in home healthcare. In this model, first-stage decisions cor-

respond to the staffing and scheduling of caregivers in geographic districts. Second-stage decisions are

related to the temporary reallocation of caregivers to neighboring districts, to contact caregivers to work

on a day-off, and to allow under- and over-covering of demand. The proposed model is tested on real-

world instances, where we evaluate the impact on costs, caregiver utilization, and service level by using

different recourse actions. Results show that when compared with a deterministic model, the two-stage

stochastic model leads to significant cost savings as staff dimensioning and scheduling decisions are more

robust to accommodate changes in demand. Moreover, these results suggest that flexibility in terms of

use of recourse actions is highly valuable as it helps to further improve costs, service level, and caregiver

utilization.

© 2019 Elsevier Ltd. All rights reserved.

1

a

t

a

e

i

t

i

h

t

p

p

i

T

1

d

a

t

t

t

t

l

a

o

s

c

v

e

i

m

c

h

0

. Introduction

Home healthcare refers to any type of care given to a patient

t his own home rather than in a healthcare facility like a hospi-

al or a clinic. Caregivers (e.g., personal support workers, nurses,

nd therapists) meet the patients’ needs by bringing all necessary

quipment at their homes and therein provide care. This activity

ncreases the quality of life for the patients, as they are allowed

o remain at home where they are most comfortable. Moreover,

t yields relevant cost savings for the entire healthcare system as

ospitalization costs are avoided [29] .

Home healthcare planning includes different decision levels

hat are usually classified in to three main categories: strategic

lanning, tactical planning , and operational planning [24] . Strategic

lanning relates to problems addressing structural decision mak-

ng to design and to dimension the healthcare delivery process.

his planning level often involves long planning horizons in which

� This manuscript was processed by Associate Editor Prokopyev. ∗ Corresponding author at: CIRRELT, Pavillon André-Aisenstadt, Montreal, QC H3T

J4, Canada.

E-mail address: [email protected] (M.I. Restrepo).

i

i

a

a

u

ttps://doi.org/10.1016/j.omega.2019.03.015

305-0483/© 2019 Elsevier Ltd. All rights reserved.

ecisions are based on aggregate information and forecasts. Some

pplications include districting problems in which the geographic

erritory where home care agencies operate is partitioned in dis-

ricts (i.e. smaller geographic zones). Tactical planning is related

o medium-term decision making dealing with the implementa-

ion of strategic decisions. Examples of problems in this decision

evel include personnel scheduling problems, where work patterns

re designed and allocated to caregivers to meet a forecasted and

ften uncertain demand for services. Operational planning includes

hort-term decision making related to the execution of the health-

are delivery process. Applications include visit rescheduling where

isit schedules are updated a few days in advance or during the

xecution day, to respond to events such as caregiver absenteeism,

ncoming urgent care requests, and changes in visit requirements.

The spatial distribution of patients and the uncertainty in de-

ands represent some important features found in home health-

are workforce planning. The incorporation of these aspects

ncreases the complexity of the problems under study. However,

ncluding them in the modeling and solution process could have

positive impact on an efficient service delivery in terms of costs

nd quality. First, the integration of decisions in several districts

sually generates flexible staffing and scheduling solutions that

2 M.I. Restrepo, L.-M. Rousseau and J. Vallée / Omega 95 (2020) 102057

2

s

s

t

q

s

m

c

K

b

a

d

m

t

p

t

q

n

a

c

l

u

e

t

s

a

s

t

t

m

a

d

o

s

i

n

a

i

g

a

u

m

u

u

s

a

a

c

s

t

s

g

a

t

i

a

c

t

m

e

m

t

g

respond in a better way to fluctuating demand, since caregivers

are allowed to work in a different district than the one they are

dedicated to [27] . In a similar way, the incorporation of demand

uncertainty provides solutions that will be more robust to accom-

modate changes in demand associated with the arrival of new pa-

tients and with changes in patients’ conditions.

In this paper, we focus on the integration of two medium-term

workforce planning problems: the staff dimensioning problem and

the caregiver scheduling problem . This integration deals with the

definition of the number of caregivers to recruit per district, as

well as with the allocation of schedules to caregivers while consid-

ering demand uncertainty. Caregiver schedules are defined by se-

quences of work stretches and rest stretches . Work stretches contain

a consecutive number of work days, where each workday contains

exactly one shift (e.g., morning shift, night shift) executed in one

district. Similarly, rest stretches represent a consecutive number of

days-off. The composition of feasible schedules is subject to work

regulations ensuring, among others, that there is a minimum rest

time between consecutive shifts, that each work stretch includes

a sequence of shifts between a minimum and a maximum value,

and that each rest stretch contains a sequence of days-off between

a minimum and a maximum value.

Our work is motivated by the challenges experienced in Alay-

aCare, a start-up company based in Canada developing software

solutions for home healthcare agencies. Most of these agencies cur-

rently lack the tools to forecast future demands, to manage their

labor resources, and to optimize work assignments. Hence, the

staffing and scheduling planning is mostly done manually by ex-

perienced coordinators. Since this planning method often fails to

include most of the rules for the composition of schedules, as well

as accurate demand forecasts, it results in the inability to hire an

adequate number of caregivers, to retain current caregivers, and to

meet the needs of patients.

This paper has the following contributions. First, to the best

of our knowledge, our work is the first to propose an optimiza-

tion approach that integrates staffing and scheduling decisions in

the context of home healthcare. To do so, we present a two-stage

stochastic programming model where first-stage decisions corre-

spond to the staffing and scheduling of caregivers at each geo-

graphic district, and second-stage decisions are related to the tem-

porary reallocation of caregivers to neighboring districts, to con-

tact caregivers to work on a day-off, and to allow under-covering

and over-covering of demand. Second, although other authors have

already benefited from the expressiveness of context-free gram-

mars to build short-term schedules with a planning horizon of one

day (see [15,38] ), we believe that our work is the first that uses

context-free grammars to build schedules over long time horizons

(i.e., one month or more) guaranteeing horizontal work regulations

such as the minimum rest time between consecutive shifts and the

allocation of a minimum and a maximum number of shifts to each

work sequence. Context-free grammars allow to easily incorporate

horizontal regulations as a set of recursive rewriting rules (or pro-

ductions) to generate patterns of strings [23] , in our case, to gener-

ate caregiver schedules. Third, we discuss how to forecast the de-

mand of home care services and how to integrate these forecasts

in a two-stage stochastic programming model. Fourth, we perform

an extensive computational study on real-based data to evaluate

the impact in costs, caregiver utilization and service level, by using

several recourse actions, various scheduling policies and different

planning horizons.

The paper is organized as follows. In Section 2 , we review re-

lated works on caregiver staffing and scheduling for healthcare.

In Section 3 , we present the methodology to solve the integrated

caregiver staffing and scheduling for home healthcare. Computa-

tional experiments are presented and discussed in Section 4 . Con-

cluding remarks and future work follow in Section 5 .

. Related work

Healthcare planning problems for hospitals have been exten-

ively studied over the past years. In particular, nurse staffing and

cheduling problems have attracted most of the attention from

he operations research community since the generation of high-

uality nurse schedules can lead to improvements in hospital re-

ource efficiency, in patient safety and satisfaction, and in ad-

inistrative workload [9] . Recent approaches to this problem in-

lude the works presented in Maenhout and Vanhoucke [32] and

im and Mehrotra [26] . Maenhout and Vanhoucke [32] present a

ranch-and-price procedure to solve an integrated nurse staffing

nd scheduling problem, where the number of nurses has to be

etermined for each profession in order to balance, over several

onths, the workforce costs and the coverage of patients in mul-

iple hospital departments. Results indicate that staffing multi-

le departments simultaneously and including nurse skills into

he staffing decisions lead to significant improvements in schedule

uality in terms of cost, employees’ job satisfaction, and effective-

ess in providing high-quality care. Kim and Mehrotra [26] present

two-stage stochastic integer program with mixed-integer re-

ourse to integrated nurse staffing and scheduling. In the prob-

em, first-stage decisions define initial staffing levels and sched-

les, while second-stage decisions adjust these schedules at a time

poch closer to the actual date of demand realization. Results show

hat when compared with a deterministic model, the two-stage

tochastic model leads to significant cost savings. The work of Kim

nd Mehrotra [26] is similar to ours as the authors use a two-stage

tochastic integer programming program with recourse to solve in-

egrated staffing and scheduling problems in healthcare. The objec-

ive of both works is to find initial staffing levels and schedules to

inimize overall labor costs by right-sizing the staff and by bal-

ncing understaffing and overstaffing costs. However, their work

iffers in some important aspects from ours. First, as opposed to

ur work, the work of Kim and Mehrotra does not consider the

patial dimension in the planning, since the staffing and schedul-

ng are done for nurses in a hospital and not for caregivers that

eed to visit patients in different geographic zones. Second, the

uthors assume that work patterns repeat from week to week dur-

ng the planning horizon and that all possible weekly patterns are

enerated in advance. Instead, in our approach, caregiver schedules

re allowed to be different from week to week, and weekly sched-

les are not generated in advance, as one of the objectives of our

odel is to build (with context-free grammars) caregiver sched-

les that guarantee several work regulations. Third, regarding the

se of recourse actions, both works allow for calling in additional

taff when needed. However, our work uses an additional recourse

ction corresponding to the reallocation of caregivers to neighbor

reas and, contrary to Kim and Mehrotra [26] , we do not allow to

ancel shifts from the scheduled staff.

Problems related to the routing and scheduling of human re-

ources involve the most important volume of existing investiga-

ions in home healthcare planning. These problems define the as-

ignment of caregivers to patients, as well as the design of care-

ivers routes to reduce travel distances, to decrease overtime costs,

nd to improve the continuity of care . Continuity of care guarantees

hat a patient is most of the time visited by the same caregiver

n the whole duration of the care plan. Home healthcare routing

nd scheduling problems often require the incorporation of several

onstraints related to the management of caregivers’ work regula-

ions, to the matching of caregivers’ skills and patients’ require-

ents, and to the satisfaction of patients’ and caregivers’ pref-

rences. Since the addition of these constraints often makes the

odeling and solution of this problem intractable, different au-

hors have proposed heuristic methods such as tabu search al-

orithms [21] and rolling horizon approaches [3,35] to efficiently

M.I. Restrepo, L.-M. Rousseau and J. Vallée / Omega 95 (2020) 102057 3

s

a

S

s

i

j

o

t

p

o

L

p

m

t

c

w

e

i

c

p

t

a

b

t

c

[

t

a

w

p

i

t

c

[

p

T

r

s

g

b

v

a

o

i

i

a

l

s

i

a

p

w

s

s

c

(

p

s

t

q

h

s

s

c

s

w

s

m

h

r

c

p

w

s

s

t

h

c

e

m

[

e

n

s

o

i

u

s

t

l

c

w

c

b

s

F

a

c

a

w

a

i

fi

z

w

t

i

S

a

p

n

d

i

p

p

3

h

a

t

z

w

t

l

d

olve practical instances of this problem. Exact approaches have

lso been developed in Bachouch et al. [2] and Cappanera and

cutellà [11] to deal (in an integrated way) with the assignment,

cheduling, and routing decisions.

Real applications of routing and scheduling of human resources

n home healthcare often require the optimization of multiple ob-

ectives, as well as the incorporation of uncertainty in demands to

btain robust solutions that react better to changes in demand. In

hat order of ideas, Duque et al. [17] and Braekers et al. [8] pro-

ose bi-objective optimization approaches to maximize the quality

f service and to minimize the distance traveled by the caregivers.

anzarone et al. [30] formulate different scenario-based stochastic

rogramming models to solve the robust nurse-to-patient assign-

ent problem that preserves the continuity of care and balances

he operators’ workloads. Lanzarone and Matta [28] use analyti-

al policies to address the nurse-to-patient assignment problem, in

hich both continuity of care and demand uncertainty are consid-

red. Nguyen et al. [34] present a variant of a home care problem

n which the availability of nurses is uncertain (e.g., nurses might

all sick on short notice). To address this problem, the authors pro-

ose to use a matheuristic optimization approach for robust nurse-

o-patient assignment and nurse scheduling and routing. Carello

nd Lanzarone [13] and Lanzarone and Matta [29] present ro-

ust approaches for the nurse-to-patient assignment under con-

inuity of care. In the former work, the authors apply the robust

ardinality-constrained approach proposed in Bertsimas and Sim

4] to incorporate the uncertainty in patients’ demands. In the lat-

er work, the authors propose an analytical policy that takes into

ccount the stochasticity of new patients’ demands and nurses

orkloads. Hewitt et al. [22] solve the nurse-to-patient assignment

roblem and develop a solution method to incorporate uncertainty

n demand as future patient requests are often unknown at the

ime of planning. Cappanera et al. [12] extend the cardinality-

onstrained robust approach presented in Cappanera and Scutellà

11] to include uncertainty in patients’ demands in a home care

roblem integrating assignment, scheduling, and routing decisions.

he interested reader is referred to Fikar and Hirsch [18] for a

ecent survey of current works in home healthcare routing and

cheduling.

Contrarily to the routing and scheduling of caregivers, inte-

rated staffing and scheduling problems for home healthcare have

een rarely studied in the literature. This problem is highly rele-

ant, as human resources need to be properly managed in order to

void inefficient visit schedules, treatment delays, and low quality

f service [33] . Two medium-term home healthcare nurse schedul-

ng problems are addressed in Trautsamwieser and Hirsch [42] and

n Wirnitzer et al. [43] . In these works, a given set of nurses is

llocated to schedules which are built by including work regu-

ations associated with the allocation of days-off between work

tretches, the allocation of rest times between consecutive work-

ng days, and the allocation of a maximum working time per day

nd per week. Trautsamwieser and Hirsch [42] use a branch-and-

rice-and-cut solution approach to solve the problem over a one-

eek planning horizon. Experiments on real-world based instances

how that the proposed method helps to significantly reduce the

chedule planning time when compared to a manual planning pro-

ess. Wirnitzer et al. [43] present a mixed integer programming

MIP) model to address the nurse scheduling problem for longer

lanning horizons (e.g., one month). Experiments on real-world in-

tances suggest that using the MIP model not only helps to reduce

he time to generate the schedules but also improves the solution

uality from the patients’ and from the nurses’ point of view. A

ome healthcare nurse staffing problem with uncertain demands is

tudied in Rodriguez et al. [39] . The authors propose to use a two-

tage stochastic programming approach where first-stage decisions

orrespond to a global staff dimensioning, while second-stage deci-

ions are related to the allocation of schedules (that do not include

ork regulations or continuity of care) to nurses with different

kills. Results indicate that the proposed approach helps decision-

akers with staffing and scheduling decisions before opening a

ome healthcare service or before hiring a new nurse.

Forecasting patients demands represent an important step in

obust approaches for planning and managing resources in health

are. These forecasts can create alerts for the management of

atient overflows, they can enhance preventive health care, and

hen used as an input for planning human resources, they can

ignificantly reduce the associated costs in overstaffing and under-

taffing [40] . Several methods have been proposed in the litera-

ure to forecast demands and to support healthcare providers in

uman resource planning before the care execution. These fore-

asting methods include, among others, Markovian decision mod-

ls [19,31] , Bayesian models [1] , and autoregressive moving average

odels [25] . In this paper, we use a decomposable time series model

20] to forecast the demand since this type of model is relatively

asy to implement and to explain to the end user.

The literature review in home healthcare planning reveals that

o method has been proposed to integrate caregiver staffing and

cheduling when demand is stochastic and when the composition

f schedules includes complex work regulations, in particular, ex-

sting works show that when rules for the composition of sched-

les are included in the problem, staffing decisions are not con-

idered since it is assumed that these decisions have been already

aken in a previous step of the decision process [16] . In a simi-

ar way, when staffing decisions are included in the problem, the

omposition of caregivers’ schedules does not consider important

ork rules such as the allocation of minimum rest time between

onsecutive shifts. This paper addresses these gaps in the literature

y proposing a model that integrates staff dimensioning with staff

cheduling decisions for a medium-term home healthcare problem.

urthermore, the proposed model includes uncertainty in demands

nd the incorporation of several work rules for the generation of

aregivers’ schedules, providing solutions that are expected to re-

ct in a robust way to variations in demand and that comply with

orkplace agreements. We remark that although other works have

lready used context-free grammars to solve personnel schedul-

ng problems under stochastic demand (see [38] ), our work is the

rst one that uses grammars to build schedules over time hori-

ons longer than one day (i.e., a month or longer). Additionally, our

ork differs from the work in [38] by three other aspects. First,

his paper considers staffing decisions, while the work presented

n [38] assumes that the number of employees is already given.

econd, in this paper, employees can work in different geographic

reas, while in [38] all employees are assumed to work in a single

lace. Third, while this paper uses the reallocation of caregivers to

eighboring areas and the possibility of calling caregivers to work

uring one of their days-off as the set of recourse actions, the work

n [38] uses the allocation of activities and breaks to daily shifts to

rotect against demand uncertainty.

Next section presents the definition and formulation of the

roblem studied in this paper.

. Problem definition and formulation

The integrated caregiver staffing and scheduling problem for

ome healthcare considers a territory divided into | C | geographic

reas or districts , each one covering several patients. We assume

hat each patient is assigned to only one district. The planning hori-

on includes | D | days, where each day d ∈ D is covered by a set of orking shifts S characterized by a set of attributes, namely: a start

ime b s , a day of the week d s (e.g. Monday, Tuesday,...), a length

s , and a cost c s that depends on the shifts’s length l s and the

ay of the week d s . Each district c ∈ C defines a different type of

4 M.I. Restrepo, L.-M. Rousseau and J. Vallée / Omega 95 (2020) 102057

i

m

f

n

d

b

s

t

w

c

t

i

v

A

a

v

h

3

p

n

p

a

v

o

t

i

v

i

s

a

d

w

s

m

b

P

d

σ

1

i

σ v

w

b

a

f

s

d

a

m

(

v

t

caregiver e ∈ E ( E = C) working in at most one shift s ∈ S per day. To guarantee the continuity of care for patients, caregiver e ∈ E should work most of the time in his district. However, caregivers might

be temporarily reallocated (at the expense of an additional cost)

to a compatible district c ∈ C during shift s ∈ S to meet unexpected demands. Campbell [10] showed that schedule flexibility resulting

from the reallocation of employees can be more valuable than the

perfect information about demand, especially when demand uncer-

tainty is high.

We assume that demands (expressed as the number of vis-

its during day d ∈ D in district c ∈ C and shift s ∈ S ) are uncertain. Hence, when solving the integrated caregiver staffing and schedul-

ing problem for home healthcare we consider two types of deci-

sions. The first type includes the first-stage decisions, which define

the staffing levels (i.e. the number of caregivers to hire), as well

as the allocation of individual schedules to each caregiver. The sec-

ond type incorporates the second-stage decisions, which define the

adjustment of caregivers’ schedules a few days before their execu-

tion. These adjustments include the caregivers reallocation to com-

patible districts, contacting caregivers to work during their day-off,

and allowing demand over-covering and under-covering. Because

schedules must be available to caregivers at least one month in ad-

vance to allow for choices, we assume that the planning horizon is

larger than or equal to 4 weeks. At the beginning of this planning

horizon staffing and scheduling decisions (first-stage decisions) are

made to minimize the sum of the total staffing costs, the expected

recourse costs, and the expected over-covering and under-covering

costs. Since the actual demand is often revealed one week in ad-

vance, the planned schedules are adjusted at the beginning of each

week for the following week. These adjustment decisions (second-

stage decisions) are applied for each type of shift at each day of

the week.

The methodology to solve the problem studied in this paper is

divided into three steps. The first step is related to the demand

forecasting and scenario generation. The second step involves the

definition of caregivers’ schedules by means of grammars. The

third step uses a two-stage stochastic programming optimization

model for caregiver staffing and schedule allocation. The descrip-

tion of these steps is presented next.

3.1. Demand forecasting and scenario generation

The ability to accurately forecast the demand for visits is a fun-

damental requirement for developing robust decision support tools

in home healthcare resource planning. In fact, several strategic and

tactical decisions in home healthcare are based on forecasts of de-

mand for resources. For instance, recruitment decisions are mainly

driven by forecasts on the number of visits required by the pa-

tients in a given planning horizon. If this demand is accurately pre-

dicted, several operational problems such as under-utilization and

over-utilization of caregivers can be avoided. On the contrary, inac-

curate forecasts threaten the quality of the plans obtained leading

to more expensive solutions that could be infeasible for some de-

mand scenarios. In this section, we present a methodology for de-

mand forecasting and scenario generation in home healthcare. We

remark that the methods used to forecast and to generate scenar-

ios for the demand are possible approaches, developing and evalu-

ating different methods for these tasks is out of the scope of this

work.

3.1.1. Demand forecasting

To estimate the number of patients b dcs to visit during day d ∈ D in district c ∈ C and shift s ∈ S we use a decomposable time se- ries model with three main model components: growth, season-

ality , and holidays . These components (included in Eq. (1) ) repre-

sent the growth function ( g ) which models non-periodic changes

dsc

n the value of the time series, the periodic changes function ( s dsc )

odelling weekly or yearly seasonality, and the effects of holidays

unction ( h dsc ) including effects from days such as Christmas and

ew year’s day. The error term �dsc represents irregular changes in emand, which are not accommodated by the time series model.

dsc = g dsc + s dsc + h dsc + �dsc , for each s ∈ S, c ∈ C (1) Eq. (1) is estimated with Facebook Prophet which is an open

ource library to create quick, accurate and completely automated

ime series forecasts. This tool uses an additive regression model

ith four components: (i) a piecewise linear or logistic growth

urve to detect changes in trends by selecting change points from

he historical data; (ii) a yearly seasonal component modeled us-

ng Fourier series; (iii) a weekly seasonal component using dummy

ariables; (iv) a user-provided list of relevant holidays. Unlike with

RIMA models, the time series measurements do not need to have

regular period. Hence, there is no need to interpolate missing

alues to fit. The reader is referred to [41] for more information on

ow Facebook Prophet works.

.1.2. Scenario generation

We only consider uncertainty in the number of visits per day,

er shift, and per district in the generation of the different sce-

arios for our problem. Therefore, we assume that the duration of

atients’ visits and travel times are deterministic parameters which

re included in the caregiver capacities (i.e. the number of patients

isited per shift). We allow these capacities to vary with the day

f the week, with the type of shift, and with the district where

he caregiver is working. For instance, the capacity of night shifts

s generally lower than the capacity of morning shifts, as patients

isited at night need care for longer periods than patients visited

n the morning. We assume that the number of visits per day, per

hift, and per district is a random variable with finite support. In

ddition, we define �d as a set of scenarios for the demand at each

ay d ∈ D , and p (w ) d

> 0 as the probability of occurrence of scenario

∈ �d . Note that ∑

w ∈ �d p (w ) d

= 1 , ∀ d ∈ D . The scenarios for the demand are generated with Monte Carlo

imulation. We assume that given the estimated values for the

ean of demand ( ̂ b dsc ) and the estimated values for the upper

ound ( ̂ b u dsc

) of a ( 1 − α) confidence interval returned by Facebook rophet after fitting model (1) to the historical data, the standard

eviation ˆ σdsc can be computed with Eq. (2) .

ˆ dsc = ( ̂ b u dsc − ˆ b dsc ) × √

n

Z 1 − α 2

(2)

Where Z 1 − α 2

is the value for a standard normal variable with a

− α 2

probability to the right, and n denotes the size of the train-

ng set used to estimate time series model (1) . Once the values for

ˆ dsc are obtained, we can compute the demand for the number of

isits in district c ∈ C and shift s ∈ S during day d ∈ D under scenario ∈ �d as:

(w ) dsc

= max {

0 ,

⌊ ˆ b dsc + R ∗

ˆ σdsc √ n

⌉ } (3)

Where R represents the value of a random variable that follows

standard normal distribution and � � denotes the nearest integer unction.

An example of the scenario generation for a given day d ∈ D is hown in Tables 1 and 2 . Table 1 presents for each combination of

istricts and shifts (denoted as d 0 , d 1 , d 2 , and d 3 for the districts,

nd a 4 , m 4 , m 8 , and n 10 for the shifts) the values for the forecasted

ean demand ( ̂ b ), the values for the lower bound and upper bound

̂

b l , ˆ b u ) of a 90% confidence interval for the forecasted demand, the

alues for the actual value of the demand ( b ), and the values for

he possible values for the demand (list) with their corresponding

M.I. Restrepo, L.-M. Rousseau and J. Vallée / Omega 95 (2020) 102057 5

Table 1

Results for the demand forecasting and Monte Carlo simulation.

district_shift b ˆ b l ˆ b u ˆ b list count

d 0 _ m 4 1 1 2 1 [1] [500]

d 0 _ m 8 2 1 3 1 [1, 2, 0, 3] [314, 157, 25, 4]

d 0 _ n 10 2 1 2 1 [1, 2, 0] [466, 30, 4]

d 1 _ a 4 7 5 9 7 [7, 6, 5, 8, 9, 4, 10, 3] [151, 134, 87, 77, 23, 22, 5, 1]

d 1 _ m 4 5 2 8 4 [4, 5, 6, 3, 2, 7, 1, 8, 0, 9] [122, 110, 84, 78, 49, 31, 14, 9, 2, 1]

d 1 _ m 8 14 12 17 14 [13, 14, 15, 12, 16, 11, 17, 18, 10] [126, 122, 106, 56, 47, 22, 13, 5, 3]

d 1 _ n 10 9 6 10 7 [8, 9, 7, 6, 10, 11, 5, 12] [182, 128, 116, 33, 32, 5, 3, 1]

d 2 _ m 4 2 1 3 1 [1, 2, 0, 3] [304, 154, 40, 2]

d 2 _ m 8 2 1 2 1 [1, 2, 0] [460, 34, 6]

d 2 _ n 10 2 1 2 1 [1, 2, 0] [420, 78, 2]

d 3 _ a 4 3 1 5 2 [3, 2, 4, 1, 5, 0] [179, 176, 67, 59, 10, 9]

d 3 _ m 4 4 3 6 4 [4, 3, 5, 2, 6, 7, 1] [204, 129, 116, 26, 23, 1, 1]

d 3 _ m 8 4 2 6 4 [3, 4, 2, 5, 1, 6, 7] [192, 147, 88, 55, 9, 8, 1]

d 3 _ n 10 4 3 6 4 [4, 3, 5, 2, 6, 1] [212, 151, 93, 30, 11, 3]

Table 2

Example of 10 scenarios for a given day in the planning horizon.

district_shift Scenario

1 2 3 4 5 6 7 8 9 10

d 0 _ m 4 1 1 1 1 1 1 1 1 1 1

d 0 _ m 8 1 1 1 2 2 3 1 2 2 1

d 0 _ n 10 1 1 1 1 2 1 1 1 1 1

d 1 _ a 4 7 5 5 6 8 8 5 7 6 7

d 1 _ m 4 3 3 5 5 5 4 6 6 6 2

d 1 _ m 8 11 15 13 13 14 13 13 11 16 11

d 1 _ n 10 7 11 9 9 5 7 6 8 8 6

d 2 _ m 4 2 2 1 2 1 1 1 1 1 2

d 2 _ m 8 1 1 2 1 1 1 1 1 1 2

d 2 _ n 10 1 1 1 1 1 2 1 2 1 1

d 3 _ a 4 3 3 3 2 2 2 3 4 3 1

d 3 _ m 4 4 5 4 4 3 3 5 5 3 3

d 3 _ m 8 3 3 5 3 3 5 3 2 3 4

d 3 _ n 10 3 5 4 5 3 4 4 3 6 3

f

s

u

d

3

(

c

C

o

a

a

〈 t

s

w

t

a

s

f

g

n

b

p

d

a

n

t

s

i

d

q

p

d

i

r

r

p

E

s

d

d

G

W

o

s

r

b

t

w

t

s

e

s

P

a

d

requency (count), after running 500 simulations. Table 2 shows a

ample of 10 scenarios from the 500 scenarios generated. Each col-

mn from this table presents the demand values (number of visits)

uring day d for each combination of districts and shifts.

.2. Grammars

A context-free grammar is a set of recursive rewriting rules

or productions) used to generate patterns of strings, or (in the

ase of personnel scheduling) to generate schedules or daily shifts.

ontext-free grammars have been successfully used in the context

f personnel scheduling. Applications include the solution of multi-

ctivity and multi-task shift scheduling problems [7,15] and multi-

ctivity tour scheduling problems [37,38] .

A context-free grammar consists of a four-tuple G = �, N, S, P 〉 , where � is an alphabet of characters called the erminal symbols, N is a set of non-terminal symbols , S ∈ N is the tarting symbol, and P is a set of productions represented as A → α, here A ∈ N is a non-terminal symbol and α is a sequence of

erminal and non-terminal symbols. The productions of a grammar

re used to generate new symbol sequences until all non-terminal

ymbols have been replaced by terminal symbols. A context-

ree language is the set of sequences accepted by a context-free

rammar.

A parse tree is a tree where each inner-node is labeled with a

on-terminal symbol and each leaf is labeled with a terminal sym-

ol. A grammar recognizes a sequence if and only if there exists a

arse tree where the leaves, when listed from left to right, repro-

uce the sequence. A DAG � is a directed acyclic graph that embeds

ll parse trees associated with words of a given length n recog-

ized by a grammar. The DAG � has an and/or structure where

he and-nodes represent productions from P and or-nodes repre-

ent non-terminals from N and letters from �. An and-node is true

f all of its children are true. An or-node is true if one of its chil-

ren is true. The root node is true if the grammar accepts the se-

uence encoded by the leaves. The DAG � is built with a procedure

roposed in Quimper and Walsh [36] using bottom-up parsing and

ynamic programming.

In employee scheduling, the use of grammars allows one to

nclude work rules regarding the definition of work stretches and

est stretches in an easy way. Thus, feasible schedules can be rep-

esented as words in a context-free language. Specifically, for the

roblem addressed in this paper we use grammars to:

• Generate work stretches representing sequences of work span-

ning a minimum and a maximum number of days. • Generate rest stretches denoting sequences of days-off spanning

a minimum and a maximum number of days. • Define a minimum and a maximum consecutive number of

morning, afternoon, and night shifts within a work stretch. For

instance, a given work stretch cannot have more than 3 night

shifts in a row. • Forbid infeasible transitions between shifts by associating costs

to productions. For instance, a night shift cannot be followed by

a morning shift. • Allocate a rest stretch between two work stretches.

xample 1. Consider the following grammar for an employee

cheduling problem where the planning horizon consists of five

ays, work stretches have a length of three consecutive days, and

ays-off can be allocated in consecutive or nonconsecutive days:

= (� = (w, r) , N = (S, F , Q , W, R ) , P, S) Where productions P are: S → RF | F R | Q R, F [3,3] → WW,

→ WW | w, Q → RF, R → RR | r and symbol | specifies the choice f production. Letter w represents the allocation of a working

hift and letter r represents the allocation of a day-off. P [min, max] estricts the subsequences generated by production P to a length

etween a minimum and a maximum number of days.

In this grammar, production F [3,3] → WW generates two non- erminal symbols W , meaning that the schedule will include a

ork stretch of exactly three days. Production Q → RF generates wo non-terminal symbols R and F , meaning that the schedule will

tart with a rest stretch and then it will include a work stretch of

xactly three days. Production R → RR generates two non-terminal ymbols R , meaning that the schedule will include a rest stretch.

roductions W → w and R → r generate terminal symbols associ- ted with the allocation of a shift and with the allocation of a

ay-off to the schedule of an employee, respectively. The last three

6 M.I. Restrepo, L.-M. Rousseau and J. Vallée / Omega 95 (2020) 102057

Fig. 1. DAG � on schedules of length five.

m

p

r

t

e

i

l

i

a

a

a

a

e

s

s

3

m

�

c

o

f

o

productions are S → RF , S → F R, and S → Q R . The first produc- tion generates a schedule starting with two days-off followed by

a work stretch. The second production generates a schedule start-

ing with a work stretch followed by two days-off. The last produc-

tion generates a schedule starting with one day-off, followed by

a work stretch, to finish with one day-off. The three words rec-

ognized as valid schedules by the grammar in this example are

rrwww, wwwrr , and rwwwr .

Let O π dl

be the or-nodes associated with π ∈ N ∪ � (i.e. with non- terminals from N or letters from �) that generate a subsequence

from day d of length l . Note that if π ∈ �, the node is a leaf and l is equal to one. On the contrary, if π ∈ N the node represents a non- terminal symbol and l ≥ 1. A ,k

dl is the k th and-node representing

production ∈ P generating a subsequence from day d of length l . There are as many A

,k dl

nodes as there are ways of using to gen-

erate a sequence of length l from day d . As previously mentioned,

undesired productions (i.e. transitions between a night shift and a

morning shift) are penalized by a cost denoted as c ,k dl

. The sets of

or-nodes, and-nodes, and leaves of DAG � are denoted by O, A , and

L , respectively. The root node is described by O S 1 n

and its children

by A ,k 1 n

. The children of or-node O π dl

are represented by ch (O π dl

) and

its parents by par(O π dl

) . Similarly, the children of and-node A ,k dl

are

represented by ch (A ,k dl

) and its parents by par(A ,k dl

) . For more de-

tails on the use of grammars in employee scheduling we refer the

reader to Côté et al. [14] .

Fig. 1 shows the DAG � associated with the grammar from

Example 1 . Observe that this figure includes three parse trees, each

one representing one word (schedule) recognized by the grammar.

As an example, we present a parse tree in dashed lines generating

schedule rwwwr .

The works of Restrepo et al. [38] and Côté et al. [14] on anony-

ous tour scheduling problems with multiple activities are exam-

les of the use of context-free grammars to represent the work

ules involved in the composition of shifts. In both works, the au-

hors present implicit grammar-based integer programming mod-

ls where the word length n corresponds to the number of periods

n the planning horizon, the set of work activities corresponds to

etters in the alphabet �, and each employee is allowed to work

n any work activity. In these models, the logical clauses associ-

ted with � are translated into linear constraints on integer vari-

bles. Each and-node A and each leaf L in � are represented by

n integer variable denoting the number of employees assigned to

specific subsequence of work. Since this grammar-based model

fficiently encapsulates the constraints for the generation of the

chedules, it is used as a component in the formulation of the two-

tage stochastic problem presented next.

.3. Two-stage stochastic optimization model

The formulation of the two-stage stochastic programming

odel requires a previous definition of the grammars and DAGs

containing specific work regulations for the composition of valid

aregiver schedules. Since work regulations could vary depending

n the type of caregiver, we define a different grammar and a dif-

erent DAG �e for each e ∈ E . The notation used for the formulation f the problem is as follows:

Parameters:

– κ e dsc

: number of visits a caregiver of type e ∈ E working on shift s ∈ S can perform in district c ∈ C during day d ∈ D ;

– c e ds

: non-negative cost associated with one caregiver of type

e ∈ E working on shift s ∈ S during day d ∈ D ;

M.I. Restrepo, L.-M. Rousseau and J. Vallée / Omega 95 (2020) 102057 7

D

s

m

y

y

u

A

u

v

y

y

c

t

s

C

s

r

t

�

s

m

fl

s

t

e

g

t

s

t

s

t

t

t

n

a

E

t

a

m

x

z

s

– c ,k,e dl

: non-negative cost associated with the k th and-node rep-

resenting production from �e , producing a sequence from

day d ∈ D of length l for caregiver e ∈ E ; – ˆ b dsc : mean demand for the number of visits in district c ∈ C and

shift s ∈ S during day d ∈ D ; – b

(w ) dsc

: demand for the number of visits in district c ∈ C and shift s ∈ S during day d ∈ D under scenario w ∈ �d ;

– c + dsc

, c − dcs

: non-negative demand over-covering and under-

covering costs for district c ∈ C and shift s ∈ S during day d ∈ D , respectively;

– t e dsc

: non-negative transition cost associated with the realloca-

tion one caregiver of type e ∈ E to district c ∈ C during day d and shift s ∈ S ;

– r e ds

: non-negative cost associated with assigning shift s ∈ S to a caregiver of type e ∈ E during its rest day d ∈ D ;

– δe sc : binary parameter that takes value 1 if caregiver e ∈ E admits a reallocation to district c ∈ C during shift s ∈ S , and it assumes value 0 otherwise.

ecision variables:

– u e : variable that denotes the number of caregivers of type e ∈ E to hire;

– v ,k,e dl

: variable that denotes the number of caregivers of type

e ∈ E assigned to the k th and-node representing production from �e producing a sequence from day d ∈ D of length l ;

– y e ds

: variable that denotes the number of caregivers of type e ∈ E working on shift s ∈ S during day d ∈ D (equivalent to the num- ber of caregivers of type e ∈ E assigned to leaf O s,e

d1 );

– y e dr

: variable that denotes the number of caregivers of type e ∈ E having rest during day d ∈ D (equivalent to the number of care- givers of type e ∈ E assigned to leaf O r,e

d1 );

– x e (w ) dsc

: variable that denotes the number of caregivers of type

e ∈ E assigned to work in district c ∈ C and shift s ∈ S during day d ∈ D under scenario w ∈ �d ;

– z e (w ) ds

: variable that denotes the number of caregivers of type

e ∈ E assigned to work during a day-off on shift s ∈ S during day d and scenario w ∈ �d ;

– s +(w ) dsc

and s −(w ) dsc

: slack variables denoting demand over-covering

and under-covering in district c ∈ C and shift s ∈ S during day d ∈ D under scenario w ∈ �d , respectively. The formulation for the stochastic caregiver staffing and

cheduling problem is as follows.

in ∑ d ∈ D

∑ s ∈ S

∑ e ∈ E

c e ds

y e ds

+ ∑ d ∈ D

∑ e ∈ E

∑ A ,k,e

dl ∈ A e

c ,k,e dl

v ,k,e dl

+ Q (y ) (4)

e ds

= ∑

A , 1 ,e d1

∈ par(O s,e d1

)

v , 1 ,e d1

, ∀ d ∈ D, e ∈ E, s ∈ S, (5)

e dr

= ∑

A , 1 ,e d1

∈ par(O r,e d1

)

v , 1 ,e d1

, ∀ d ∈ D, e ∈ E, (6)

e = ∑

A ,k,e 1 n

∈ ch (O S,e 1 n

)

v ,k,e 1 n

, ∀ e ∈ E, (7)

∑

,k,e dl

∈ ch (O π ,e dl

)

v ,k,e dl

= ∑

A ,k,e dl

∈ par(O π ,e dl

)

v ,k,e dl

,

∀ e ∈ E, O π ,e dl

∈ O e \ { O S,e 1 n

∪ L e } , (8)

e ≥ 0 and integer , ∀ e ∈ E, (9)

,k,e dl

≥ 0 and integer , ∀ d ∈ D, e ∈ E, A ,k,e dl

∈ A e , (10)

e ds

≥ 0 and integer , ∀ d ∈ D, e ∈ E, s ∈ S, (11)

e dr

≥ 0 and integer , ∀ d ∈ D, e ∈ E. (12) The objective of model (4) –(12) is to minimize the total staffing

ost (i.e. allocation of working shifts to caregivers), the penaliza-

ion for certain transitions between shifts (i.e. transition from night

hifts to morning shifts), and the expected recourse function Q (y ) . onstraints (5) –(6) set the value of variables y e

ds and y e

dr as the

ummation of the value of the parents of leaf nodes O s,e d1

and O r,e d1

,

espectively. Constraints (7) define the number of caregivers of

ype e ∈ E to hire. Constraints (8) guarantee, for every or-node in e , e ∈ E excluding the root node O S,e

1 n and the leaves L e , that the

ummation of the value of its children is the same as the sum-

ation of the value of its parents. Constraints (8) can be seen as

ow conservation equations where or-nodes O π ,e dl

represent “tran-

ition nodes”. The constraints for those transition nodes guarantee

hat if m caregivers of type e are allocated to the productions gen-

rating the subsequence associated with node O π ,e dl

, those m care-

ivers have to be distributed along all the possible ways to use π o generate a sequence of length l from position d ( ch (O π ,e

dl ) ). Con-

ider the following example using the DAG � from Fig. 1 . Assume

hat three caregivers are assigned to and-node A W → W W, 1 22

(r epr e-

ented by variable v W → W W, 1 22

) and that one employee is assigned

o and-node A W → W W, 1 12

(represented by variable v W → W W, 1 12

). Since

hese two and-nodes have one child in common (i.e. or-node O W 21

)

he number of employees allocated to O W 21

is four. Now, since or-

ode O W 21

has one child ( A W → w, 1 21

) these four employees must be

llocated to a working shift during day 2.

The expected recourse function Q (y ) is denoted by Q (y ) ≡ ξ [ Q (y , ξ )] . The recourse function Q (y , ξd (w )) for a given realiza-

ion w of ξ and fixed values for the allocation of caregivers to shifts nd days-off ( ̄y e

ds , ȳ e

d−1 r , ȳ e dr

, and ȳ e d+1 r ) is represented by:

in ∑ e ∈ E

∑ s ∈ S

∑ c ∈ C

t e dsc

x e (w ) dsc

+ ∑ e ∈ E

∑ s ∈ S

r e ds

z e (w ) ds

+ ∑ s ∈ S

∑ c ∈ C

( c +

dsc s +(w ) dsc

+ c − dsc

s −(w ) dsc

) (13)

∑ c ∈ C

δe sc x e (w ) dsc

= (z e (w ) ds

+ ȳ e ds

) , ∀ s ∈ S, e ∈ E, (14)

∑ s ∈ S

z e (w ) ds

≤ ȳ e d−1 r , ∀ e ∈ E, (15)

∑ s ∈ S

z e (w ) ds

≤ ȳ e dr

, ∀ e ∈ E, (16)

∑ s ∈ S

z e (w ) ds

≤ ȳ e d+1 r , ∀ e ∈ E, (17)

∑ e ∈ E

κ e dsc

x e (w ) dsc

− s +(w ) dsc

+ s −(w ) dsc

= b (w ) dsc

, ∀ s ∈ S, c ∈ C, (18)

e (w ) dsc

≥ 0 and integer , ∀ e ∈ E, s ∈ S, c ∈ C, (19)

e (w ) ds

≥ 0 and integer , ∀ e ∈ E, s ∈ S, (20)

+(w ) dsc

, s −(w ) dsc

≥ 0 , ∀ s ∈ S, c ∈ C. (21)

8 M.I. Restrepo, L.-M. Rousseau and J. Vallée / Omega 95 (2020) 102057

4

Table 3

Costs and capacity values for each type of shift.

Parameter Shift

m 8 m 4 a 4 n 10

Shift allocation cost c e ds

($) 8 4 4 10

Under-covering cost c − dsc

($) 40 40 20 100

Over-covering cost c + dsc

($) 2 2 1 5

Capacity κ e ds

(number of visits) 2 1 2 1

Max_days 6 4 4 3

Table 4

District compatibilities.

District District

d 0 d 1 d 2 d 3

d 0 1 0 0 0

d 1 0 1 1 0

d 2 0 1 1 1

d 3 0 0 1 1

The objective of model (13) –(21) is to minimize the realloca-

tion costs, the costs of contacting caregivers to work on a day-

off, and the penalization for demand over-covering and under-

covering. Constraints (14) define the reallocation of caregivers of

type e ∈ E working on shift s ∈ S to compatible districts. Constraints (15) –(17) set the valid conditions to contact caregivers to work on

a day-off. That is, if an employee is having three days-off in a row

only the day-off in the middle of the rest stretch can be assigned

to a working shift. Constraints (18) ensure that the total number

of caregivers working on day d ∈ D , shift s ∈ S , and district c ∈ C is equal to the demand subject to some adjustments related to de-

mand under-covering and over-covering. Constraints (19) –(21) set

the non-negativity and integrality of variables x e (w ) dsc

and z e (w ) ds

, and

the non-negativity of variables s +(w ) dsc

and s −(w ) dsc

.

Since we assumed that the number of visits per day, per shift,

and per district is a random variable with finite support, where

�d is the set of scenarios for the demand at each day and p (w ) d

> 0

is the probability of occurrence of scenario w ∈ �d , the expected recourse function Q (y ) can be expressed as:

Q (y ) ≡ ∑ d ∈ D

E ξ [ Q (y , ξd )] ≡ ∑ d ∈ D

∑ w ∈ �d

p (w ) d

Q (y , ξd (w )) (22)

With this result, recourse functions (13) –(21) can be incorpo-

rated in (4) –(12) to obtain an deterministic equivalent problem given

by:

f (Z) = min ∑ d ∈ D

∑ s ∈ S

∑ e ∈ E

c e ds

y e ds

+ ∑ d ∈ D

∑ e ∈ E

∑ A ,k,e

dl ∈ A e

c ,k,e dl

v ,k,e dl

+

∑ d ∈ D

∑ w ∈ �d

p (w ) d

( ∑ e ∈ E

∑ s ∈ S

∑ c ∈ C

t e dsc

x e (w ) dsc

+ ∑ e ∈ E

∑ s ∈ S

r e ds

z e (w ) ds

)

∑ d ∈ D

∑ w ∈ �d

p (w ) d

( ∑ s ∈ S

∑ c ∈ C

c + dsc

s +(w ) dsc

+ c − dsc

s −(w ) dsc

)

(5) − (12) and (14) − (21) , ∀ d ∈ D, w ∈ �d .

Observe that model Z could involve a large number of variables and constraints, especially when the number of days in the plan-

ning horizon is large. However, since context-free grammars allow

to handle multiple shift types and to represent complex work reg-

ulations in an implicit (compact) way, and since the size of the

model does not depend on the number of caregivers to hire at each

district, model Z can be efficiently solved for large instances with- out the need of decomposition methods.

4. Computational experiments

In this section, we test the proposed approach on real-world in-

stances from a home healthcare agency working with AlayaCare.

First, we present information related to the agency’s operations

and to the rules for schedule generation. Second, we describe the

procedure adopted for the generation of the instances and present

the size of these instances. Third, we report and analyze the com-

putational results and present a discussion on the practical aspects

and managerial insights of the proposed approach.

The computational experiments were performed on a Linux op-

erating system, 16 GB of RAM and 1 processor Intel Xeon X5675

running at 3.07GHz. The algorithm to solve the problem was im-

plemented in C ++ . The deterministic equivalent problem Z was solved with CPLEX version 12.7.0.0. The time limit to solve each

instance is proportional to the length of the planning horizon. For

example, if a given instance is defined over 4 weeks, the time limit

is set to 2 h. Similarly, if a given instance is defined over 12 weeks,

the time limit is set to 6 h. A relative gap tolerance of 0.01 was set

as a stopping criterion for solving the MILPs with CPLEX.

.1. Operations and schedule generation

• Operations: The test instances are generated based on 8-month

historical data from operations of one private agency operating

in Greater Toronto Area. This region is divided into four dis-

tricts (i.e. | C| = 4 ). The agency operates in these districts 24 h per day from Monday to Sunday. We only consider the staffing

and scheduling of personal support workers, as they represent

the largest portion of employees in the agency (70% of the total

number of caregivers). Based on the agency’s operations we de-

fined four types of shifts: morning shifts of type 1 (denoted as

m 8 ) starting at 7:00 with an 8-h length; morning shifts of type

2 (denoted as m 4 ) starting at 10:00 with a 4-h length; after-

noon shifts (denoted as a 4 ) starting at 14:00 with a 4-h length;

and night shifts (denoted as n 10 ) starting at 18:00 with a 10-

h length. We assume that the base cost of each working time

interval is 1$ and that the shift allocation cost depends on the

shift length, as well as on the day covered (weekend shifts are

more expensive than weekday shifts). Because one of the ob-

jectives of the agency is to increase the service level, demand

under-covering costs are set to a large value equal to the cost of

each visit ( c e ds

/ κ e ds

) multiplied by 10. Similarly, the costs for the

demand over-covering are equivalent to the cost of each visit

( c e ds

/ κ e ds

) multiplied by 0.5. The values for these costs, for the

capacities of shifts, as well as other parameters characterizing

each type of shift, are presented in Table 3 . Observe that the

costs presented in this table do not consider a 20% surcharge

for weekend days. In addition, the cost of contacting a care-

giver to work on a day-off is r e ds

= c e ds

∗ 2 , the surcharge for al- lowing transitions between districts is t e

dsc = 10% , and the tran-

sition costs between forbidden shifts is equal to c ,k,e dl

= 10 0 0 $. The compatibilities between districts are presented in Table 4 .

• Schedule composition: The work regulations for the schedule

composition are the following

1. The minimum and the maximum number of days in each

work stretch are 4 and 6, respectively.

2. The minimum and the maximum number of days in each

rest stretch are 1 and 3, respectively.

3. A rest stretch is necessary between two work stretches.

4. Each shift has a maximum number of consecutive times it

can appear in a work sequence. These values are presented

in row Max_days of Table 3 . For instance, a work stretch

cannot contain more than 3 night shifts in a row. • Grammar: Let w s be a terminal symbol that defines working

on shift s ∈ S . Let r be a terminal symbol that represents a rest

M.I. Restrepo, L.-M. Rousseau and J. Vallée / Omega 95 (2020) 102057 9

Table 5

Instances size.

Instance

I1 (4 weeks) I2 (8 weeks) I3 (12 weeks)

Or-nodes 1,551 3,102 6,204

And-nodes 3,614 7,228 14,456

Leaves 140 280 560

First-stage constraints 6,208 12,416 24,832

Second-stage constraints 305,0 0 0 610,0 0 0 1,120,0 0 0

First-stage integer variables 15,016 30,032 60,064

Second-stage integer variables 560,0 0 0 1,120,0 0 0 2,240,0 0 0

Second-stage continuous variables 224,0 0 0 448,0 0 0 896,0 0 0

Table 6

Costs on stochastic instances for different number of scenarios.

Instance Scen. Realloc. RestToW Status Real.C ($) Recour.C ($) %I.Real.C %I.Recour.C

I1 5 1 1 Optimal 1,679.6 2,297.34 14.63% 28.45%

I1 25 1 1 Optimal 1,505.8 1,807.29 2.77% 1.05%

I1 100 1 1 Optimal 1,464.6 1,801.97 -0.04% 0.75%

I1 150 1 1 Optimal 1,508.6 1,800.15 2.96% 0.65%

I1 200 1 1 Optimal 1,638.8 1,827.56 11.85% 2.18%

I1 250 1 1 Optimal 1,506.8 1,824.26 2.84% 2.0%

I1 300 1 1 Optimal 1,428 1,794.67 -2.54% 0.34%

I1 350 1 1 Optimal 1,567 1,835.46 6.95% 2.62%

I1 400 1 1 Optimal 1,503.8 1,827.55 2.63% 2.18%

I1 450 1 1 Optimal 1,465.2 1,788.53 0.0% 0.0%

I2 5 1 1 Optimal 3,829 4,048.22 24.77% 11.92%

I2 25 1 1 Optimal 3,106 3,832.19 1.21% 5.95%

I2 50 1 1 Optimal 3,212 3,786.17 4.67% 4.67%

I2 100 1 1 Optimal 3,100.8 3,685.55 1.04% 1.89%

I2 150 1 1 Optimal 3,062.2 3,618.67 -0.22% 0.04%

I2 200 1 1 Optimal 3,068.8 3,617.14 0% 0.0%

I3 5 1 1 Optimal 6,187.4 6,315.87 6.68% 9.18%

I3 25 1 1 Optimal 5,904.4 5,827.59 1.8% 0.74%

I3 50 1 1 Optimal 5,800 5,784.86 0% 0%

4

w

t

d

e

n

e

v

s

m

e

w

n

u

o

d

i

w

o

a

w

T

i

t

t

p

t

r

i

a

i

a

R

t

period. Let F and R be non-terminal symbols representing work

and rest stretches, respectively. Let s u be the maximum num-

ber of consecutive times shift s can appear in a work sequence.

In productions ∈ P, c tr → [min, max] restricts the subsequences generated by a given production to a length between a mini-

mum and a maximum number of days, and ctr denotes a cost

associated with the production. The grammar and the produc-

tions that define valid schedules for caregivers of type e ∈ E dur- ing a planning horizon of four weeks are as follows:

G e = (� = (w s ∀ s ∈ S, r) , N = (S, F , H, J s , J ′ s , J 2 s , J 3 s ∀ s ∈ S, R ) , P, S) , S [28 , 28] → RH R | RH | H R, H → F RF RF RF , F [4 , 6]

c tr → J s J ′ s , ∀ s ∈ S; F [4 , 6] → J 2 s J 3 s , ∀ s ∈ S, J ′ s

c tr → J s ′ J ′ s ′ , ∀ s ∈ S, ∀ s ′ ∈ S\{ s }; J ′ s → J 2 s ′ J 3 s ′ , ∀ s ∈ S, ∀ s ′ ∈ S\{ s }; J s [0 ,s u ] → J 2 s J 3 s , ∀ s ∈ S, J 2 s → J 2 s J 3 s , ∀ s ∈ S; J 3 s → w s , ∀ s ∈ S; R [1 , 3] → rR ; R → r.

.2. Instances generation and size of problems

Three instances spanning planning horizons from 4 to 12

eeks and including 500 demand scenarios were generated to

est our model. These instances were built with the proce-

ures presented in Sections 3.1.1 and 3.1.2 . Table 5 presents for

ach instance (denoted as I1, I2, and I3), the number of or-

odes, the number of and-nodes, and the number of leaves in

ach DAG �e , ∀ e ∈ E . This table also presents the number of ariables and the number of constraints for the first-stage and

econd-stage components of model Z. Note that the size of the odel is not proportional to the number of caregivers, as the

mployee dimension is included in the model in an implicit

ay.

Since the size and complexity of problem Z increase with the umber of scenarios, we decided to perform an analysis to eval-

ate how staffing and scheduling decisions (including a fraction

f the scenarios) accommodate the real demand, and how these

ecisions react when they are evaluated on all generated scenar-

os (500). Specifically, for each instance we first solve problem Z ith a fraction of the scenarios (e.g., 50 out of 500) to get the

ptimal solution for variables y e ds

and y e dr

. These optimal values

re fixed in second-stage problems (13) –(21) , which are solved

ith the actual demand information and with all 500 scenarios.

able 6 presents the results for this evaluation on problem Z ncluding the reallocation of caregivers (Realloc. = 1) and con- acting caregivers to work on a day-off (RestToW = 1). For each ype of instance (Instance) and number of scenarios (Scen.), we

resent the status of the solution (Status), the recourse cost when

he schedule is evaluated with the real demand (Real.C), and the

ecourse cost when the schedule is evaluated with 500 scenar-

os (Recour.C). The percentage increase in these two costs (Real.C

nd Recour.C) by using a fraction of the scenarios is presented

n columns %I.Real.C and %I.Recour.C. This percentage is computed

s: % I = 100 × Cost − base _ cost base _ cost

, where Cost represents the value for

eal.C and Recour.C, and base _ cost denotes the recourse cost ob-

ained after solving problem Z with the largest possible number of

10 M.I. Restrepo, L.-M. Rousseau and J. Vallée / Omega 95 (2020) 102057

Table 7

Computational effort and results on stochastic instances.

Instance Scen. Realloc. RestToW Time (s) Status Total.C ($) Caregivers

d 0 d 1 d 2 d 3 Total

I1 300 0 0 8.04 Optimal 12,858.8 4 43 6 22 75

I1 300 1 0 418.45 Optimal 11,773.5 4 39 13 15 71

I1 300 0 1 166.78 Optimal 11,528.5 4 39 5 20 68

I1 300 1 1 1,121.53 Optimal 10,843 4 37 11 17 69

I2 150 0 0 53.54 Optimal 24,990.7 4 43 6 21 74

I2 150 1 0 1,876.03 Optimal 22,620.7 4 38 13 14 69

I2 150 0 1 675.45 Optimal 21,441.6 3 38 5 17 63

I2 150 1 1 5,212.85 Optimal 20,116.4 4 35 11 14 64

I3 50 0 0 1,139.62 Optimal 35,995.5 4 34 6 17 61

I3 50 1 0 10,522.7 Optimal 32,341.8 4 30 11 13 58

I3 50 0 1 2,799.27 Optimal 30,033.5 3 30 6 16 55

I3 50 1 1 11,983.2 Optimal 27,805.5 3 27 10 12 52

I

m

o

4

o

m

a

t

r

c

p

i

a

s

b

n

i

w

a

r

c

w

u

V

a

s

c

w

w

a

d

4

e

p

t

p

a

a

a

w

i

scenarios (300 for I1 instances, 125 for I2 instances, and 25 for I3

instances).

To choose the number of scenarios that will be used in each

instance we observed the values for the percentage differences in

the recourse costs (%I.Recour.C). Since these differences are smaller

than 0.5% for 300 scenarios for instances I1 and for 150 scenar-

ios for instances I2, we decided to set | �d | = 300 for I1 and to set | �d | = 150 for I2. Regarding instances I3, we set | �d | to 50 as the expected recourse cost (Recour.C) was smaller than the value

of Recour.C for the other number of scenarios (5 and 25), and as

the model was not able to solve instances with a larger number of

scenarios.

4.3. Computational results

In this section, we present the computational results after test-

ing our model on real-world instances. First, we present the perfor-

mance of the proposed model for different planning horizons. Sec-

ond, we introduce an example to illustrate an output of the prob-

lem. Third, we analyze the impact of the type of recourse actions

used in the costs and number of caregivers staffed. An analysis of

the impact of schedule flexibility in the costs and number of care-

givers staffed is presented at the end of this section.

Table 7 presents for each instance and each combination of re-

course actions allowing caregiver reallocation (Realloc.) and work-

ing on a day-off (RestToW), the CPU time in seconds to solve the

problem (Time), the status of the solution (Status), the total cost

(Total.C), and the total number of caregivers to hire in each dis-

trict.

Results from Table 7 indicate that the computational effort in-

creases with the length of the planning horizon, as well as with

the flexibility related to the recourse actions. Observe that it was

possible to find an optimal solution for all instances. We can con-

clude that the recourse action that contributes the most to an in-

crease in the CPU time is allowing the reallocation of caregivers

(Realloc. = 1). Specifically, for instances I1, I2, and I3 and when Realloc. = 1 CPLEX was respectively 52, 35 and 10 times slower to solve the model when compared to solving the model with sim-

ple recourse, i.e. Realloc = 0 and RestToW = 0. When the recourse RestToW is included in the model (contact caregivers to work on a

day-off), these values increase to 140, 97, and 10 for instances I1,

I2, and I3, respectively.

Results on staff dimensioning suggest that the number of care-

givers to hire in districts d 0 , d 2 , and d 3 is very similar for instances

spanning different planning horizons. However, for districts d 1 and

d 3 we can observe some significative differences in the number of

caregivers to hire (e.g., 27 caregivers for d 0 in instance I3 when Re-

alloc = 1 and RestToW = 1 versus 37 caregivers for d in instance

0

1 when Realloc = 1 and RestToW = 1). We remark that this result ight be due to forecasting errors and changes in the magnitude

f demands from one month to the other one.

.4. Example 2: Output illustration

Tables 8 and 9 present an example of the schedules and the use

f recourse actions after solving the two-stage stochastic program-

ing model on an instance including a 4-week planning horizon

nd 10 scenarios. This example incorporates the use of recourse ac-

ions associated with under-covering, with over-covering, with the

eallocation of caregivers to neighbor districts, and with contacting

aregivers to work on a day-off. Table 8 shows four schedules (one

er district) including the shift and day-off allocation at each day

n the planning horizon. Recall that r represents the allocation of

day-off and that m 4 , m 8 , a 4 , and n 10 denote different types of

hifts. For instance, a caregiver hired to work in district 3 ( d 3 ) will

e allocated in the week from 2017-07-24 to 2017-07-30 to after-

oon shifts ( a 4 ) in the first 2 days of the week; then he will work

n the next 2 days in night shifts ( n 10 ); the caregiver will finish the

eek with 3 consecutive days-off (r).

The shift and day-off allocation of the schedule for d 3 is used

s an example to show the use of recourse actions related to the

eallocation of caregivers to neighbor districts, and with contacting

aregivers to work on a day-off. Table 9 shows for each day of the

eek from 2017-07-24 to 2017-07-30 the changes in the sched-

les due to the recourse actions used for 10 demand scenarios.

alues in bold indicate that a recourse action was used to protect

gainst uncertainty. For instance, during day 2017-07-24 and under

cenario 10 the model decided to include a district reallocation (a

aregiver from district d 3 is reallocated to district d 1 ). In a similar

ay, during day 2017-07-29 the model chose to use the recourse

ork on a day-off for scenarios 2, 7, 9, and 10 (e.g., in scenario 2,

caregiver is called to work in his day-off in a morning shift in

istrict 3 ( m 4 _ d 3 )).

.5. Assessing the impact of different recourse actions

In this section, we perform a comparison among the differ-

nt types of recourse actions used in the two-stage stochastic

rogramming model. The impact of allowing caregiver realloca-

ion and working on a day-off is evaluated. Table 10 reports the

ercentage difference in the total cost (%D.Total.C), the percent-

ge difference in the scheduling cost (%D.Sched.C), the percent-

ge difference in the recourse cost (%D.Recour.C), and the percent-

ge difference in the total number of caregivers staffed (%D.Staff)

hen flexibility regarding the use of different recourse actions is

ntroduced in the model. These percentage differences are com-

M.I. Restrepo, L.-M. Rousseau and J. Vallée / Omega 95 (2020) 102057 11

Table 8

Example of the schedules obtained with the two-stage stochastic programming model.

district Date

2017-07-03 2017-07-04 2017-07-05 2017-07-06 2017-07-07 2017-07-08 2017-07-09

d 0 m 8 _ d 0 m 8 _ d 0 m 8 _ d 0 m 4 _ d 0 m 4 _ d 0 r m 8 _ d 0 d 1 m 4 _ d 1 m 4 _ d 1 m 4 _ d 1 m 8 _ d 1 m 8 _ d 1 r r

d 2 r r r m 4 _ d 2 m 4 _ d 2 n 10 _ d 2 n 10 _ d 2 d 3 m 4 _ d 3 m 4 _ d 3 a 4 _ d 3 a 4 _ d 3 r r r

2017-07-10 2017-07-11 2017-07-12 2017-07-13 2017-07-14 2017-07-15 2017-07-16

d 0 m 8 _ d 0 n 10 _ d 0 n 10 _ d 0 r r r m 8 _ d 0 d 1 r m 4 _ d 1 m 4 _ d 1 m 8 _ d 1 m 8 _ d 1 r r

d 2 r r r m 8 _ d 2 m 8 _ d 2 n 10 _ d 2 n 10 _ d 2 d 3 a 4 _ d 3 a 4 _ d 3 n 10 _ d 3 n 10 _ d 3 r r r

2017-07-17 2017-07-18 2017-07-19 2017-07-20 2017-07-21 2017-07-22 2017-07-23

d 0 m 8 _ d 0 n 10 _ d 0 n 10 _ d 0 r r r m 8 _ d 0 d 1 r m 4 _ d 1 m 4 _ d 1 m 8 _ d 1 m 8 _ d 1 r r

d 2 n 10 _ d 2 r r r m 4 _ d 2 m 4 _ d 2 n 10 _ d 2 d 3 m 8 _ d 3 m 8 _ d 3 n 10 _ d 3 n 10 _ d 3 r r r

2017-07-24 2017-07-25 2017-07-26 2017-07-27 2017-07-28 2017-07-29 2017-07-30

d 0 m 8 _ d 0 m 8 _ d 0 n 10 _ d 0 n 10 _ d 0 r r r

d 1 r m 8 _ d 1 m 8 _ d 1 m 8 _ d 1 a 4 _ d 1 a 4 _ d 1 r

d 2 n 10 _ d 2 r m 4 _ d 2 m 4 _ d 2 m 4 _ d 2 m 8 _ d 2 m 8 _ d 2 d 3 a 4 _ d 3 a 4 _ d 3 n 10 _ d 3 n 10 _ d 3 r r r

Table 9

Illustration on the use of recourse actions in a schedule of a caregiver working in d 3 .

Date

2017-07-24 2017-07-25 2017-07-26 2017-07-27 2017-07-28 2017-07-29 2017-07-30

Master schedule a 4 _ d 3 a 4 _ d 3 n 10 _ d 3 n 10 _ d 3 r r r

Scen. 1 a 4 _ d 3 a 4 _ d 3 n 10 _ d 3 n 10 _ d 3 r r r

Scen. 2 a 4 _ d 3 a 4 _ d 3 n 10 _ d 3 n 10 _ d 3 r m 4 _ d 3 r

Scen. 3 a 4 _ d 3 a 4 _ d 3 n 10 _ d 3 n 10 _ d 3 r r r

Scen. 4 a 4 _ d 3 a 4 _ d 3 n 10 _ d 3 n 10 _ d 3 r r r

Scen. 5 a 4 _ d 3 a 4 _ d 3 n 10 _ d 3 n 10 _ d 3 r r r

Scen. 6 a 4 _ d 3 a 4 _ d 3 n 10 _ d 3 n 10 _ d 3 r r r

Scen. 7 a 4 _ d 3 a 4 _ d 3 n 10 _ d 3 n 10 _ d 3 r a 4 _ d 3 r

Scen. 8 a 4 _ d 3 a 4 _ d 3 n 10 _ d 3 n 10 _ d 3 r r r

Scen. 9 a 4 _ d 3 a 4 _ d 3 n 10 _ d 3 n 10 _ d 3 r a 4 _ d 3 r

Scen. 10 a 4 _ d 1 a 4 _ d 3 n 10 _ d 3 n 10 _ d 3 r n 10 _ d 3 r

Table 10

Impact of the type of recourse action used in the costs and number of caregivers staffed.

Instance Scen. Realloc. RestToW %D.Total.C %D.Sched.C %D.Recour.C %D.Staff

I1 300 1 0 −8.44% −5.35% −21.17% −5.33% I1 300 0 1 −10.35% −12.7% −0.65% −9.33% I1 300 1 1 −15.68% −12.87% −27.22% −8% I2 150 1 0 −9.48% −6% −23.03% −6.76% I2 150 0 1 −14.2% −17.84% −0.03% −14.86% I2 150 1 1 −19.5% −17.36% −27.85% −13.51% I3 50 1 0 −10.15% −6.16% −24.73% −4.92% I3 50 0 1 −16.56% −18.91% −7.99% −9.84% I3 50 1 1 −22.75% −20.5% −25.26% −14.75%

p

s

r

b

s

s

p

u

c

a

i

c

t

z

T

w

t

l

s

uted as % D = 100 × (V alue − base _ v alue ) /base _ v alue . Value repre- ents the final value for the total cost, for the staffing cost, for the

ecourse cost, and for the total number of caregivers staffed, and

ase _ v alue denotes the value for the same attribute obtained after olving problem Z (on each instance I1, I2, and I3) with the base cenario. Since the base scenario corresponds to the use of sim-

le recourse in the second-stage model (i.e. only allowing demand

nder-covering and over-covering) the differences in the recourse

osts are mainly due to the reduction in demand under-covering

nd over-covering costs.

Results from Table 10 suggest that the introduction of flexibil-

ty in the use of recourse actions significantly reduces the total

osts, as well as the number of caregivers staffed. These reduc-

ions appear to be larger for instances spanning planning hori-

ons of 8 weeks or longer, than for instances spanning 4 weeks.

he recourse action with larger impact is contact caregivers to

ork on a day −off. When this recourse action is integrated with he reallocation of caregivers, the reductions in costs become even

arger. Solving an integrated problem including all districts in-

tead of solving independent problems for each district generates

12 M.I. Restrepo, L.-M. Rousseau and J. Vallée / Omega 95 (2020) 102057

Table 11

Impact of schedule flexibility in the costs and number of caregivers staffed.

Instance Scen. Realloc. RestToW Time (s) Total.C ($) Total.Staff

Flex No.Flex Flex No.Flex Flex No.Flex

I2 150 0 0 53.54 12.36 24,990.7 25,879.5 74 71

I2 150 1 0 1,876.03 1,397.98 22,620.7 23,583 69 67

I2 150 0 1 675.45 547.97 21,441.6 22,344.3 63 62

I2 150 1 1 5,212.85 3,442.57 20,116.4 20,858.4 64 58

I3 50 0 0 1,139.62 14.6 35,995.5 40,120.3 61 70

I3 50 1 0 10,522.7 704.88 32,341.8 36,155 58 69

I3 50 0 1 2,799.27 533.79 30,033.5 33,006.6 55 57

I3 50 1 1 11,983.2 2,668.15 27,805.5 30,678.8 52 54

Table 12

Computational effort and results for the stochastic and deterministic models.

Instance Scen. Realloc. RestToW Stochastic Deterministic

Time(s) Real.C ($) Time (s) Real.C ($)

I1 300 0 0 8.04 13,102.2 2.73 12,765.6

I1 300 1 0 418.45 11,831 8.78 12,174.68

I1 300 0 1 166.78 11,158.4 2.32 11,431.8

I1 300 1 1 1,121.53 10,478.68 9.77 10,981.48

I2 150 0 0 53.54 24,947.6 34.59 28,810.4

I2 150 1 0 1,876.03 22,464.72 218.16 25,952.68

I2 150 0 1 675.45 20,635 48.18 22,148.8

I2 150 1 1 5,212.85 19,587.2 217.29 21,157.92

I3 50 0 0 1,139.62 37,509.2 575.7 45,786.8

I3 50 1 0 10,522.7 32,884.12 8706.94 40,853

I3 50 0 1 2,799.27 30,655.2 577.08 31,873

I3 50 1 1 11,983.2 28,262.8 5144.16 30,706.6

s

w

c

t

u

t

t

t

c

l

h

4

g

t

s

r

r

p

e

E

c

l

a

m

t

m

b

a

m

s

a supplementary cost reduction, as well as an improvement in

caregivers’ utilization. In particular, allowing reallocation of care-

givers to neighbor districts gives planners the flexibility to occa-

sionally use resources from other districts to respond to changes in

demands.

4.6. Assessing the impact of schedule flexibility

Since the two-stage stochastic programming problem becomes

harder to solve with the length of the planning horizon, we per-

form an analysis of the impact of reducing schedule flexibility.

Specifically, for instances including more than 4 weeks (I2 and I3),

we solve the two-stage stochastic programming problem by impos-

ing schedules starting at week 5 to be exactly the same as sched-

ules from the previous 4 weeks. For instance, in a problem with

an 8-week planning horizon, the schedules in week 5 must be the

same as the schedules for week 1, the schedules in week 6 must

be the same as the schedules for week 2, and so on.

Table 11 reports the analysis of the impact of schedule flexibil-

ity in the computational effort and results of model Z. In particu- lar, this table presents a comparison of the CPU times in seconds

(Time (s)), of the total costs (Total.C), and of the number of care-

givers staffed (Total.Staff) when schedules are completely flexible

(Flex.) and when the scheduling flexibility is reduced (No.Flex) as

explained above.

Results from Table 11 indicate that the method is in average 14

times faster when flexibility in the allocation of schedules is lim-

ited. This speed-up is more substantial for instances with type I3

as a longer time horizon is being considered. Observe that the total

cost presents an increase when there is less flexibility associated

with the allocation of schedules, as the two-stage model has less

freedom to use recourse actions when needed. However, the num-

ber of caregivers to hire shows a different behavior for instances I2

and I3. Specifically, in I2 instances the value of Total.Staff becomes

maller when the schedule flexibility is reduced. On the contrary,

hen the schedule flexibility is reduced, the value of Total.Staff be-

omes larger for instances I3. This might be explained by the fact

hat for short time horizons (8 weeks), the model with less sched-

le flexibility (No.Flex) decides to hire fewer employees (even if

his means to have some extra under-covering) in order to reduce

he employee underutilization (visits over-covering). On the con-

rary, for longer time horizons (12 weeks) the No.Flex model de-

ides to hire more employees as this restriction in the schedule al-

ocation might significantly increase the visits under-covering and

ence the total costs.

.7. Value of the stochastic solution

The VSS is a standard measure that indicates the expected

ain from solving a stochastic model rather than its determinis-

ic counterpart, the expected value problem (EV). The value of the

tochastic solution is defined as V SS = E E V − RP, where RP cor- esponds to the optimal value of problem (4) –(12) and EEV cor-

esponds to the expected value of using the EV solution. EV is

roblem (4) –(12) evaluated using the mean scenario ξ̄d = ˆ b d for ach day d ∈ D . Given an EV solution ( ̄y ∗ ) , EEV corresponds to: E V = ∑ d ∈ D ∑ w ∈ �d p (w ) d Q ( ̄y ∗, ξd (w )) . A large VSS means that un- ertainty is important for the quality of the resulting optimal so-

ution. On the contrary, a small VSS means that a deterministic

pproach based on the expected values of the random variables

ight be sufficiently good to take a decision. The reader is referred

o Birge and Louveaux [6] for an overview of stochastic program-

ing.

Table 12 presents a comparison of the computational effort

etween the two-stage stochastic programming model (denoted

s Stochastic) and the mean value problem (denoted as Deter-

inistic). This effort is measured by the CPU time in seconds to

olve the problem. This table also reports the total cost when the

M.I. Restrepo, L.-M. Rousseau and J. Vallée / Omega 95 (2020) 102057 13

Table 13

Value of the stochastic solution.

Instance Scen. Realloc. RestToW VSS Cost VSS Scheduling VSS Recourse VSS Staff

I1 300 0 0 15.53% −17.62% 60.89% −13.64% I1 300 1 0 14.12% −11.34% 59.68% −5.97% I1 300 0 1 5.61% −2.04% 25.75% −1.49% I1 300 1 1 5.12% −1.74% 28.77% −1.47% I2 150 0 0 16.33% −20.5% 61.8% −17.46% I2 150 1 0 14.62% −13.8% 60.97% −9.52% I2 150 0 1 3.35% 0.86% 10.56% 0.0%

I2 150 1 1 4.27% −0.2% 20.15% −3.23% I3 50 0 0 18.67% −22.81% 63.58% −19.61% I3 50 1 0 17.25% −15.61% 63.92% −13.73% I3 50 0 1 5.34% 0.26% 18.68% −7.84% I3 50 1 1 6.56% 0.64% 24.13% −4%

s

d

d

s

t

c

(

m

m

s

t

t

l

t

e

s

i

d

d

t

r

(

t

w

e

t

c

a

t

w

t

s

c

m

c

a

1

c

O

c

t

t

s

m

4

p

i

c

A

k

s

u

t

c

t

i

c

t

t

c

c

t

s

l

chedules obtained with the stochastic model and with the

eterministic model are evaluated with the actual values for the

emand (Real.C).

Table 13 presents an evaluation of the values of the stochastic

olution. In particular, this table reports the expected gains in the

otal cost ( VSS Cost ), in the scheduling cost ( VSS Scheduling ), in the re-

ourse cost ( VSS Recourse ), and in the quantity of caregivers staffed

VSS Staff) from solving the stochastic model rather than its deter-

inistic counterpart. This evaluation is computed as: VS S i = 100 × ( EE V i − RP i ) / EE V i , for all i = { Cost; Scheduling; Recourse ; Staff} .

Results from Table 12 indicate that the CPU time to solve the

ean value problem is significantly smaller than the CPU time to

olve the stochastic problem. However, when the schedules ob-

ained after solving the deterministic problem are evaluated on

he real demand these schedules perform worse (as the Real.C is

arger in most instances) when compared to the performance of

he schedules obtained with the stochastic problem. The differ-

nces in the real cost between the deterministic model and the

tochastic model are of great importance in practice since Real.C

ndicates how well the caregivers’ schedules react to the actual

emand. Since the majority of values for Real.C are lower when

emand uncertainty is included in the model, we can conclude

hat the schedules obtained with the stochastic model are more

obust than the schedules obtained with the deterministic model

EV problem).

We remark that since the schedules obtained with the stochas-

ic model are usually more robust than the schedules obtained

ith a deterministic model, Real.C is expected to be lower when

valuated with the stochastic schedules than when evaluated with

he deterministic schedules. However, it may happen that in some

ases this is not true. For example, in instance I1 with Realloc. = 0 nd RestToW = 0. In this case, what could have happened was that he actual demand was very similar to the mean demand. Hence,

hen the dimensioning and scheduling decisions obtained with

he deterministic model are evaluated on a single instance corre-

ponding to the actual (observed) demand, Real.C is lower than the

ost obtained with the stochastic model.

Results from Table 13 suggest that the two-stage stochastic

odel can lead to significant reductions in the total cost when

ompared to the mean value problem since all the VSSs associ-

ted with the total cost are positive values ranging from 3.35% to

8.67%. This result is mainly due to a reduction in the recourse

osts associated with demand under-covering and over-covering.

bserve that some instances have negative VSS for the scheduling

osts ( VSS Sched . ) and for the staffing decisions ( VSS Staff). This means

hat the two-stage stochastic model selects a larger workforce

han the deterministic model, resulting in more robust staffing and

cheduling decisions that accommodate better to changes in de-

ands. q

.8. Practical aspects and managerial insights

The methodology developed in this paper represents an im-

ortant and general decision support tool for home care agencies

nterested in staff dimensioning and caregiver scheduling. Specifi-

ally, our computational experiments indicate that:

• The design of robust staffing and scheduling decisions require

the incorporation of uncertainty in demands, as expected costs

are smaller when uncertainty is included. This is explained by

the fact that opposite to deterministic models, the strength of

stochastic programming arises from the ability to represent so-

lutions that protect against multiple possible future outcomes

[5] . Hence, the aptitude to identify solutions that handle or

adapt best to the set of potential outcomes, relative to their

probability of occurring, is expected to generate costs that are

smaller when compared to a deterministic model when evalu-

ated on several possible demand realizations. • Including recourse actions such as allowing caregiver realloca-

tion to neighbor districts and working on a day-off significantly

improves the costs associated with the dimensioning decisions

(staffing), as well as with demand under-covering and over-

covering, resulting in the improvement of caregiver utilization

and quality of service. • Solving an integrated problem including all districts instead of

solving independent problems for each district, generates sup-

plementary cost reductions. In particular, allowing reallocation

of caregivers to neighbor districts gives planners the flexibility

to occasionally use resources from other districts to respond to

changes in the demand or in caregivers’ availabilities.

Even though the case study was done for a specific agency from

layaCare, this agency was selected because it includes most of the

ey features of the considered problem (e.g., stochastic demands,

everal geographic areas, different types of shifts, several work reg-

lations for the composition of schedules). Therefore, we believe

hat our study is general and that the conclusions drawn from the

omputational experiments can be similar if the methodology is

ested in other practical cases.

The proposed model could be useful to evaluate the impact

n costs and in the quality of solutions by using different re-

ourse actions. Specifically, recourse actions including the alloca-

ion of overtime and the use of part-time caregivers could be

ested to evaluate if an increase in recourse flexibility helps to de-

rease the scheduling costs and demand under-covering and over-

overing costs. The model could also be used as a tool to detect

he lack/excess of caregivers due to changes in demand. For in-

tance, given a fixed number of caregivers, the model will incur

arge under-covering costs if the size of the workforce is inade-

uate to satisfy all patient visits when demand increases. On the

14 M.I. Restrepo, L.-M. Rousseau and J. Vallée / Omega 95 (2020) 102057

A

w

a

d

c

a

S

f

R

[

[

[

[

contrary, the solutions of the model will return large over-staffing

costs if the size of the permanent workforce is too large for the

demand. Moreover, the two-stage stochastic programming model

could be extended to incorporate multiple types of caregivers with

different skills, and to include information about current employ-

ees with their preferences and availabilities.

Regarding the computational effort and limits of the two-stage

stochastic programming model, computational experiments indi-

cate that the CPU time increases with the length of the planning

horizon, with the number of scenarios, and with the flexibility in

recourse actions. For each type of instances tested, we observed

that the most important factor in this computational time increase

was the value of RestToW (i.e. contact caregivers to work on their

day-off) since problem Z was in average 100 times slower when RestToW was set to 1. We also observed that the computational

time required to solve the problems can be reduced by 5 times

on average by limiting the schedule allocation flexibility. One idea

to deal with the computational limits of the method on larger

planning horizons could be to use a rolling horizon approach. In

this way, the complexity of the problem will be reduced as this

method will gradually move along the planning horizon to incor-

porate stochastic information of the demand.

The work presented in this paper has some limitations that

could be addressed in future work. These limitations are mainly

related to the assumptions adopted to facilitate the modeling and

solution of the problem under study. For instance, assuming that

the duration of patients’ visits and travel times are deterministic

parameters could lead to suboptimal solutions, especially if care-

givers perform several short visits within one day and the variabil-

ity in these times is large. In the case of AlayaCare, this variability

does not affect significantly the solution of the problem, as most

of the caregivers are personal support workers that perform long

visits during their shift. In addition, the practical use of the work

presented in this paper can be affected by assuming that caregivers

will accept to work when called during their day-off, since from

time to time caregivers are free to reject this type of request from

their employer. Moreover, in a home care setting where caregiver

absenteeism rates are high, assuming that the workforce capacity

is deterministic could lead to problems in the implementation of

the solutions obtained. The last limitation of this work is related to

the demand forecasting methods used, as other techniques could

be explored to predict the demand in a more accurate way.

5. Concluding remarks

We presented a two-stage stochastic programming model for

integrated staffing and scheduling in home healthcare. In this

model, first-stage decisions correspond to staff dimensioning and

to the allocation caregivers to schedules. Second-stage decisions

are related to the temporary reallocation of caregivers to neigh-

bor districts, to contact caregivers to work on their day-off, and

to allow under-covering and over-covering. Results on real-world

instances show that the use of the two-stage stochastic program-

ming model helps to reduce demand under-covering and over-

covering costs when compared to a deterministic approach using

the mean demand. Moreover, computational results indicate that

the use of flexible recourse actions significantly reduces the to-

tal costs, improves caregiver utilization, and increases the level of

service.

An interesting avenue for future research is related to the devel-

opment of specialized solution methods to tackle larger instances

commonly found in practice. Future research could also include the

use of different techniques for demand forecasting and for scenario

generation to assess the impact of demand estimation accuracy in

the solutions obtained with the two-stage stochastic programming

problem.

cknowledgments

The authors would like to thank MEDTEQ which supported this

ork a grant. The authors would also like to thank the data team

t AlayaCare for their support in getting access to anonymized

ata. We also thank the two anonymous referees and the Asso-

iate Editor for their insightful comments and suggestions which

llowed us to improve the paper.

upplementary material

Supplementary material associated with this article can be

ound, in the online version, at doi: 10.1016/j.omega.2019.03.015 .

eferences

[1] Argiento R , Guglielmi A , Lanzarone E , Nawajah I . A Bayesian framework for de-

scribing and predicting the stochastic demand of home care patients. Flexible Serv Manuf J 2016;28(1–2):254–79 .

[2] Bachouch RB , Guinet A , Hajri-Gabouj S . A decision-making tool for home health care nurses’ planning. In: Supply chain forum: an international journal,

12. Taylor & Francis; 2011. p. 14–20 . [3] Bennett AR , Erera AL . Dynamic periodic fixed appointment scheduling for

home health. IIE Trans Healthcare Syst Eng 2011;1(1):6–19 .

[4] Bertsimas D , Sim M . The price of robustness. Oper Res 2004;52(1):35–53 . [5] Birge JR . Models and model value in stochastic programming. Ann Oper Res

1995;59(1):1–18 . [6] Birge JR , Louveaux F . Introduction to stochastic programming. Springer Science

& Business Media; 2011 . [7] Boyer V , Gendron B , Rousseau L-M . A branch-and-price algorithm for

the multi-activity multi-task shift scheduling problem. J Scheduling 2012;17(2):185–97 .

[8] Braekers K , Hartl RF , Parragh SN , Tricoire F . A bi-objective home care schedul-

ing problem: analyzing the trade-off between costs and client inconvenience. Eur J Oper Res 2016;248(2):428–43 .

[9] Burke EK , De Causmaecker P , Berghe GV , Van Landeghem H . The state of the art of nurse rostering. JScheduling 2004;7(6):441–99 .

[10] Campbell GM . A two-stage stochastic program for scheduling and allocating cross-trained workers. J Oper Res Soc 2011;62(6):1038–47 .

[11] Cappanera P , Scutellà MG . Joint assignment, scheduling, and routing mod-

els to home care optimization: a pattern-based approach. Transp Sci 2014;49(4):830–52 .

[12] Cappanera P , Scutellà MG , Nervi F , Galli L . Demand uncertainty in robust home care optimization. Omega 2018;80:95–110 .

[13] Carello G , Lanzarone E . A cardinality-constrained robust model for the assign- ment problem in home care services. Eur J Oper Res 2014;236(2):748–62 .

[14] Côté M-C , Gendron B , Rousseau L-M . Grammar-based integer programming

models for multiactivity shift scheduling. Manage Sci 2011;57(1):151–63 . [15] Côté M-C , Gendron B , Rousseau L-M . Grammar-based column genera-

tion for personalized multi-activity shift scheduling. INFORMS J Comput 2013;25(3):461–74 .

[16] Defraeye M , Van Nieuwenhuyse I . Staffing and scheduling under nonstationary demand for service: a literature review. Omega 2016;58:4–25 .

[17] Duque PM , Castro M , Sörensen K , Goos P . Home care service planning. the case

of landelijke thuiszorg. Eur J Oper Res 2015;243(1):292–301 . [18] Fikar C , Hirsch P . Home health care routing and scheduling: a review. Comput

Oper Res 2017;77:86–95 . [19] Garg L , McClean S , Meenan B , Millard P . A non-homogeneous discrete

time markov model for admission scheduling and resource planning in a cost or capacity constrained healthcare system. Health Care Manage Sci

2010;13(2):155–69 .

[20] Harvey AC , Peters S . Estimation procedures for structural time series models. J Forecast 1990;9(2):89–108 .

[21] Hertz A , Lahrichi N . A patient assignment algorithm for home care services. J Oper Res Soc 2009;60(4):481–95 .

22] Hewitt M , Nowak M , Nataraj N . Planning strategies for home health care de- livery. Asia-Pac J Oper Res 2016;33(05):1650041 .

23] Hopcroft JE , Motwani R , Ullman JD . Introduction to automata theory, lan-

guages, and computation. ACM SIGACT News 2001;32(1):60–5 . [24] Hulshof PJ , Kortbeek N , Boucherie RJ , Hans EW , Bakker PJ . Taxonomic classifi-

cation of planning decisions in health care: a structured review of the state of the art in or/ms. Health Syst 2012;1(2):129–75 .

25] Jalalpour M , Gel Y , Levin S . Forecasting demand for health services: develop- ment of a publicly available toolbox. Oper Res Health Care 2015;5:1–9 .

26] Kim K , Mehrotra S . A two-stage stochastic integer programming approach to integrated staffing and scheduling with application to nurse management.

Oper Res 2015;63(6):1431–51 .

[27] Lahrichi N , Lapierre S , Hertz A , Talib A , Bouvier L . Analysis of a territorial ap- proach to the delivery of nursing home care services based on historical data.

J Med Syst 2006;30(4):283–91 . [28] Lanzarone E , Matta A . A cost assignment policy for home care patients. Flexible

Serv Manuf J 2012;24(4):465–95 .

M.I. Restrepo, L.-M. Rousseau and J. Vallée / Omega 95 (2020) 102057 15

[

[

[

[

[

[

[

[

[

[

[

[

29] Lanzarone E , Matta A . Robust nurse-to-patient assignment in home care ser- vices to minimize overtimes under continuity of care. Oper Res Health Care

2014;3(2):48–58 . 30] Lanzarone E , Matta A , Sahin E . Operations management applied to home care

services: the problem of assigning human resources to patients. IEEE Trans Syst ManCybern-Part A 2012;42(6):1346–63 .

[31] Lanzarone E , Matta A , Scaccabarozzi G . A patient stochastic model to support human resource planning in home care. Prod Plann Control 2010;21(1):3–25 .

32] Maenhout B , Vanhoucke M . An integrated nurse staffing and schedul-

ing analysis for longer-term nursing staff allocation problems. Omega 2013;41(2):485–99 .

33] Matta A , Chahed S , Sahin E , Dallery Y . Modelling home care organisa- tions from an operations management perspective. Flexible Serv Manuf J

2014;26(3):295–319 . 34] Nguyen TVL , Toklu NE , Montemanni R . Matheuristic optimization for robust

home health care services. In: Proc. ICAOR; 2015. p. 2 .

35] Nickel S , Schröder M , Steeg J . Mid-term and short-term planning support for home health care services. Eur J Oper Res 2012;219(3):574–87 .

36] Quimper C-G , Walsh T . Decomposing global grammar constraints. In: Prin- ciples and practice of constraint programming–CP 2007. Springer; 2007.

p. 590–604 . [37] Restrepo MI , Gendron B , Rousseau L-M . Branch-and-price for multi-activity

tour scheduling. INFORMS J Comput 2016;28(2):1–17 . 38] Restrepo MI , Gendron B , Rousseau L-M . A two-stage stochastic pro-

gramming approach for multi-activity tour scheduling. Eur J Oper Res 2017;262(2):620–35 .

39] Rodriguez C , Garaix T , Xie X , Augusto V . Staff dimensioning in homecare ser-

vices with uncertain demands. Int J Prod Res 2015;53(24):7396–410 . 40] Soyiri IN , Reidpath DD . An overview of health forecasting. Environ Health Prev

Med 2013;18:1—9 . [41] Taylor SJ , Letham B . Forecasting at scale. Am Stat 2018;72(1):37–45 .

42] Trautsamwieser A , Hirsch P . A branch-price-and-cut approach for solv- ing the medium-term home health care planning problem. Networks

2014;64(3):143–59 .

43] Wirnitzer J , Heckmann I , Meyer A , Nickel S . Patient-based nurse rostering in home care. Oper Res Health Care 2016;8:91–102 .