# Joint employee weekly timetabling and daily rostering: a decision-support tool for a logistics platform

Anne-Laure Ladier, Gülgün Alpan, Bernard Penz

► To cite this version:

Anne-Laure Ladier, Gülgün Alpan, Bernard Penz. Joint employee weekly timetabling and daily rostering: a decision-support tool for a logistics platform. European Journal of Operational Research, 2014, 234 (1), pp.278-291. 10.1016/j.ejor.2013.10.023. hal-00881714

HAL Id: hal-00881714

https://hal.science/hal-00881714v1

Submitted on 29 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Joint employee weekly timetabling and daily rostering: a decision-support
tool for a logistics platform ⚙

Anne-Laure Ladier<sup>a,∗</sup>, Gülgün Alpan<sup>a</sup>, Bernard Penz<sup>a</sup>

<sup>a</sup>Grenoble-INP / UJF-Grenoble 1 / CNRS
G-SCOP UMR5272 Grenoble, F-38031
46 avenue Félix Viallet, 38000 Grenoble, France

**Abstract**

To deal with their highly variable workload, logistics companies make their task force flexible using multi-skilled employees, flexible working hours or short-term contracts. Together with the legal constraints and the handling equipments' capacities, these possibilities make personnel scheduling a complex task. This paper describes a model to support their chain of decisions from the weekly timetabling to the daily rostering (detailed task allocation).

We divide the problem into three sub-problems depending on the type of decision to be made: (1) workforce dimensioning, (2) task allocation for a week, (3) detailed rostering for a day. The three decisions are made sequentially, the output of a step being the input of the next one. Each step is modeled as a mixed integer linear program which is described and commented.

The proposed models are tested with industrial data as well as generated instances. From the observations made in an industrial context, we show that our model is an actual management tool supporting the managers in their operational decisions. This tool is currently used by the company which provided us with the industrial data. Based on the results with the generated instances, we present the conditions under which the models can be solved within a reasonable amount of time, and we assess the robustness of the daily rostering when the input data changes.

**Keywords:** Manpower planning, Logistics, Mixed integer linear programming, Sequential solving

**1. Introduction**

Warehouses operate in a very competitive market, where purchasers keep pushing to knock the prices down (Rebitzer [24], Klaus [17]). The logistics providers therefore have to show a high flexibility to be able to attract customers. Even if some operations can be automated, buying machines and adapting them to the customer's need is barely cost-effective (Naish et al. [21]). Therefore, most of the operations taking place in logistics platforms are done by human beings, which makes manpower the first cost center. It is thus crucial to stick to the activity volume when dimensioning the task force.

A difficulty is that the workload is variable: the number of arriving trucks and the number of orders to be prepared change every day. To be able to react accordingly, the workforce needs to be flexible: the number of working hours for a given employee may differ from one week to another. Short-term contracts can also be used to ensure more flexibility. All these parameters, together with other constraints such as the employees' qualifications, vacations, the handling equipment availability, etc., make *weekly timetabling* and *daily rostering* a complex process.

<footnote><sup>∗</sup>This work has been supported by Rhône-Alpes Region.</footnote>

<footnote>*Corresponding author</footnote>

<footnote>Email address: anne-laure.ladier@g-scop.grenoble-inp.fr (Anne-Laure Ladier)</footnote>
Wren [30] defines rostering as “the placing, subject to constraints, of resources into slots in a pattern. One may seek to minimize some objective, or simply to obtain a feasible allocation. Often the resources will rotate through a roster”. Following Ernst et al. [11], we use the words personnel scheduling to describe the whole process of constructing work timetables for an organization’s staff, in order to satisfy the demand for its goods or services. As mentioned by Musliu et al. [20], personnel scheduling algorithms consist of different stages related to each other, that can be solved simultaneously or in sequence, depending on the context. In this paper, we call weekly timetabling the part of the process which consists of determining the number of employees needed and allocating these employees to shifts (sets of consecutive time periods within a day) to meet the demand. The expression daily rostering refers to the assignment of tasks to employees on a daily level.

The problem presented in this article falls in the category of “multi-day personnel scheduling problems” defined by Brucker et al. [2] in their general model for personnel scheduling. The authors underline that the “multi-day personnel scheduling problems” can be decomposed into two levels: in the first stage, the working days are assigned to the employees (i.e. weekly timetabling), whereas the second stage assigns a shift for each employee working on a given day, and a task for which the employee is qualified on each working period (i.e. daily rostering). Although weekly timetabling and daily rostering are intertwined, they are often treated separately in the literature; in this paper, we propose to deal with the two of them together through sequential solving. We also notice from the literature that the logistics field is not a common application area for personnel scheduling problems, and the few existing papers use heuristic methods to solve the problem. The model proposed in this paper meets the specific requirements of a logistics platform to support the personnel scheduling process for warehousing operations, and its solution is based on optimal methods (mixed integer linear programming).

Our purpose is to determine the working hours of all employees for one week, as well as their exact task allocation every day. All legal and job-related constraints must be included. We divide the problem into three steps, each representing a decision to be made. Each step is modeled by a mixed integer linear program.

The model has been tested in a logistics company, whose name is not cited for confidentiality reasons. A decision-support tool, based on the models described in the present article, is now used on a weekly/daily basis to support the managers’ decisions.

The rest of the article is organized as follows. After a literature review (section 2), we give in section 3 an overview of the problem, the decision-making process, and the general notations. Section 4 details the first part of the model, namely the weekly timetabling (step 1 and step 2). Section 5 deals with the detailed daily rostering (step 3). Section 6 presents the numerical results, and concluding remarks are given in section 7.

## 2. Literature review

Our review will focus on two aspects: firstly, section 2.1 focuses on the application areas of personal scheduling problems, to see how the logistics field relates with the fields covered by current research. Secondly, in section 2.2 we have a closer look at the working methods used in the literature to solve weekly timetabling and daily rostering problems.

### 2.1. Personnel scheduling in logistics

In logistics and especially for logistics providers, the main production resource is the human resource (Graham [13]). Therefore, production planning consists mainly of workforce scheduling, which thus becomes a crucial point for the operations efficiency. The logistics industry faces several challenges which are specific to this field:

* The highly variable demand makes the workload very different from one day to another, which means that regular patterns cannot be used to create the workers’ timetables;
* The qualifications are very specific to a person: two employees are very likely to have different skills and different licenses to drive the handling equipment. Therefore, the set of tasks mastered by a given employee will be different from the set of tasks mastered by any of his colleagues, and clustering the employees according to their skills does not simplify the problem;

* The unequal distribution of busy periods over a day does not fit a standard 8-hour shift: supervisors must therefore assign shorter or longer shifts, force some employees to take a day off, or hire temporary workers.

Personnel scheduling questions have been broadly studied for transportation systems (including airlines, railways and buses): the constraints tackled by the so-called *crew scheduling* problems are very specific, since the location of the crews is also a variable. The interested reader can refer to Castillo-Salazar et al. [5] for a survey on workforce scheduling and routing. *Nurse scheduling* and, more generally, health care systems scheduling is also a major application area (see the survey by Burke et al. [3]), in which the problems are highly constrained because hospitals work around the clock. The main differences between the health care field and logistics are:

* The relative simplicity of the qualifications profiles used. As mentioned earlier, a logistics employee has qualifications that allow him to work only on specific tasks, while a nurse has one qualification which allows her to do all the tasks. Therefore, the daily rostering is not needed for nurses, since they know precisely what they are supposed to do when assigned to a given shift. The problem can be solved on a shift level.

* The shape of the coverage function (number of employees required each hour). As highlighted by De Causmaecker et al. [7], hospital personnel scheduling problems are *permanence centered*, while warehouse personnel planning are based on *fluctuating demand*.

Overall, the granularity of the nurse timetabling problems is lower than staff timetabling for logistics and, more generally, for the service industry.

The service industries whose characteristics and requirements are the closest to the logistics area are retailing, call centers and postal service; for instance, the model proposed by Bard et al. [1] to schedule the United States Postal Service staff meets most of the constraints encountered in logistics operations. However, they focus on the long-range planning problem rather than the weekly scheduling problem. The weekly personnel scheduling problems raised in the US Postal Service mail processing are addressed by Wan [29], who also deals with the US Postal service distribution centers, whose activities are typical logistics operations. But like Bard et al [1], he considers a homogeneous workforce, without distinctions in skills and qualifications.

The literature studying warehouse personnel scheduling as such is still very limited: no paper appears in the comprehensive review made by Ernst et al. [10], covering the literature until 2004 of more than 700 analyzed sources dealing with personnel scheduling problems. Only De Causmaecker et al. [7] mention this field as an application area, since a small warehouse (20 employees) was included in the sample of Belgian companies they investigated to classify the scheduling problems. A recent state-of-the-art by Van den Bergh et al. [27] reviews 291 articles from 2004 to 2012, in which Günther and Nissen [14, 15] are the only ones dealing with a real-world scheduling problem in logistics, comparing three heuristics and an evolutionary method to solve a daily rostering problem for a German logistics service provider with 65 employees. The model proposed by these authors is a multi-objective model. They seek to minimize the over and understaffing, the extra hours worked every week, and the cases where the working days are too short, too long, or split up during a working day. The industrial data used is in open access. We will come back to these data at the numerical experiments section of our article (section 6.2).

## 2.2. Sequential approach for joint weekly timetabling and daily rostering

The current paper proposes to solve in sequence a weekly timetabling and a daily rostering problem. We see from the articles gathered by Ernst et al. [10] that these concepts (named a bit differently in the
review, since the authors use the words “workforce planning”, “shift scheduling” and “task assignment”) are never studied at the same time: amongst the articles reviewed, 163 deal with workforce planning and shift scheduling, 33 for task assignment, but none tackles these problems together.

Since the review by Ernst et al. [10] was conducted in 2004, two papers proposed some global models to solve a timetabling problem (see Detienne et al. [8] and Naudin et al. [22]). The similarity with our approach resides in the fact that they also consider the overall problem to have two decision stages (a weekly stage and a daily stage). In their case, this idea is exploited to propose bounds or decomposition methods that can help solving one overall model. Detienne et al. [8] use this idea to implement a Lagrangian lower bound for their model. They also propose a multi-dimensional multi-choice knapsack problem which aggregates the two decision stages in one, but the latter formulation generates an exponential number of constraints. Naudin et al. [22] propose two decompositions: a Dantzig-Wolfe decomposition reformulated with mid-term variables, and another one with long-term variables. These two approaches are not easily applicable in our case because of the multiple constraints we have – but it is an idea that could be investigated. In the current article, we use the decomposition idea in order to propose a sequential approach where the problem is divided into steps solved one after the other, each stage using as an input the output of the previous stage. Each phase having only limited information about the others, the solution is unlikely to be optimal, but this approach can solve large timetabling problems. Another advantage of our model compared to Detienne et al. [8] and Naudin et al. [22] is that the outcome of our approach is not only a daily timetable but both the weekly schedule and the daily timetable. From a managerial point of view, both are of importance. The managers need the weekly schedule for workforce dimensioning and planning and the daily rostering for operations management. Furthermore, having both gives a certain flexibility in case of unexpected events. For instance, the daily rostering can be readjusted very quickly based on a new piece of information, which was not available when the weekly schedule was done.

A sequential approach with two stages is used in a recent paper by van Veldhoven et al. [28] but to solve a different problem, the nurse days-off scheduling problem. The first stage specifies the days off for each employee (days off scheduling), then the second phase specifies which shifts are actually assigned to the employees on their working days. Each phase is solved with an integer program. We note that our problem is of finer granularity, since we deal with the daily rostering as well.

Each stage of our model, taken separately, presents some similarities with problems which have been modeled already. In the weekly timetabling, we first dimension the workforce. This step is close to the one solved by Eitzen et al. [9] for an Australian power station: the employees have different skill qualifications and need to be allocated under legal constraints, while ensuring the equity of the outcome. The authors formulated the problem as a generalized set-covering problem minimizing the total under-staffing, and tested various solution strategies. Only the method of branch and price is capable of finding a provably optimal solution for a problem size of 20 to 110 employees. Note also that Eitzen et al. [9] do not consider hiring temporary workers if the demand gets too high. The review by Van den Bergh et al. [27] shows that the possibility of hiring interim or casual workers is not very common in the personnel scheduling literature.

The second step of the weekly timetabling consists of assigning shifts and tasks to employees. This step is close to the one described by Schaerf and Meisels [25], although they do not give the exact formulation of their model in this paper. Their generalized local search is tested for nurses in a hospital department and for a production line in a factory, with 20 to 50 employees, 100 to 300 tasks and 20 to 40 shifts, after relaxing all soft constraints. Their coverage function is less precise than the one we use, since it only gives a number of employees that should be present during each shift. Also, it is not clear whether the length of the shifts can vary in their case. Another model close to ours is the one proposed by Dahmen and Rekik [6], who deal with a multi-activity shift problem. The goal is to construct the shifts and assign the activities for employees with various qualifications (although all the employees are qualified for all tasks in the instances used to test the model). The constraints considered are very similar to ours: over and under-staffing are penalized, and the tasks have minimum and maximum durations. The limit of this model is that it supposes an explicit enumeration of all admissible shifts with assigned activities for each employee. This, in practice, is quite
complex to do when the number of activities or employees is high. The authors propose a hybrid heuristic to solve the problem, combining tabu search and branch and bound.

The daily rostering problem has been modeled by Campbell and Diaby [4] in the case of multi-skilled workers. In their model, a worker less skilled than another needs more time to complete his work. They propose a linear program for the special case of binary capabilities, and an assignment heuristic for the general allocation problem. More recently, other problems closer to our third stage have been studied by Smet and Vanden Berghe [26] and Lequy et al. [18, 19]. Smet and Vanden Berghe [26] deal with a shift minimization personnel task scheduling problem, where the objective is to assign tasks to multi-skilled employees (with binary capabilities) while minimizing the number of employees used. Solutions are obtained with a very large-scale neighborhood search algorithm, combining metaheuristics and exact approaches. A model closer to our approach is the multi-activity assignment problem proposed by Lequy et al. [18]. The work shifts being already assigned to the employees, the problem is to assign activities, taking the qualifications into account and covering the demand as much as possible on the planning horizon (from one day to one week). The objective is to minimize the under-staffing, over-staffing and transition costs (paid when an employee changes activity). This work is extended in Lequy et al. [19]: the workload is now divided between tasks which are uninterruptible pieces of work, and activities for which preemption is allowed. The solution strategy proposed is a two-stage heuristic: the task assignment is done first, then the activities are assigned considering the fixed tasks.

It is important to note that in all those papers, the employees' shifts cannot be changed anymore at this stage. In our model however, shift changes are allowed in exchange for a penalty cost, if there are differences between the forecast and the actual workload occurring on that day.

The articles cited above solve a part of the global problem we want to solve, and they mainly do it through heuristics or metaheuristics. The originality of our approach is to combine the workforce scheduling problem and the daily rostering through sequential solving, each step being modeled by a mixed integer linear program solved to optimal.

### 3. Problem presentation and overview of the decisions model

Our goal is to define a model which can be used in logistics platforms to generate the personnel schedules based on optimal methods. To be as close as possible to an industrial context when building the model and defining its main assumptions, we observed the scheduling process within a warehouse where the timetabling generation is done manually.

According to the agreements signed with the trade unions, the working hours for the following week have to be communicated to the employees seven days in advance. The daily roster, however, can be given each morning or even redefined at any time during the day. Of course the working hours of each employee in this detailed roster must be as close as possible to what has been announced a week before. Since there are two different time scales in the decisions to be made, the problem can be split into two distinct phases. First, working days and shifts are assigned to employees for one week (*weekly timetabling*); then the weekly timetable is used as a basis to re-assign tasks within a day with more precision, taking into account the possibly new data which may arrive in the meantime (*daily rostering*).

Looking more closely at the *weekly timetabling* problem, we can see that it is also a two-stage decision. First, the workforce has to be dimensioned (decision about the number of employees to hire on short-term contracts, and the total number of hours worked) before deciding upon the shifts themselves (when each employee should start and finish his day) and the task allocation. The scheduling system is therefore composed of three different mixed integer linear programs, as shown in figure 1. These are referred to in this article as MILP1, MILP2 and MILP3. The *weekly timetabling* part, composed of MILP1 and MILP2, will be detailed in section 4, and the *daily rostering* part (MILP3) in section 5. What needs to be noted at this point is the fact that some inputs of MILP2 and MILP3 are the outputs of MILP1 and MILP2 respectively.

MILP1, MILP2 and MILP3 are built under the assumption that the workload is varying over time, while the employees' working hours are flexible. We consider two types of employees: regular employees
<figure><img src="image_2.png" /><figcaption>Figure 1: Overview of the decision-support tool</figcaption></figure>

and temporary workers. For regular employees, various shifts are possible as long as they respect the trade agreements. Temporary workers with short-time contracts, though, do not have flexible working times: they are hired for the exact number of hours allowed by the law per week.

The objective of each linear program is to get a feasible solution under the hard constraints related to legal requirements, while minimizing unwanted situations like non-equity, over-staffing or having an employee working on the same task for too long. A penalty point is counted for the occurrence of each one of these situations, and the objective function is a weighted sum of the penalty points.

As a convention, for the rest of the document, we will use calligraphic letters to name the sets, capital letters for the known input parameters, and lower-case letters for the decision variables. In the following sections, the input data and the decision variables are defined over these sets:

E, set of employees considered in the timetabling operation.

Efixed subset of E, set of employees whose shift is fixed beforehand. These employees are working under a special contract (pre-retirement, for instance) and their working time is fixed instead of flexible. Their exact tasks during that time still have to be calculated.

$\mathcal{T}$, set of tasks to be processed by the employees. Two tasks are different if they require different abilities or different handling machines. The time when the tasks have to be done depends on their nature: some tasks must be carried out in precise time windows, while some can be carried out at any time during the day. We therefore split the tasks into two groups:

* $\mathcal{T}^1$ subset of $\mathcal{T}$, set of tasks whose workload is defined precisely, hour per hour. For instance, containers have to be unloaded right after their arrival, so the workload for the task “unloading containers” is defined hour per hour. Note that this definition helps expressing precedence relationships among tasks in the data set. For each arriving container, the distribution of the workload over all tasks are estimated. For example, if a container arrives at 8 am, a non-zero workload will be estimated for the “unloading” task at 8 am, then the workload for the “scanning and computer reception” task will be estimated at 9 am. The constraints on consecutive tasks are therefore not needed in the model.

* $\mathcal{T}^2$ subset of $\mathcal{T}$, complementary to $\mathcal{T}^1$, set of tasks whose workload is defined for a whole slot. For instance, stocktaking is a task that can be completed at any time during the day, the workload for this task is therefore defined for the whole slot 8 am - 5 pm.

$\mathcal{P}$, set of temporary workers profiles. In case the workload is too heavy compared to the workforce available, the decision-support tool will suggest to hire temporary workers of a given profile. A temporary worker profile is a set of tasks that this type of worker can handle. For example, the profile of an “order picker” could be {manual unloading, picking, wrapping}.
D, set of working days considered for the weekly schedule. That can be five to seven, depending on whether work over the week-end is allowed or not.

H, set of working hours in a day. That can be eight to twenty-four, depending on whether the activity runs with one, two or three shifts a day.

S, set of possible shifts. A shift, for example, is "8 am - 4 pm" or "10 am - 6 pm". Two shifts are different if they have different beginning and/or ending times.

I, set of intervals considered for the daily rostering. The unit may be smaller than an hour.

## 4. The weekly timetabling

In this section we present in detail how we obtain a weekly timetable for the employees. First, the workforce dimensioning is calculated using MILP1, and this data is used to process the weekly shift allocation in MILP2.

### 4.1. MILP1

The aim of the first linear program is to define the workload per person and per day. The decisions made are therefore about the number of temporary workers to hire, and the number of hours per task assigned to a worker (temporary or regular) each day, for a one-week horizon.

Initially, a pre-treatment of the input data is made, in order to reduce the size of the linear programs in terms of number of constraints. We have information about:

* the abilities ($\mathcal{E} \times \mathcal{T}$): for each task, whether or not each employee is able to carry it out;

* the availabilities ($\mathcal{E} \times \mathcal{D}$): for each day, whether or not each employee is present;

* the work planning ($\mathcal{D} \times \mathcal{T}$): for each day, whether or not each task needs to be carried out on that day.

Instead of considering these three bi-dimensional matrices in the linear program, we build a three-dimensional binary matrix that puts this information together without redundancies. We call this matrix $X$ and define it over $\mathcal{E} \times \mathcal{D} \times \mathcal{T}$. $X_{edt} = 0$ if the employee $e$ is not qualified for the task $t$, or if the employee $e$ is not available on the day $d$, or if there is no work needed for task $t$ on day $d$; $X_{edt} = 1$ otherwise.

We use as inputs the following data:

$X_{edt}$ $\forall e \in \mathcal{E}, d \in \mathcal{D}, t \in \mathcal{T}$ **Data matrix** as defined above.

$W_{td}$ $\forall t \in \mathcal{T}, d \in \mathcal{D}$ **Workload** (in working hours) per task and per day.

$N_{td}$ $\forall t \in \mathcal{T}, d \in \mathcal{D}$ Minimum number of people needed at the **same time** to carry out task $t$ on day $d$.

$Q_{et}$ $\forall e \in \mathcal{E}, t \in \mathcal{T}$ **Non-binary qualifications** per employee and per task, defined on $\{0..\zeta\}$ where $\zeta \in \mathbb{N}^*$. The value of $Q_{et}$ depends on the level of experience of the employee $e$ for a given task $t$.

$P_{pt}$ $\forall p \in \mathcal{P}, t \in \mathcal{T}$ **Temporary workers profile** description. $P_{pt} = 1$ if a worker with profile $p$ is qualified for task $t$, 0 otherwise.

$C_p$ $\forall p \in \mathcal{P}$ **Temporary workers cost**. $C_p$ is the cost of hiring a worker with profile $p$.

$\text{Max}_t$ $\forall t \in \mathcal{T}$ Maximum amount of time (in hours) that a worker can spend per day on task $t$. This value enables one to respect **safety and ergonomics** principles.

$F_{ed}$ $\forall e \in \mathcal{E}^{fixed}, d \in \mathcal{D}$ Working time of the employee $e$, whose shift is defined beforehand, on day $d$.
In order to be as general as possible, we note $min^{day}$ the minimum number of hours that an employee can work per day, $max^{day}$ the maximum daily hours, and $max^{week}$ the maximum number of hours per week permitted by the law. The model can therefore be adapted to different labor legislations or local agreements.

This step uses the following decision variables:

Regarding the regular workers:

$h_{edt}$ $\forall e \in \mathcal{E}, d \in \mathcal{D}, t \in \mathcal{T}$ **Number of hours** worked by employee $e$ on day $d$ and task $t$.

$p_{ed}$ $\forall e \in \mathcal{E}, d \in \mathcal{D}$ **Presence** of employee $e$ on day $d$. $p_{ed} = 1$ if $e$ works on day $d$, 0 otherwise.

$x_{edt}$ $\forall e \in \mathcal{E}, d \in \mathcal{D}, t \in \mathcal{T}$ **Task allocation.** $x_{edt} = 1$ if employee $e$ works on task $t$ on day $d$, 0 otherwise.

Regarding the temporary workers:

$h_{dtp}$ $\forall d \in \mathcal{D}, t \in \mathcal{T}, p \in \mathcal{P}$ **Number of hours** worked by all temporary workers of profile $p$ on day $d$ and task $t$.

$n_p$ $\forall p \in \mathcal{P}$ **Number of temporary workers** hired with profile $p$.

The objective function is a weighted sum of the penalties listed below.

$\Pi_1^\alpha$ **Temporary workers** penalty. We give $C_p$ penalty points for each temporary worker of profile $p$ we suggest to hire.

$\Pi_1^\beta$ **Qualifications** penalty. We give $(q-\zeta)$ penalty points for each hour spent on a task by an employee who has a qualification $q$.

$\Pi_1^\gamma$ **Equity** penalty. We give a penalty point for each hour of difference between two employees' total numbers of working hours on one day.

$\Pi_1^\delta$ **Ergonomic** penalty. We give a penalty point for each hour in excess compared to the maximum amount of time allowable for a task, per worker and per day.

$\Pi_1^\epsilon$ **Unplanned absence** penalties. We give a penalty point each time we force a regular employee to take a day off, which was not planned by the employee himself (i.e. not defined in the matrix $X$). From the company's point of view, these extra days off are a good way to compensate the overtime work.

Some of the constraints we use need to be linearized. Particularly, we note that a constraint $z = |x - y|$ can be linearized as follows if $z$ appears in the minimization objective:

$$z = |x - y| \Leftrightarrow \begin{cases} z \geq x - y \\ z \geq y - x \end{cases}$$

For the sake of clarity and conciseness, for the rest of the paper we will note $\mathcal{L}(|x - y|)$ the linearization of $|x - y|$.

We can now introduce the linear program MILP1:

$$\min \quad \alpha_1 \Pi_1^\alpha + \beta_1 \Pi_1^\beta + \gamma_1 \Pi_1^\gamma + \delta_1 \Pi_1^\delta + \varepsilon_1 \Pi_1^\varepsilon$$

$$\text{s.t.} \quad \Pi_1^\alpha = \sum_{p \in \mathcal{P}} n_p C_p \qquad (1)$$

$$\Pi_1^\beta = \sum_{e \in \mathcal{E}, d \in \mathcal{D}, t \in \mathcal{T}} (\zeta - Q_{et} x_{edt}) \qquad (2)$$

$$\Pi_1^\gamma = \sum_{e_1, e_2 \in \mathcal{E}, d \in \mathcal{D}} \mathcal{L}\left(\left|\sum_{t \in \mathcal{T}} h_{e_1 dt} - \sum_{t \in \mathcal{T}} h_{e_2 dt}\right|\right) \qquad (3)$$

$$\Pi_1^\delta = \sum_{e \in \mathcal{E}, d \in \mathcal{D}, t \in \mathcal{T}} (h_{edt} - \text{Max}_t) \qquad (4)$$

$$\Pi_1^\epsilon = \sum_{e \in \mathcal{E}, d \in \mathcal{D}} \left( \sum_{t \in \mathcal{T}} X_{edt} - p_{ed} \right) \qquad (5)$$

$$\min^{\text{day}} p_{ed} \le \sum_{t \in \mathcal{T}} h_{edt} \le \max^{\text{day}} p_{ed} \qquad \forall e \in \mathcal{E}, d \in \mathcal{D} \qquad (6)$$

$$\sum_{d \in \mathcal{D}, t \in \mathcal{T}} h_{edt} \le \max^{\text{week}} \qquad \forall e \in \mathcal{E} \qquad (7)$$

$$\sum_{t \in \mathcal{T}} h_{dtp} = 7n_p \qquad \forall p \in \mathcal{P}, d \in \mathcal{D} \qquad (8)$$

$$\sum_{t \in \mathcal{T}} h_{edt} = p_{ed} F_{ed} \qquad \forall e \in \mathcal{E}^{\text{fixed}}, d \in \mathcal{D} \qquad (9)$$
$$ \sum_{e \in \mathcal{E}} h_{edt} + \sum_{p \in \mathcal{P}} P_{pt} h_{dtp} = W_{td} \qquad \forall t \in \mathcal{T}, d \in \mathcal{D} \qquad (10) $$

$$ \sum_{e \in \mathcal{E}} x_{edt} + \sum_{p \in \mathcal{P}} P_{pt} n_p \geq N_{td} \qquad \forall t \in \mathcal{T}, d \in \mathcal{D} \qquad (11) $$

$$ p_{ed} \leq \sum_{t \in \mathcal{T}} x_{edt} \qquad \forall e \in \mathcal{E}, d \in \mathcal{D} \qquad (12) $$

$$ h_{edt} \leq 10x_{edt} \leq \max^{\text{day}} X_{edt} \qquad \forall e \in \mathcal{E}, d \in \mathcal{D}, t \in \mathcal{T} \qquad (13) $$

$$ x_{edt}, p_{ed} \in \{0, 1\} \qquad \forall e \in \mathcal{E}, d \in \mathcal{D}, t \in \mathcal{T} $$

$$ n_{edt}, n_p, h_{dt} \in \mathbb{N}^+ \qquad \forall e \in \mathcal{E}, d \in \mathcal{D}, t \in \mathcal{T}, p \in \mathcal{P} $$

$$ \Pi_{1}^{\alpha}, \Pi_{1}^{\beta}, \Pi_{1}^{\gamma}, \Pi_{1}^{\delta}, \Pi_{1}^{\epsilon} \in \mathbb{R}^{+} $$

The objective function minimizes the weighted sum of all penalties, defined by the constraints (1) to (5) as detailed in the penalty list above. The determination of the weights $\alpha_1$ to $\epsilon_1$ will be discussed in section 6.1. Constraints (6) to (8) are related to legal requirements. Constraints (6) and (7) ensure that an employee cannot work less than four hours nor more than 10 hours during a working day. The total number of hours worked in a week cannot exceed 44 hours (7). The short-term contract employees cannot work more than 35 hours a week; on the other hand, hiring an employee for less than a week is not common and not easy. For these reasons, we make sure that all temporary workers work exactly 7 hours a day (8). As mentioned in section 3, some employees work under a special contract which makes their working time fixed instead of flexible, although their exact tasks during that time still have to be calculated. Constraint (9) ensures that the total number of hours worked by those employees matches exactly their contract.

Constraint (10) ensures that the total number of hours worked by the regular employees and the short term workers matches the workload need. Constraint (11) ensures that the number of people needed at the same time is consistent for each task and day.

Constraints (12) and (13) define the links between $x$, $p$ and $h$, followed by the non-negativity constraints. Constraint (12) ensures that an employee is present on a given day if and only if he has tasks assigned for that day. The left-hand side of the inequality in constraint (13) defines the number of hours worked by each employee per day, making sure that it cannot exceed the maximum number of daily hours required by the law. The right-hand side inequality of the constraint ensures that the abilities, availabilities and work planning constraints (as defined in the data matrix $X$) are met.

## 4.2. MILP2

When MILP1 is solved, we get the number of hours per employee and per day, and the number of temporary workers to be hired with their profiles. These data ($h_{edt}$, $h_{dtp}$ and $n_p$) are then reprocessed in order to include the temporary workers in a new employee set $\mathcal{E}'$, such that $|\mathcal{E}'| = |\mathcal{E}| + \sum_{p \in \mathcal{P}} n_p$. The number of hours $h_{edt}$ obtained at the end of the first step is reprocessed to include the temporary workers as well, to become $H'_{edt}$ (defined on $\mathcal{E}' \times \mathcal{D} \times \mathcal{T}$) and be used as an input for MILP2 – see figure 2.

<figure><img src="image_3.png" /><figcaption>Figure 2: Overview of the inputs and outputs of the weekly timetabling</figcaption></figure>

Besides the sets used in MILP1, we now use the sets $\mathcal{S}$ and $\mathcal{H}$, namely the shifts and hours. MILP2 is thus refining the decisions made in MILP1 by considering the timetabling on a more detailed scale.
MILP2 uses the following input data:

Outputs of step 1:

$H'_{edt} \quad \forall e \in \mathcal{E}', d \in \mathcal{D}, t \in \mathcal{T}$ **Number of hours** worked by employee $e$ on day $d$ and task $t$.

Description of the workload:

$W_{tdh}^1 \quad \forall t \in \mathcal{T}^1, h \in \mathcal{H}, d \in \mathcal{D}$ **Workload** (in working hours) of the tasks defined on a precise time window, per task, per hour and per day.

$W_{td}^2 \quad \forall t \in \mathcal{T}^2, d \in \mathcal{D}$ **Workload** (in working hours) of the tasks defined on a slot, per task and per day.

$S_{tdh} \quad \forall t \in \mathcal{T}^2, h \in \mathcal{H}, d \in \mathcal{D}$ **Slot description.** $S_{tdh} = 1$ if task $t \in \mathcal{T}^2$ can be done on hour $h$ and day $d$, 0 otherwise.

$\text{Max}_{tdh} \quad \forall t \in \mathcal{T}, d \in \mathcal{D}, h \in \mathcal{H}$ **Handling equipment** upper bound. $\text{Max}_{tdh}$ is the amount of **handling equipment available** for task $t$ and day $d$. Its value can be infinite.

Description of the shifts:

$Z_{sh} \quad \forall s \in \mathcal{S}, h \in \mathcal{H}$ **Shift description.** $Z_{sh} = 1$ if hour $h$ is in shift $s$, 0 otherwise.

$D_s \quad \forall s \in \mathcal{S}$ **Shift duration.** $D_s$ is the length of shift $s$, in hours.

The aim of this step is to create a weekly schedule, giving for each employee (temporary workers included) their exact working times. Since the possible shifts are input data, the aim of the current step is to choose the right shift for each employee per day, ensuring that this allocation matches the workload needed. The decision variables used at this step are the following:

$x'_{etdh} \quad \forall e \in \mathcal{E}, d \in \mathcal{D}, h \in \mathcal{H}, t \in \mathcal{T}$ **Percentage of time** spent on task $t$ by employee $e$ on day $d$ and hour $h$.

$y'_{eds} \quad \forall e \in \mathcal{E}, d \in \mathcal{D}, s \in \mathcal{S}$ **Shift allocation.** $y'_{eds} = 1$ if employee $e$ is allocated to shift $s$ on day $d$.

The penalties which are part of the objective function are defined as follows.

$\Pi_2^\alpha$ **Under/over-staffing** penalty. We give a penalty point each time a person is assigned in excess or missing for a task, compared to the needed workload.

$\Pi_2^\beta$ **Hour adjustments** penalty. The number of hours calculated in step 1 did not take the task slots into account; it could therefore need a few adjustments to have a feasible solution for MILP2. We give a penalty point if we have to remove an hour from the working time calculated for an employee on a given day.

$\Pi_2^\gamma$ **Handling equipment** penalty. Knowing the upper bound on the amount of handling equipment, we give a penalty point each time we have to rent an extra machine during one hour to be able to perform a task.

The linear program MILP2 is written as follows:

$$ \min \quad \alpha_2 \Pi_2^\alpha + \beta_2 \Pi_2^\beta + \gamma_2 \Pi_2^\gamma $$

$$ \text{s.t.} \quad \Pi_2^\alpha = \sum_{t \in \mathcal{T}^1, d \in \mathcal{D}, h \in \mathcal{H}} \mathcal{L}\left(\left|W_{tdh}^1 - \sum_{s \in \mathcal{S}, e \in \mathcal{E}} Z_{sh} y'_{eds}\right|\right) + \sum_{t \in \mathcal{T}^2, d \in \mathcal{D}} \mathcal{L}\left(\left|W_{td}^2 - \sum_{h \in \mathcal{H}, e \in \mathcal{E}} S_{tdh} x'_{etdh}\right|\right) \quad (14) $$

$$ \Pi_2^\beta = \sum_{e \in \mathcal{E}, d \in \mathcal{D}, t \in \mathcal{T}} (H'_{edt} - \sum_{h \in \mathcal{H}} x'_{etdh}) \quad (15) $$

$$ \Pi_2^\gamma = \sum_{t \in \mathcal{T}, d \in \mathcal{D}, h \in \mathcal{H}} \left( \sum_{e \in \mathcal{E}} x'_{etdh} - \text{Max}_{tdh} \right) \quad (16) $$

$$ \sum_{s \in \mathcal{S}} D_s y_{eds} = \sum_{t \in \mathcal{T}} H'_{edt} \quad \forall e \in \mathcal{E}', d \in \mathcal{D} \quad (17) $$

$$ \sum_{t \in \mathcal{T}} x'_{etdh} = \sum_{s \in \mathcal{S}} Z_{sh} y_{eds} \quad \forall e \in \mathcal{E}', d \in \mathcal{D}, h \in \mathcal{H} \quad (18) $$

$$ \sum_{s \in \mathcal{S}} y_{eds} \le 1 \quad \forall e \in \mathcal{E}', d \in \mathcal{D} \quad (19) $$
$$x'_{etdh} \leq 1, x'_{etdh} \in \mathbb{R}^+$$

$$y'_{eds} \in \{0, 1\}$$

$$\Pi_2^\alpha, \Pi_2^\beta, \Pi_2^\gamma \in \mathbb{R}^+$$

$$\forall e \in \mathcal{E}', t \in \mathcal{T}, d \in \mathcal{D}, h \in \mathcal{H}$$

$$\forall e \in \mathcal{E}', d \in \mathcal{D}, s \in \mathcal{S}$$

Constraints (14) to (16) define the penalties as described above. We note that constraint (14) matches the employees' presence with the workload need, both for the tasks $t \in \mathcal{T}^1$ defined per hour and the tasks $t \in \mathcal{T}^2$ defined per slot.

Besides constraint (15), constraint (17) also ensures the continuity with step 2, by matching the length of the shifts with the number of hours per employee defined by MILP1. Constraint (18) defines the link between $x'$, $y'$ and $Z$, while (19) makes sure that each employee has no more than one task per hour.

## 5. Daily rostering

The aim of this step is to build the detailed schedule for a given day of the week. While MILP1 and MILP2 are meant to be used every week to set up the following week's planning, this linear program is supposed to be run every morning to plan the upcoming day.

Depending on the rostering requirements, the time scale can be further refined to use time windows smaller than an hour (in our tests for example, we use 15 minutes time windows). We recall from section 3 that these time windows are called intervals and defined on the set $\mathcal{I}$. The outcome of MILP3 is thus an assignment of tasks to employees for each interval.

Some information may be adjusted before running MILP3. For instance, the temporary workers suggested by MILP1 have been hired and we now know their exact qualifications; the employees who are absent do not need to be considered; the manager also has the possibility to make a few changes in the timetable produced by MILP2. We therefore note $\mathcal{E}''$ the new set of employees. The data about the workload also evolves; it is more precise than (and possibly very different from) previous available forecasts.

The interval structure and the given day being known, we can reprocess the output of MILP2 $x'_{etdh}$, to obtain the matrix $X''$ defined on $\mathcal{E}'' \times \mathcal{T} \times \mathcal{I}$. $X''_{eti}$ gives the percentage of time spent on task $t$ by employee $e$ during interval $i$, as calculated by MILP2 and possibly adjusted by the manager if needed. Similarly, we reprocess the output of MILP2 $y'_{eds}$ into the matrix $Y''_{es}$ defined on $\mathcal{E}'' \times \mathcal{S}$, which contains the shift allocations planned for the given day.

<figure><img src="image_4.png" /><figcaption>Figure 3: Overview of the inputs and outputs of MILP3</figcaption></figure>

The other input data needed are similar to the ones used in the previous steps, but they are now defined on intervals rather than hours, and for the given day only. Figure 3 summarizes the mechanism of MILP3.

To summarize, we have the following data as inputs for MILP3:

$X_{eti}$ $\forall e \in \mathcal{E}'', t \in \mathcal{T}, i \in \mathcal{I}$ Binary matrix similar to $X_{edt}$ described in section 4.1, containing information about the presence of the employees, their abilities, and the work volume, with a precision by intervals inside the given day.
$X''_{eti} \quad \forall e \in \mathcal{E}'', t \in \mathcal{T}, i \in \mathcal{I}$ **Task allocation** as calculated by MILP2 and possibly adjusted by the manager.

$Y''_{es} \quad \forall e \in \mathcal{E}'', s \in \mathcal{S}$ **Shift allocation** as calculated by MILP2 and possibly adjusted by the manager.

$W_{ti}^1 \quad \forall t \in \mathcal{T}^1, i \in \mathcal{I}$ **Workload** per task defined per interval.

$W_t^2 \quad \forall t \in \mathcal{T}^2$ **Workload** for the tasks defined per slot.

$S_{ti} \quad \forall t \in \mathcal{T}^2, i \in \mathcal{I}$ **Slot description.** $S_{ti} = 1$ if task $t \in \mathcal{T}^2$ can be done during interval $i$, 0 otherwise.

$\text{Max}_{ti} \quad \forall t \in \mathcal{T}, i \in \mathcal{I}$ **Handling equipment upper bound.** $\text{Max}_{ti}$ is the number of machines available for task $t$ during interval $i$. This value can be infinite.

$\text{Max}_t \quad \forall t \in \mathcal{T}$ **Maximum amount of time (in intervals) that a worker can spend per day on task $t$.** This value enables one to respect safety and ergonomics principles.

This step uses two decision variables:

$y_{es}'' \quad \forall e \in \mathcal{E}'', s \in \mathcal{S}$ **Shift allocation.** $y_{es}'' = 1$ if employee $e$ is affected on shift $s$, 0 otherwise.

$x_{eti}'' \quad \forall e \in \mathcal{E}'', t \in \mathcal{T}, i \in \mathcal{I}$ **Task allocation.** $x_{eti}'' = 1$ if employee $e$ works on task $t$ during interval $i$, 0 otherwise.

The following penalties are part of the objective function:

$\Pi_3^\alpha$ **Shift changes** penalty. We give a penalty point per employee whose shift has been changed, compared to the plan made at the end of MILP2.

$\Pi_3^\beta$ **Task changes** penalty. We give a penalty point each time we have to change the task of an employee, compared to what was planned at the end of MILP2.

$\Pi_3^\gamma$ **Knowing the handling equipment** upper bound, we give a penalty for each interval for which an additional handling machine has to be rent to be able to perform a task.

$\Pi_3^\delta$ **Ergonomy** penalty. We give a penalty point for each interval in excess for a worker, compared to the maximum amount of time per day defined for his task.

We can now introduce the linear program MILP3:

$$ \min \quad \alpha_3 \Pi_3^\alpha + \beta_3 \Pi_3^\beta + \gamma_3 \Pi_3^\gamma + \delta_3 \Pi_3^\delta $$

$$ \text{s.t.} \quad \Pi_3^\alpha = \sum_{e \in \mathcal{E}'', s \in \mathcal{S}} \mathcal{L}(|Y_{es}'' - y_{es}''|) \quad (20) $$

$$ \Pi_3^\beta = \sum_{e \in \mathcal{E}'', t \in \mathcal{T}, i \in \mathcal{I}} \mathcal{L}(|X_{eti}'' - x_{eti}''|) \quad (21) $$

$$ \Pi_3^\gamma = \sum_{t \in \mathcal{T}, i \in \mathcal{I}} \left( \sum_{e \in \mathcal{E}''} x_{eti}'' \right) - \text{Max}_{ti} \quad (22) $$

$$ \Pi_3^\delta = \sum_{e \in \mathcal{E}''}, \forall t \in \mathcal{T} \left( \sum_{i \in \mathcal{I}} x_{eti}'' \right) - \text{Max}_t \quad (23) $$

$$ \sum_{e \in \mathcal{E}''} y_{et_1 i} = W_{t_1 i}^1 \quad \forall t \in \mathcal{T}^1, i \in \mathcal{I} \quad (24) $$

$$ \sum_{e \in \mathcal{E}''}, \forall i \in \mathcal{I} S_{t_2 i} y_{et_2 i} = W_{t_2}^2 \quad \forall t \in \mathcal{T}^2 \quad (25) $$

$$ x_{eti}'' \le X_{eti} \quad \forall e \in \mathcal{E}''}, \forall t \in \mathcal{T}, i \in \mathcal{I} \quad (26) $$

$$ x_{eti}'' = \sum_{s \in \mathcal{S}} Z_{si} y_{es}'' \quad \forall e \in \mathcal{E}''}, \forall t \in \mathcal{T}, i \in \mathcal{I} \quad (27) $$

$$ \sum_{t \in \mathcal{T}} x_{eti}'' \le 1 \quad \forall e \in \mathcal{E}''}, \forall t \in \mathcal{T}, i \in \mathcal{I} \quad (28) $$

$$ \sum_{s \in \mathcal{S}} y_{es}'' \le 1 \quad \forall e \in \mathcal{E}''} \quad (29) $$

$$ x_{eti}'' \in \{0, 1\} \quad \forall e \in \mathcal{E}''}, \forall t \in \mathcal{T}, i \in \mathcal{I} $$

$$ \Pi_3^\alpha, \Pi_3^\beta, \Pi_3^\gamma, \Pi_3^\delta \in \mathbb{R}^+ $$

Constraints (20) to (23) define the penalties (shift changes, task changes, handling equipment, ergonomy) as described above. Constraints (24) and (25) match the workers to the workload, for the tasks from $\mathcal{T}^1$
defined per hour and for the tasks from $T^2$ defined by slots, respectively. Constraint (26) checks that the tasks are allocated to the employees only when it is possible. Finally, constraints (28) and (29) ensure that each employee has no more than one shift per day, and one task per interval.

# 6. Numerical results

In this section, the linear programs detailed previously are tested to assess their performances in different situations. The results described in section 6.1 have been obtained using industrial data, while section 6.2 explains our results on a benchmark data set made available by Günther et al. [14, 15]. The tests in section 6.3 are carried out on instances generated for testing purposes.

Unless indicated otherwise, the linear programs were run with IBM ILOG CPLEX Optimizers 12.2, on a personal computer with a 2.40GHz processor and 4.00GB of RAM.

## 6.1. Industrial instances

30 different data sets from real-life industrial cases were tested. Three different warehouse teams with different configurations were considered, and the decision-support tool was tested for 10 weeks in each team. The different configurations are as follows:

**Configuration 1** has 5 days, 16 hours, 64 intervals, 17 possible shifts, 19 tasks, 11 employees, 18 temporary workers profiles. This warehouse team has only one big client. The products arrive in containers from overseas, and the arrival of containers creates a peak of activity for the unloading-related tasks. One single task can therefore represent the major part of the workload, which makes the workload distribution geometric. The execution time is 5 seconds on the average for this configuration.

**Configuration 2** has 5 days, 16 hours, 64 intervals, 12 possible shifts, 44 tasks, 15 employees, 1 temporary worker profile. This warehouse has several smaller clients. It makes the number of tasks higher, and statistically smooths the occurrences of unloading and preparation tasks, therefore the workload distribution is normal. It does not vary much from one day to another, therefore this team almost never uses temporary workers – this is why they define only one temporary worker profile. The execution time is 10 seconds on the average for this configuration.

**Configuration 3** has 6 days, 12 hours, 24 intervals, 36 possible shifts, 13 tasks, 2 employees, 8 temporary worker profiles. This activity is only seasonal, therefore the 2 regular employees handle the management tasks, and the operational work is done by up to 200 temporary workers of 8 different profiles. The execution time is 8 seconds on the average for this configuration.

Two instances, typical of configurations 1 and 2, and made anonymous for confidentiality concerns, are available at http://pagesperso.g-scop.grenoble-inp.fr/~gaujalg/TimeTabling/.

The results we obtained on those two instances are displayed in table 1 – the figures for MILP3 are the mean of the results obtained for the 5 days. More details on solutions, including the penalty points and results on each day of the week (via MILP3), can be found online along with the instances.

<table><caption>Table 1: Results obtained on two instances available online</caption><thead><tr><th rowspan="2">Instance</th><th colspan="3">Execution time (seconds)</th><th colspan="3">Value of the objective function</th></tr><tr><th>MILP1</th><th>MILP2</th><th>MILP3</th><th>MILP1</th><th>MILP2</th><th>MILP3</th></tr></thead><tbody><tr><td>instance1</td><td>2,57</td><td>1,53</td><td>0,05</td><td>5 900</td><td>40 388</td><td>704</td></tr><tr><td>instance2</td><td>5,62</td><td>2,05</td><td>0,14</td><td>8 290</td><td>35 274</td><td>889</td></tr></tbody></table>

Our industrial partner favored a free integer programming solver, for economical reasons. Thus for company use, ours methods are implemented with lp_solve 5.5.2, a free MILP solver under the GNU LGP license.
With CPLEX, for all the instances tested, the computing times were below 10 seconds. The computation
times are much higher with lp_solve for the same instances. For practical reasons, the computation of lp solve
is interrupted after a short period of time, and we keep the best feasible solution found during its search.
For our instance1, setting up a time-out at 20 seconds gives a 40% gap to optimal, and waiting for 2 minutes
reduces this gap to 15% for MILP1 (which is the longer step in terms of execution time) – see figure 4. The
company was satisfied with the quality of the solution obtained at this point, even though it is not optimal.

<figure><img src="image_5.png" /><figcaption>Figure 4: Gap to optimal on MILP1 according to the time-out set in lp_solve</figcaption></figure>

In our industrial context, the logistics provider was satisfied with the quality of the timetable the managers
could obtain manually; the problem was that the operation was extremely long and tedious. The main
objective was therefore to automate that process, but keeping an outcome similar to the one the manager
would have obtained manually. The soft constraints were created in this perspective: listing the criteria
that make a timetable better than another from the manager's point of view. These soft constraints being
weighted in our objective functions, the manager has the possibility to play with the parameters until he
gets the solution he is most satisfied with. The managers who are experienced in manual timetabling can
therefore choose the settings with a trial and error approach.

From a theoretical point of view, using a weighted objective function raises some issues about the best
way to fix the parameters for non-homogeneous criteria – see Pöyhönen and Hämäläinen [23]. Methods like
UTA (additive utilities<fnref n="1" />) or AHP (Analytical Hierarchy Process) can be used to determine the weights; the
interested reader can refer to the survey on multiple criteria decision analysis by Figueira et al. [12].

Here, the weights in the objective function are determined in an iterative process, using interviews and
expert opinions, together with the trial-and-error test runs, prior to real planning runs. During these test
runs, the weights are set such that the solution proposed by our tool is not very different from what a
manager would have planned himself. We note that such iterative procedures can be found in the literature
for industrial applications (see Günther and Nissen [15]). In this practical situation, the fact that the weight
settings are not fixed is perceived as an asset by the end user, who uses them as an actual managing tool.
It offers more flexibility, for instance to change the relative importance of the soft constraints depending on
the nature of the upcoming activity.

The outputs are the weekly timetable (see figure 5 as an example) and the daily roster (figure 6). They
are presented in a table format, ready to be used by the manager. The value added compared to the former
situation is the speed of the timetable operation: the automated timetable is generated in a few seconds,
whereas the manual process was tedious and time consuming and took up to 4 hours.

<footnote n="1">¹UTA stands for *Utilités Additives*, in French.</footnote>
<figure><img src="image_6.png" /><figcaption>Figure 5: Weekly timetable, in the format used by the manager</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 6: Daily roster, in the format used by the manager. Each color represents a task.</figcaption></figure>

## 6.2. Benchmark

In order to assess the performance of our model compared to existing benchmarks, we tested it on the instances provided by Günther and Nissen [14, 15]. This benchmark (available at http://www.tu-ilmenau.de/fileadmin/media/wid/forschung/TestproblemePersonaleinsatzplanung/) comes from a real-world logistics case. Since the context is similar to ours, this data set matches the main characteristics of our problem, as described in section 2.1: very diverse skills, flexible working hours, uneven workload.
With 65 employees, 9 tasks and 13 shift types to be scheduled over 7 days, this set of data is different from the instances tested in section 6.1. It has half as many tasks but up to 6 times more employees, and the scheduling period is two days longer. Note that the objective function used by Günther and Nissen is also different. They penalize under-staffing and the number of job changes as we do, but they distinguish between two cases for over-staffing: over-staffing at a period when the workload needed (i.e. demand) is zero is seen as much worse than over-staffing when there is a positive demand. All the other criteria we used in our objective functions are not taken into account by Günther and Nissen. This is due to how their model's constraints are related to the daily rostering only, whereas we use three different models with different time scales in our approach. Solving three MILPs sequentially requires extra constraints to link the different steps with each other (e.g. the output of MILP1 is included in a constraint in MILP2).

For this reason, we decided to run our model keeping the same coefficients of the objective function used in the previous section. Hence, it is important to note that we do not optimize exactly the same criteria as Günther and Nissen. This test only aims at checking that we can process a different type of data in a reasonable amount of time. Nevertheless, in order to have some comparison points, we reprocessed our output in order to evaluate it with Günther and Nissen's criteria. The results are shown in table 3.

<table><caption>Table 3: Comparison with Günther and Nissen's results</caption><thead><tr><th></th><th>Execution time</th><th>over-staffing when no demand</th><th>over-staffing when demand &gt; 0</th><th>under-staffing</th><th>number of job changes</th></tr></thead><tbody><tr><td>Our results</td><td>2.59 min</td><td>7 995</td><td>795</td><td>0</td><td>664</td></tr><tr><td>Günther's manual timetabling</td><td>unknown</td><td>33 795</td><td>14 610</td><td>20 130</td><td>0</td></tr><tr><td>Günther's best solution</td><td>about 50 min</td><td>7 245</td><td>28 395</td><td>7 355</td><td>1 502</td></tr></tbody></table>

The differences observed in table 3 in terms of objective function values is due to the differences in the constraints of the two models. Our model does not allow under-staffing at the daily level, which explains why we get 0 on that criterion. Günther and Nissen's model also gives work to each and every employee, while our model can assign days off rather than creating over-staffing. But we see that our sequential method gives results in about 3 minutes, while Günther and Nissen's particle swarm optimization requires an execution time of about 50 minutes. It meets our goal of providing the logistics managers with a decision tool that can be used daily without a long execution time.

## 6.3. Numerical results from the generated instances

The previous section demonstrates that the weekly and daily timetables for real size problems can be solved easily and in a fast manner.

Real-life problems are actually very constrained: if some employees have shifts fixed beforehand, or are absent for one or two days, the solution space is reduced and the problem is easier to solve. Our goal in the current section is to show the performance and limits of the models detailed previously, regarding some of the input parameters that can make the situation more complicated.

We will especially focus on the workload variations and the workforce abilities. Since workload variations are one of the main challenges warehouses have to cope with, it is important to check how the model behaves when the workload changes. One of the main tools to absorb these variations is the adjustment of the workforce skills; therefore, we also vary this piece of data in our test. One goal is to see what could be a good policy for the employees' training in the warehouse.

The weights linked to soft constraints which are not related to the workload ($\beta_1, \gamma_1, \delta_1, \epsilon_1, \gamma_2, \gamma_3$ and $\delta_3$) are put to zero. We assume the remaining weight parameters are equally important, and hence fix $\alpha_1 = \alpha_2 = \beta_2 = \alpha_3 = \beta_3 = 1$.

The data matrices representing the workload ($W_{td}^2$), the temporary workers profiles ($P_{pt}$) and the abilities (part of $X_{edt}$ or $X_{eti}$) are generated randomly. Each dimension of the given matrix is generated using a
<figure><img src="image_8.png" /><figcaption>Figure 7: Matrix $P_{pt}$ with a geometric distribution on one dimension and a normal distribution on the other</figcaption></figure>

normal, geometric or uniform distribution function. As an example, figure 7 displays a temporary workers profile matrix $P_{pt}$. In this figure, the number of tasks mastered by each employee (given in the rows) follows a normal distribution, while the number of employees who can perform each task (given in the columns) is randomly drawn from a geometric distribution. Similarly, we can generate different $P_{pt}$ by changing the type of distribution (normal, geometric or uniform) for the columns or the rows.

Considering that a temporary worker is likely to be paid more if he has more skills, we define the temporary workers cost $C_p$ as the number of tasks mastered by the worker $p$.

We set $\mathcal{T}^1 = \emptyset$ and $\mathcal{T}^2 = \mathcal{T}$, so that the workload is entirely defined per slots. We set the slot description matrix $S$ such as $S_{thd} = 1$ for all $t \in \mathcal{T}, h \in \mathcal{H}, d \in \mathcal{D}$. Once $W_{tdh}^2$ is generated as described above, the workload $W_{td}$ and the number $N_{td}$ of people needed at the same time are deduced easily.

As we have seen with the industrial case study, most of the input parameters (e.g. fixed work times $F_{ed}$ and planned absences) are context dependent. Therefore, such input parameters (listed below) are fixed in all tested instances:

**Matrix X.** The planned absences narrow the decision space. Therefore we assume that all the employees $e \in \mathcal{E}$ are available for all the time units $t \in \mathcal{T}$ and $i \in \mathcal{I}$. Similarly, we assume that all tasks $t \in \mathcal{T}$ need to be carried out during all the time intervals considered.

**Non-binary qualifications $Q_{et}$**. This matrix only plays a role in one soft constraint (penalty $\Pi_1^\alpha$ defined in constraint 1). For the sake of simplicity, we use only binary qualifications for our tests, thus we set $Q_{et} = 1$ if the employee $e$ is qualified for the task $t$, 0 otherwise.

**Safety and ergonomics upper bound $\text{Max}_t$.** This vector is also only related to soft constraints. We relax it setting $\text{Max}_t = \infty$ for all $t \in \mathcal{T}$.

**Handling equipment upper bounds $\text{Max}_{tdh}, \text{Max}_{ti}$**. Similarly, these matrices are only related to soft constraints. We relax them setting $\text{Max}_{tdh} = \text{Max}_{ti} = \infty$ for all $t \in \mathcal{T}, d \in \mathcal{D}, h \in \mathcal{H}, i \in \mathcal{I}$.

**Fixed work times $F_{ed}$**. Defining some shifts beforehand also narrows the decision space, thus we set $\mathcal{E}^{\text{fixed}} = \emptyset$, which means that $F_{ed}$ does not need to be defined.
**Shift description Z<sub>sh</sub>.** This matrix is built enumerating all legally possible shifts. The shift duration D<sub>s</sub>
is easily obtained from the matrix Z.

6.3.1. *Tests on weekly timetabling*

One set of tests was carried out on MILP1 to study the impact of the abilities matrix shape on the execution time. The size of the instances were as follows: 10 employees, 8 tasks, 8 temporary worker profiles, 5 days, 24 hours, 115 possible shifts. 30 different abilities matrices were generated, using normal, geometric and uniform distributions. The normal distribution models a case where 80% of the employees can handle 20% of the tasks; it is the situation we encountered most often in our real-life cases. The uniform distribution represents a case which can be seen as fairer: all the employees master the same number of tasks. The geometric distribution models a situation where most of the workers are hired for short periods of time, and therefore master only a few tasks. The organization relies upon a very small number of long-term employees to handle all the complex tasks.

Each matrix is tested with 40 different workload distributions. Each dot on figure 8 shows the average computation time of MILP1 for these 40 different runs for a given abilities matrix. This average computation time is displayed as a function of the total number of abilities in the ability matrix.

<figure><img src="image_9.png" /><figcaption>Figure 8: Execution time as a function of the total number of abilities</figcaption></figure>

The result is shown in figure 8. On one extreme, when the ability matrix is near empty (low total number of abilities), the problem size is highly reduced, therefore the solution is obtained faster. On the other extreme, when the ability matrix is nearly full (high total number of abilities), it is easy to find a solution without any temporary workers, so the problem can be solved quickly as well. The most complex problems are for a half-full ability matrix, because the problem in this situation can become highly combinatorial. The instances generated from a geometric distribution regarding the tasks are especially difficult, because they contain one or two tasks, which have a high workload compared to the others: if many employees are qualified for these tasks, there are many possible combinations for the allocation of tasks to employees. Therefore the search of a solution can fail; some of these instances cannot be solved with our test configuration due to a memory overflow.

On the contrary, the instances generated from normal distributions are faster to solve. Note that the computation times needed to solve the industrial instances were short, because the real-life data distributions were close to normal ones.

Since the other penalties are left aside, the only element optimized in the objective function of MILP1
is the number of temporary workers hired. Figure 9 shows how the total number of abilities influences this
objective. We can see that training multi-skilled employees brings a real added value for the company up to
50% of the qualification matrix. It offers no further benefits, however, to increase this rate from 60% to 70% or higher.

<figure><img src="image_10.png" /><figcaption>Figure 9: Number of temporary workers hired as a function of the total number of abilities</figcaption></figure>

The linear program MILP1 determines the number of hours worked by each employee per day and per task. MILP2 refines this decision by choosing the exact shifts (starting and ending times) for each employee. Since the soft constraints are left aside and the workload used is only defined by slots, the problem modeled by MILP2 can be solved with a short computation time. With the test settings described previously, MILP2 can be solved in less than one second on all generated instances.

### 6.3.2. Tests on daily rostering

As explained in section 5, MILP3 is meant to be run every morning to plan the upcoming day, with input data that can possibly be very different from the ones used in the weekly timetable generation. Therefore the most important criteria to assess for MILP3 is the robustness of the outcome, when the input data change between runs. We therefore run MILP1 and MILP2 in sequence, with a set of instances which can be computed in a reasonable time (ability matrix filled to 60%), and different workload distributions (geometric and normal). Those were the two distribution types we observed in our real-life situations, as explained in section 6.1 (see configurations 1 and 2). The workload matrix $W_{ti}^2$ is created by increasing or reducing the workload used in MILP2 ($W_{tdh}^2$) for each task by a given percentage. MILP3 is solved with this new workload as an input and with all the other input data left unchanged. We then look at the values of $\Pi_3^\alpha$ (number of employees whose shifts have been changed, compared to the plan made at the end of MILP2) and $\Pi_3^\beta$ (total number of times an employee's task has been changed, compared to what was planned at the end of MILP2). The length of an interval is set to 15 minutes, which means we consider 96 intervals in total.

The results of these tests are shown in figures 10 and 11 for $\Pi_3^\alpha$ and $\Pi_3^\beta$, respectively. For improved readability, the values have been turned into percentages. Each dot is an average obtained from the results of 20 different instances, and the vertical lines show the corresponding standard deviation.

We observe that the number of changed shifts increases linearly for the geometric workload distributions: with 30% change in the workload, all the shifts need to be changed. Normal distributions are very sensitive to small workload changes, and reach stability very fast. Changing 50% of the shifts can handle a workload change of 5% to 30%. As shown in figure 10, the tasks changes stay below 10%: they are more constrained, since the qualification matrix does not allow to allocate an employee to any task. The number of task changes increases linearly for both distributions, which behave similarly for up to 10% of changes. For higher percentages, the normal distributions are the most robust again.
<figure><img src="image_11.png" /><figcaption>Figure 10: Shift changes as a function of the workload change</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 11: Tasks changes as a function of the workload change</figcaption></figure>

The daily schedule recreated by MILP3 from the weekly timetable can therefore stay close to the original plan, if the changes made in the workload are below 30%. Geometric distributions are less robust, since they contain one or two tasks which are very heavy compared to the others, and thus more difficult to redistribute without changing the employees' pre-planned shifts.

In the industrial context, it would thus be interesting to have workload distributions that are rather normal than geometric. The manager could try to negotiate with his client in order to get a better forecast of the upcoming volumes: since a better forecast leads to a better timetable, it can also help reducing the costs the client is charged for. The other option for the manager is to try and consolidate the flows, for instance by having several clients served by the same warehousing team, in order to further smoothen the workload.

## 7. Conclusion

The paper at hand proposes a new decomposition approach to solve complex timetabling problems on different time scales (weekly and daily). Three mixed integer linear programs are solved sequentially in order to achieve both weekly timetabling and daily rostering in an integrated manner. We are thus able to solve a real-life, complex industrial problem within a reasonable amount of time, providing important time savings compared to the manual scheduling process. The solution proposed by the decision-support tool also offers
improvements compared to the manual schedule that mainly focused on feasibility: it helps in reducing the number of temporary workers and in making better use of the qualifications of each employee.

One prospect for future work would be to support the managers in setting their parameters, particularly by automatically tuning these optimization parameters through machine learning methods (see e.g. Jurisica [16]).

Note that, although the model was designed for a logistics platform, it could be adapted to other service systems, such as mail processing or cleaning companies. Another opportunity for future research would be to apply this decomposition method to similar problems.

Finally, we provide new real-life instances that can be used to benchmark different scheduling techniques. It would be interesting to compare, for each of those instances, the performance of our method with techniques like column generation, the decomposition methods described by Detienne et al. [8] and Naudin et al. [22], or constraint programming.

## References

[1] Jonathan F. Bard, Canan Binici, and Anura H. de Silva. Staff scheduling at the United States Postal Service. *Computers and Operations Research*, 30(5):745-771, 2003.

[2] Peter Brucker, Rong Qu, and Edmund Burke. Personnel scheduling: models and complexity. *European Journal of Operational Research*, 210(3):467-473, 2011.

[3] Edmund K. Burke, Patrick De Causmaecker, Greet Vanden Berghe, and Hendrik Van Landeghem. The state of the art of nurse rostering. *Journal of Scheduling*, 7:441-499, 2004.

[4] Gerard M. Campbell and Moustapha Diaby. Development and evaluation of an assignment heuristic for allocating cross-trained workers. *European Journal of Operational Research*, 138(1):9-20, 2002.

[5] J. Arturo Castillo-Salazar, Dario Landa-Silva, and Rong Qu. A survey on workforce scheduling and routing problems. In *Practice and Theory of Automated Timetabling*, 2012.

[6] S. Dahmen and M. Rekik. Solving multi-activity personalized shift scheduling problems with a hybrid heuristic. Technical report, Interuniversity Research Centre on Enterprise Networks, Logistics and transportation, 2012.

[7] Patrick De Causmaecker, Peter Demeester, Greet Vanden Berghe, and Bart Verbeke. Analysis of real-world personnel scheduling problems. In *Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling*, pages 183-198, 2004.

[8] Boris Detienne, Laurent Péridy, Éric Pinson, and David Rivreau. Cut generation for an employee timetabling problem. *European Journal of Operational Research*, 197(3):1178-1184, 2009.

[9] Guy Eitzen, David Panton, and Graham Mills. Multi-skilled workforce optimisation. *Annals of Operations Research*, 127:359-372, 2004.

[10] Andreas T. Ernst, Houyuan Jiang, Mohan Krishnamoorthy, Bowie Owens, and D. Sier. An annotated bibliography of personnel scheduling and rostering. *Annals of Operations Research*, 127:21-144, 2004.

[11] Andreas T. Ernst, Houyuan Jiang, Mohan Krishnamoorthy, and David Sier. Staff scheduling and rostering: A review of applications, methods and models. *European Journal of Operational Research*, 153:3-27, 2004.

[12] José Figueira, Salvatore Greco, and Matthias Ehrgott. *Multiple criteria decision analysis: state of the art surveys*. Kluwer Academic Publishers, 2004.
[13] Douglas D. Graham. Warehouse of the future. *Frontline Solutions*, 4:20–26, 2003.

[14] Maik Günther and Volker Nissen. A comparison of three heuristics on a practical case of sub-daily staff scheduling. In *8th International Conference on the Practice and Theory of Automated Timetabling*, pages 224–240, 2010.

[15] Maik Günther and Volker Nissen. Sub-daily staff scheduling for a logistics service provider. *KI - Künstliche Intelligenz*, 24:105–113, 2010.

[16] Igor Jurisica. Building better decision-support systems by using knowledge discovery. In *Proceedings of the 63rd ASIS annual meeting*, volume 37, pages 281–291, 2000.

[17] Peter Klaus. The assessment of competitive intensity in logistics markets. *Logistics Research*, 3:49–65, 2011.

[18] Quentin Lequy, Mathieu Bouchard, Guy Desaulniers, François Soumis, and Beyime Tachefine. Assigning multiple activities to work shifts. *Journal of Scheduling*, 15:239–251, 2012.

[19] Quentin Lequy, Guy Desaulniers, and Marius M. Solomon. A two-stage heuristic for multi-activity and task assignment to work shifts. *Computers & Industrial Engineering*, 63(4):831–841, 2012.

[20] Nysret Musliu, Johannes Gärtner, and Wolfgang Slany. Efficient generation of rotating workforce schedules. *Discrete Applied Mathematics*, 118:85–98, 2002.

[21] Stuart Naish and Peter Baker. Materials handling – fulfilling the promises. *Logistics & Transport Focus*, 6:18–23, 2004.

[22] Édith. Naudin, Peter Y.C. Chan, M. Hiroux, T. Zemmouri, and G. Weil. Analysis of three mathematical models of the staff rostering problem. *Journal of Scheduling*, 15:23–38, 2012.

[23] Mari Pöyhönen and Raimo P. Hämäläinen. On the convergence of multiattribute weighting methods. *European Journal of Operational Research*, 129:569–585, 2001.

[24] Dieter W. Rebitzer. The European logistics market. *Europe Real Estate Yearbook*, pages 112–121, 2007.

[25] Andrea Schaerf and Amnon Meisels. Solving employee timetabling problems by generalized local search. In *Advances in Artificial Intelligence*, volume 1792 of *Lecture Notes in Computer Science*, pages 380–389. Springer Berlin/Heidelberg, 2000.

[26] Pieter Smet and Greet Vanden Berghe. A matheuristic approach to the shift minimisation personnel task scheduling problem. In *Practice and Theory of Automated Timetabling*, 2012.

[27] Jorne Van den Bergh, Jeroen Beliën, Philippe De Bruecker, Erik Demeulemeester, and Liesje De Boeck. Personnel scheduling: A literature review. *European Journal of Operational Research*, 226(3):367–385, 2013.

[28] Sophie van Veldhoven, Gerhard Post, and Egbert van der Veen. Days off scheduling – a 2-phase approach to personnel rostering. In *Practice and Theory of Automated Timetabling*, 2012.

[29] Lin Wan. *Staff Planning and Scheduling in the Service Industry: An Application to US Postal Service Mail Processing and Distribution Centers*. PhD thesis, University of Texas, 2005.

[30] Anthony Wren. Scheduling, timetabling and rostering – a special relationship? In Edmund Burke and Peter Ross, editors, *Practice and Theory of Automated Timetabling*, volume 1153 of *Lecture Notes in Computer Science*, pages 46–75. Springer Berlin / Heidelberg, 1996.