A stochastic integer programming approach to reserve staff scheduling with preferences Carl Perreault-Laﬂeura Margarida Carvalhoaand Guy Desaulniersb

2025-05-01 0 0 533.52KB 25 页 10玖币

侵权投诉

A stochastic integer programming approach to reserve staff

scheduling with preferences

Carl Perreault-Laﬂeura,∗, Margarida Carvalhoaand Guy Desaulniersb

aCIRRELT and D´

epartement d’informatique et de recherche op´

erationnelle, Universit´

e de Montr´

eal, Montr´

eal, H3T 1J4,

Canada

bGERAD and D´

epartment de math´

ematiques et de g´

enie industriel, Polytechnique Montr´

eal, Montr´

eal, H3T 1J4, Canada

E-mail: carl.perreault-laﬂeur@umontreal.ca [Carl]; carvalho@iro.umontreal.ca [Margarida];

guy.desaulniers@gerad.ca [Guy]

Abstract

Nowadays, reaching a high level of employee satisfaction in efﬁcient schedules is an important and difﬁcult task

faced by companies. We tackle a new variant of the personnel scheduling problem under unknown demand by con-

sidering employee satisfaction via endogenous uncertainty depending on the combination of their preferred and

received schedules. We address this problem in the context of reserve staff scheduling, an unstudied operational

problem from the transit industry. To handle the challenges brought by the two uncertainty sources, regular em-

ployee and reserve employee absences, we formulate this problem as a two-stage stochastic integer program with

mixed-integer recourse. The ﬁrst-stage decisions consist in ﬁnding the days off of the reserve employees. After the

unknown regular employee absences are revealed, the second-stage decisions are to schedule the reserve staff du-

ties. We incorporate reserve employees’ days-off preferences into the model to examine how employee satisfaction

may affect their own absence rates.

Keywords: Personnel scheduling; Stochastic programming; Integer programming; Employee preferences; Transit industry; En-

dogenous uncertainty

1. Introduction

Employee absences can have a critical impact on the quality of service offered by companies. This is

particularly the case in the transportation sector where the absenteeism is very high due to atypical

workdays, which can easily lead to service cancellations. Therefore, some enterprises rely on a speciﬁc

pool of workers, called extra-boards (XBs) in the transit industry, to mainly cover the regular employees’

absences. In contrast to the known-in-advance absences such as employee vacations, long term absences

and open work, the unknown absences that are declared close to the operation day result in uncertainty

∗Author to whom all correspondence should be addressed (e-mail: carl.perreault-laﬂeur@umontreal.ca).

arXiv:2210.04808v1 [math.OC] 10 Oct 2022

about when to schedule XBs. It is important that each day, the number of XBs scheduled matches the

demand in terms of the shortage of regular employees to avoid service cancellation or XBs idle time. In

the remainder of the study, when we mention demand, we are referring to demand in terms of XBs to

cover the regular employee absences.

As described in Desaulniers and Hickman (2007), the planning process of transit industry is commonly

divided into three parts: strategical, tactical and operational. The strategical part aims at taking long-

term decisions having a direct impact on the quality of service such as the network and route transit

design. The tactical phase is reviewed on a seasonal basis, and also concerns the quality of service

such as the bus frequencies and timetabling, recruitment targets and employee dispatch by division.

Finally, the operational phase seeks to offer the previously proposed service at a minimal cost. To do so,

many different problems are solved, the largest two problems being vehicle scheduling and personnel

scheduling. This is where the XB (personnel) scheduling problem arises. The XB scheduling process

varies around the world. In Europe, the XBs are assigned each possible days-off pattern and duty (the

shift of the employees, consisting of the start time, end time, and a potential pause) over time, as part

of rotating schedules. In contrast, in North America, the days-off patterns are assigned from scratch to

the XBs at the start of each scheduling horizon, and the duties are assigned at the latest the eve of the

operation day. In practice, the dispatcher decides on the number of days off to be offered each day of the

scheduling horizon. Then, according to their seniority, the XBs take turn choosing which days off they

prefer among the ones still available.

Due to ongoing and anticipated labor market shortages, it has become essential for companies to

take into account employee preferences to differentiate themselves, recruit new employees and address

employee retention. In our study, we follow the North American XB scheduling process and directly

assign the days-off pattern to the XBs to better incorporate their preferences in the optimization process.

This approach generalizes well to multiple applications that consider employee preferences, such as in

nurse scheduling (see Miller et al. (1976) and Goodman et al. (2009)).

1.1. Contributions

Our contributions summarize as follows.

First, we formulate a two-stage stochastic integer program with mixed-integer recourse to model the

XB days-off scheduling problem over a ﬁnite time horizon. In most cases, this scheduling is done manu-

ally by the dispatchers, at best making use of average absence ratios. In our model formulation, we lever-

age the decomposable aspect of absence scenarios per time period to achieve representational power for

uncertainty. This contrasts with the classical method of deﬁning scenarios in stochastic programming,

which would require exponentially more scenarios.

Second, we consider XB preferences in the process to model uncertainty. Social science researches

aiming at reducing employee absenteeism have unanimously identiﬁed job satisfaction as a key factor

inﬂuencing the employee’s motivation to attend work (Kehinde (2011), Tasie (2018)). Personal reasons,

at the individual level, have also been identiﬁed as an absenteeism cause. For example, some employees

might have some strict constraints (due to family responsibilities, health issues, etc.), making them un-

available to work on certain days. These motivate our initial assumption that an XB assigned to preferred

days off is less likely to be absent. This assumption not only gives the ﬂexibility to increase the satisfac-

tion level of employees receiving their preferred days off, but also allows to manage the strict schedule

constraints some employees might have. To the best of our knowledge, this is the ﬁrst time that reserve

employee preferences are considered in an absence stafﬁng problem.

Third, we expose a new type of problem mixing both exogenous and endogenous uncertainties. In

one hand, exogenous uncertainty, i.e., uncertainty independent from the decisions, is the most standard

form of uncertainty in stochastic programming and is represented in our problem as the demand. On

the other hand, endogenous uncertainty has been little studied and is much more difﬁcult to treat as the

stochastic processes are affected by the decisions. Indeed, in our problem, when an XB is assigned to

a days-off pattern, he/she can be satisﬁed, unsatisﬁed or neutral, which can alter his/her own absence

probability on certain of his/her working days. Hence, the uncertainty regarding XB absences depends

on the ﬁrst-stage decisions related to the days-off pattern assignment. In our formulation, we mimic this

endogenous uncertainty in a linear fashion.

Our approach is validated with an empirical study based on data from the city of Los Angeles. We

show that taking preferences into account leads to signiﬁcant improvements when compared to not con-

sidering preferences: on average, employee social welfare is improved by 37.12% while also substan-

tially minimizing the cancelled service by 21.14%. The stochastic programming formulation is partly

responsible for theses gains as the social welfare and the cancelled service are improved on average by

7.65% and 16.63%, respectively, when comparing with a deterministic formulation.

1.2. Paper organization

This paper is organised the following way. Section 2 surveys the literature relevant to our problem. In

Section 3, we describe the XB days-off scheduling problem and the proposed mathematical program to

model it in Section 4. We detail the setup of our empirical study in Section 5, and report the results in

Section 6. Finally, Section 7 draws conclusions and discusses possible directions for future research.

2. Related literature

In this section, we provide a detailed landscape of the existent literature related to personnel scheduling,

uncertainty in scheduling and preference optimization.

Personnel scheduling.Historically, personnel scheduling problems have been the subject of numerous

studies in many industries: transportation, health care, retail stores, etc. It consists in ﬁnding the days off

and working days of a set of employees, and the shifts or duties for the working employees. In general

and at a very high level, the set of hard constraints is divided into two parts. The ﬁrst one requires

a covering of the demand by the employees. The second one can be seen as a set of work rules to

comply to, ensuring the feasibility of the employee schedules. Then, a set of soft constraints comes on

top to deﬁne which solutions are preferable among the set of valid schedules. Employee preferences,

for example, belong to this class of soft constraints. These groups of constraints are easily identiﬁed

in most of the personnel scheduling problems, e.g., the nurse scheduling problem (Jafari and Salmasi

(2015)), the airline and transit crew rostering problems (Kohl and Karisch (2004) and Xie et al. (2012)),

and the retail store workforce scheduling problem (Chapados et al. (2011)). Of course, many variations

emerge from one domain to another. For instance, cyclic schedules are often required in the European

bus transit industry, employee competency-based schedules are mostly used in the health care industry,

and preference-based schedules are increasing in popularity across all domains.

Within the personnel scheduling literature, it is particularly relevant the works on days-off scheduling.

To the best of our knowledge, no literature exists on our particular problem of assigning days off to

reserve employees. However, general days-off scheduling has been studied. Days-off scheduling consists

in ﬁnding the right daily number of employees needed to satisfy the daily demand, while ensuring the

days-off rules hold. Multiple policies exist for the days off: two days off per week, two consecutive days

off per week, four days off every two weeks, etc. This problem alone is not very complex as the number

of days-off patterns is usually low and the demand is pre-determined. Its main challenge resides in the

modeling of the days-off rules. Variants include consideration of multiple types of employees such as

part time and full time (Emmons and Fuh (1997)), employee skills and qualiﬁcations for tasks (Ulusam

Sec¸kiner et al. (2007)), and cyclic schedules (Emmons and Burns (1991)). After having decided who

is working on which days, the shift scheduling occurs, which consists in assigning duties to working

employees to satisfy the demand over the course of the day. Shift scheduling alone can have varying

complexity depending on the number of possible duties. Again, the employee demand is pre-determined.

Embedding days-off with shift scheduling yields the so-called tour scheduling. When the duty start

and end times are mostly invariant (such as in manufacturing companies where the duties are often

9AM-5PM), the tour scheduling problem can be tackled directly. Such an example is shown in Bailey

(1985) which considers only ﬁve different start times. However, usually, the days-off and shift scheduling

problems must be solved in turn, due to the explosion of possibilities when considering the combinations

of days-off patterns and duties. van Veldhoven et al. (2016) show that although this 2-step decomposition

reduces the solution time by 80% to 90%, the quality of the solutions is often deteriorated compared to

when solving directly the tour scheduling problem. The problem tackled by us is a (stochastic) tour

scheduling problem.

Scheduling under uncertainty.Van den Bergh et al. (2013) offer a broad review of the solution meth-

ods for general personnel scheduling problems. In their review, they point out three uncertainty sources

that could be faced. Those are uncertainties related to the demand (what is the workload to accomplish?),

the arrival (when does the workload occur?), and the capacity (how many employees can be used?). In

the personnel scheduling literature, it is very common to account for pre-determined demand and num-

ber of employees. Those uncertainties about the workload and the workforce are thus, most of the time,

completely ignored. In these deterministic approaches, the workers are assumed to be always present,

whereas absences are unavoidable in practice. The uncertainties related to the workload are also dis-

regarded; when not ﬁxed and known, the workload is estimated via historical data, using forecast and

prediction techniques such as machine learning. Although these estimations can be accurate, the stochas-

tic aspect of the demand is left out, leaving the developed models sensitive to when the estimations differ

from the real demand. Some approaches exist to account for the disruptions while keeping a determinis-

tic modeling. In this context, the goal is to create schedules that necessitate only few adjustments when

disruptions happen to the estimated demand. Examples of works in this line are Ingels and Maenhout

(2017); Paias et al. (2021).

Stochastic approaches, however, are more appropriate due to their ability to incorporate and han-

dle such forms of uncertainty compared to the deterministic approaches. Overall, although most of the

personnel scheduling problems are approached in a deterministic way, some papers follow the stochas-

tic path. This is the case of Kim and Mehrotra (2015), who formulate an integrated nurse stafﬁng and

scheduling problem with unknown demand as a two-stage stochastic integer program. They schedule the

nurses for 3-month long horizons, while respecting rules on the nurse-to-patient ratios and not knowing

in advance the number of patients in the hospital. Their recourse action is to add or cancel shifts, with

associated costs for each. Penalty costs are also inferred for overstafﬁng and understafﬁng. They demon-

strate computationally the efﬁciency of their model on the cost savings, and that these savings increase

with the precision of the demand forecasts. In our model, the uncertainty, i.e., the stochastic process, will

be in personnel absences.

In stochastic optimization, most of the uncertainty we encounter is modeled as exogenous uncertainty.

That is, the decision variables do not affect the uncertainty distribution. However, with endogenous un-

certainty, the decisions can inﬂuence the probability distribution. Goel and Grossmann (2006) and Li and

Grossmann (2021) distinguish two types of endogenous uncertainty. In type I endogenous uncertainty,

decisions inﬂuence the parameter realizations by altering the underlying probability distributions for the

uncertain parameters. In type II, the decisions inﬂuence the parameter realizations by affecting the time

at which we observe these realizations. In our setting, only the type I is of interest since we hypothe-

size that the XBs’ absence rates vary according to their satisfaction with the assigned days-off patterns.

However, to the best of our knowledge, there is no work on scheduling considering type I endogenous

uncertainty.

Individual preference optimization.Individual preferences are now fundamental in the design of

schedules. More and more personnel scheduling papers incorporate them in their models. In the litera-

ture, we can ﬁnd two different approaches for considering preferences. The ﬁrst one, the most common,

is to account for the preferences directly in the model and maximize for overall satisfaction. This method

is used in Badri et al. (1998), Jafari and Salmasi (2015) and Bard and Purnomo (2005), to name just a

few. The second one consists in ﬁrst creating schedules without preferences, and then performing an

auction where the employees bid on their preferred schedules as in De Grano et al. (2009). In general,

few attention is given to the fairness in the attribution of the schedules to employees. Multiple optimal

solutions that assign different schedules to different employees might exist, with some employees being

more satisﬁed than others about their schedules. This demonstrates that even if the employee satisfaction

about the schedules is globally high, unfairness can arise from an egalitarian perspective. To counter this

effect, Badri et al. (1998) design the penalty of not respecting a preference as an increasing function of

the number and severity (according to some rules) of preference violations. As explained in Section 1.1,

one of the reasons to consider employee preferences in schedules is to increase job satisfaction, which

can in turn decrease absenteeism. The inverse is also, and perhaps even more, true: de Boer et al. (2002)

state that job dissatisfaction, together with stress, are the two explanations for absenteeism. In the math-

ematical programs designed to solve preference-aware personnel scheduling problems, keeping track of

employee satisfaction at the individual level based on the realization of their preferences on the assigned

schedules becomes challenging because it depends on decision variables.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

AstochasticintegerprogrammingapproachtoreservestaffschedulingwithpreferencesCarlPerreault-Laeura,,MargaridaCarvalhoaandGuyDesaulniersbaCIRRELTandD´epartementd'informatiqueetderechercheop´erationnelle,Universit´edeMontr´eal,Montr´eal,H3T1J4,CanadabGERADandD´epartmentdemath´ematiquesetdeg´enieindust...

展开>> 收起<<

A stochastic integer programming approach to reserve staff scheduling with preferences Carl Perreault-Laﬂeura Margarida Carvalhoaand Guy Desaulniersb.pdf

共25页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

A stochastic integer programming approach to reserve staff scheduling with preferences Carl Perreault-Laﬂeura Margarida Carvalhoaand Guy Desaulniersb

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: