03022020  Issue 2/2020 Open Access
The flexible break assignment problem for large tour scheduling problems with an application to airport ground handlers
 Journal:
 Journal of Scheduling > Issue 2/2020
Important notes
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
In most personnel scheduling problems, workforce demand is a function of the number of required tasks per period and, depending on the application, can have extremely high variance. To optimally cover demand, a tour scheduling problem needs to be solved to determine the days off (daysoff scheduling) and shift assignments (shift scheduling) for each worker on each day of the planning horizon. Once the days off are fixed, there are two immediate ways to modify a worker’s tour when demand is highly variable: adjust the start time and length of a shift, and redo the assignment of breaks to shifts. Although much has been written about the first option, there is a noticeable absence in the literature when it comes to analyzing different break regulations, especially in the context of tour scheduling. Moreover, there is little practical evidence that planners have exploited the benefits offered by such regulations when it comes to better matching supply with demand.
One of the objectives of this paper is to show how break assignments can be used to improve the scheduling of airport ground handlers. When a flight arrives at an airport, baggage and cargo must be transferred to the terminal, handicapped passengers must be transported to either their next flight or the baggage area, and the aircraft must be prepared for its next trip. These functions fall under the heading of
ground handling and, depending on the number of arriving passengers and the distance flown, may require a dozen or more service workers to perform (Ashford et al.
1997). Personnel costs are the largest expense faced by the service provider and must be managed carefully in today’s competitive environment. Ground handling as well as many other personnel scheduling problems requires the explicit assignment of shifts and days off to individual employees rather than to a generic workforce. This means that information on individual skills, availability, and overtime balances must be taken into account (e.g., see Love and Hoey
1990). In ground handling, the difference between peak and nonpeak demand can be as large as three to one over the day. Meeting the demand without an excess of under or overcoverage is an extremely challenging task. To the best of our knowledge, this paper is the first to analyze the full range of break options in tour scheduling.
Advertisement
The approach we take involves decomposing the full problem into a tour scheduling problem (TShP) and a break assignment problem (BAP). By separating the two, we create a framework in which different break models can be computationally evaluated without controlling for the basic tour scheduling parameters. As standalone problem, the BAP arises in daily break planning as well as intraday break assignment and the presented implicit models can incorporate a hierarchical multiskill workforce. Other decomposition approaches based on branch and price turned out to be intractable for such largescale realworld application considering individual workers and complex break regulations. The presented heuristic is flexible enough to be adopted to many realworld tour scheduling problems and general enough to incorporate all kinds of break regulations. To the best of our knowledge, there is no approach present in the literature to tackle a TShP of the size and complexity resulting from our ground handling application. The majority of the work in the area of breaks has focused on model development and the design of computational techniques for reducing problem size and runtimes in the context of shift scheduling. The primary example centers on the the implicit modeling of breaks in shift scheduling (see Aykin
1996, Bechtold and Jacobs
1990, Rekik et al.
2010). Our decomposition approach enables us to fully investigate the various implicit formulations in the wider context of tour scheduling and a hierarchical workforce. As part of the developments, we introduce a classification scheme for the BAP and present a complexity analysis of all major variations. Based on the different properties of the accompanying models, the flexibility and operational value of each is evaluated using data from a large European ground handling company. For applications where breaks are assigned dynamically over the day, e.g., for fast food, ground handling, and mail processing operations, the decomposition approach provides an upper bound on costs. In such environments, the break assignment model can be used in a rolling horizon manner to support reactive planning.
In order to generate tours, we rely on templates that define a set of permissible shifts for each day of the planning horizon. The templates also include the option for a day off and therefore allow us to consider the availability of each employee each day of the week. To show the impact of shift starting time and shift duration flexibility and its interaction with break flexibility, we investigate two different scenarios. In the case of high shift flexibility, when early and late shifts are considered, we get more than 1400 possible shifts for the different combinations of starting times and working hours alone. This is in contrast to less than 30 possible shifts for the low flexibility case. As expected, we show that model size is strongly correlated with our ability to solve realistic instances in a timely manner.
The main contributions of this paper are as follows.
The paper is organized as follows. In Sect.
2, we review the literature on ground handling operations and break assignment models. This is followed in Sect.
3 with a detailed description of the full problem, including an example and definitions related to templates and tours. An integrated mixedinteger programming (MIP) formulation of the tour scheduling problem based on weekly templates is presented in “Appendix
B”. In Sect.
4, we introduce a classification scheme for the different BAPs and analyze the complexity of each. The decomposition approach is highlighted in Sect.
5 along with an efficient implicit model for break assignments for a hierarchical workforce. This is followed by a computational study in Sect.
6 where the various break assignment models and the decomposition procedure are empirically evaluated. We close with some insights and observations on the proposed methodology.

A classification scheme and a complexity analysis of the BAP for all practical variations.

The presentation of three efficient implicit formulation for assigning breaks to shifts in a manner that accounts for hierarchical skill levels.

A heuristic decomposition procedure for scheduling a hierarchical workforce that can accommodate all permissible break placements in a shift (the heuristic supports reactive planning of breaks in response to unforeseen changes in hourly demand) that has successfully been applied at a major European ground handling service company.

An analysis showing the impact of shift and break flexibility on solution quality and runtime.
2 Literature review
Personnel scheduling is the process of constructing work timetables for the employees of an organization to best meet the demand for its goods and services (Ernst et al.
2004). An overview of the subject can be found in Tien and Kamiyama (
1982), Ernst et al. (
2004), and Van den Bergh et al. (
2013). In our review, we focus on tour scheduling, break assignments, implicit break formulations, and airport ground staff scheduling.
Advertisement
The first integer programming formulation for personnel scheduling problems was given by Dantzig (
1954) who introduced a setcovering model in which each decision variable corresponded to a feasible tour. For all but the simplest of applications, however, problem size grows exponentially and becomes unmanageable when more than a handful of shift types and break options are considered. As a consequence, a large number of alternative formulations have been developed to reduce model size. Foremost are implicit formulations that either solve the problem by aggregating decisions or by modeling the rules for building shifts, breaks, or tours as constraints. Stolletz (
2010) introduced a reduced setcoveringbased formulation for the tour scheduling problem for checkin counter personnel in which all feasible shifts are enumerated explicitly as columns. A decision variable for each worker, each day of the planning horizon, and each shift is employed while the rules for building tours are modeled as constraints.
Çecik et al. (
2001) piece together tours using a network flow formulation. In their approach, integer variables are used to indicate the frequently with which a specific shift is assigned to a specific number of workers. However, the principle of shift aggregation cannot be directly adapted to tour scheduling problems in which individual shift information, such as worker skill levels or over and undertime, has to be considered.
Recent work to tackle the complexity of tour scheduling by means of branch and price is given by Restrepo et al. (
2016). A multiactivity assignment to shifts is included such that skill requirements can be modeled. In the case of our application, though, branch and price leads to a large number of subproblems that are burdened by complex break regulations. Furthermore, shift start and shift length were sufficient in the subproblem presented by Restrepo et al. (
2016) to find the best reduced costbased shift, whereas in our case, breaks influence the net working time of an employee in a shift. An algebraic representation of the constraints that model the rules for building tours is presented by Brunner et al. (
2009,
2010) for scheduling physicians in hospitals. In this paper, we extend those formulations to solve the tour scheduling subproblem that results from our decomposition.
The increase in problem complexity for the integrated tour and break scheduling problem is made clear in Brunner and Stolletz (
2014) where meal breaks must be assigned to shifts within a specified time window. While the setcovering formulation proposed by Stolletz (
2010) could be solved to optimality with offtheshelf software (CPLEX) for small instances, as the shift definition expanded and breaks were included it become impossible to find optimal solutions. To tackle the larger instances, branch and price was applied. However, computational results still showed gaps of up to 7% with 65 workers and a 1,000 node limit on the size of the search tree. Those instances also included a 15day planning horizon with 34 periods per day, and an upper bound of 435 shifts per day (without breaks). In contrast, we consider a 7day scheduling problem with 96 periods per day, up to 638 shifts per day and significantly higher complexity in break regulations. In Sect.
4, we give an overview of the various break regulations that have appeared in the in literature and classify relevant work.
Contributions to tour scheduling for ground handlers and other airport personnel have been made by Dowling et al. (
1997), Chu (
2007), Ásgeirsson (
2012), and Lusby et al. (
2011). In contrast to their work and other tour scheduling research found in the literature (e.g., see Van den Bergh et al.
2013), our framework considers the most flexible break regulations and contains over and undertime constraints for individual workers with hierarchical skill levels. To the best of our knowledge, this leads to the most general formulations to date. Practical instances of tour scheduling problems for ground handlers can include up to several hundred workers.
Given that the general problem is NPhard, finding optimal solutions to realworld instances is mostly beyond the reach of current technology. Dowling et al. (
1997) developed a system to support the monthly rostering of 500 workers at a large airport. They used simulated annealing to minimize idle time under highly fluctuating demand. A novel component of their approach was an external rule engine to check for feasibility after each neighborhood search. Chu (
2007) optimized daily schedules for baggage handlers at the Hong Kong International Airport using a goal programmingbased algorithm. Taking a behaviorbased approach, Ásgeirsson (
2012) designed a heuristic that emulates the logic of personnel managers when creating schedules for an airport ground service company with 53 employees. He begins with a partial schedule derived from employee requests and then builds a full schedule that satisfies the prevailing labor laws and company policies. Solution quality was judged by how closely the dayson and daysoff assignments matched employee requests. Finally, Lusby et al. (
2011) tackled a ground crew rostering problem for a European airline using a column generationbased heuristic. Their goal was to create longterm rosters based on 6 dayson, 3 daysoff work patterns.
Implicit break formulations for shift scheduling are presented by Bechtold and Jacobs (
1990), Aykin (
1996) and Rekik et al. (
2010). Bechtold and Jacobs (
1990) reduced the size of the setcoveringtype model by excluding the break information from the shift matrix. That is, breaks are treated in the aggregate and not explicitly assigned to shifts by the MIP. A set of constraints is introduced to guarantee that feasible breaks are available for the shifts chosen. In a postprocessing step, breaks are assigned to shifts. A different approach is proposed by Aykin (
1996) where a variable is introduced for each combination of shift and eligible break starting times. Again, beak information is removed from the shift matrix. In both formulations, predetermined break time windows and a fixed break duration are assumed.
The modeling of subbreaks for shift scheduling was introduced by Rekik et al. (
2010) who used the term
fractionable breaks. A fractionable break has an overall duration that can be split into one or more subbreaks with the restriction that the number of subbreaks is within a predefined range. In their work, subbreak placement is constrained by work stretch durations between consecutive breaks. They present two implicit model formulations for shift scheduling based on extensions of the models of Bechtold and Jacobs (
1990) and Aykin (
1996). For reasons similar to those stated for the network flow formulation of Çecik et al. (
2001), their modeling approaches cannot be easily adapted to shift scheduling problems that require individual shift information.
While many organizations take advantage of flexible break patterns within a shift, there has been little if any research on their use in the extended problem of tour scheduling. In part, this paper is aimed at filling this void. By separating the tour scheduling problem from the BAP, it is possible to use implicit formulations for dealing with a range of skill requirements. Building on the work of Rekik et al. (
2010) and others, we present two implicit formulations for the BAP in which hierarchical skills are taken into account. The one based on Bechtold and Jacobs (
1990), however, needs a postprocessor to assign breaks to workers and so cannot be applied in all environments (e.g., bus driver scheduling; see Rekik et al.
2010). To circumvent this limitation, we introduce and evaluate an alternative implicit formulation that models the break rules as constraints.
3 Problem description
Our tour scheduling model is built around individual
templates that specify the feasible set of shifts and days off that may be assigned to a worker each day of the planning horizon. We define a
shift as a given number of continuous periods with a fixed start time and duration. A
shift type is a set of shifts whose start times and durations fall within predefined ranges (e.g., early, midday or late). The set of all feasible shifts is denoted by
\(\mathcal {S}\).
To illustrate the concept of a template, consider a oneweek planning horizon and three workers, each having a different template as shown in Table
1. The notation E/L means that a worker can be assigned either an early or a late shift; L/X means that a worker can be assigned either a late shift or a day off, depending on demand. In the latter case, some workers may be on while others may be off. If a template offers all shift types on all days, i.e., E/L/X in the case of early and late shifts, the problem is equivalent to a tour scheduling problem without templates.
Table 1
Example of three different weekly templates for three workers with the following shift types: E = early, L = late, X = day off
Worker

Days of the week



Mo

Tue

Wed

Thu

Fri

Sat

Sun


1

X

E/X

E/X

E

E

E/L

L

2

L

L/X

X

X

X

E/X

E

3

E

E

E/L

L

L

L/X

X

Table 2
Sets and indices used in the formulation
Sets

Definition

Sets

Definition


\(\mathcal {W}\)

Workers,
\(w \in \mathcal {W}\)

\(\mathcal {M}\)

Shift types,
\(m \in \mathcal {M}\)

\(\mathcal {W}(q)\)

Workers with skill
q

\(\mathcal {M}(p)\)

Eligible shift types in template
p

\(\mathcal {S}\)

Shifts,
\(s \in \mathcal {S}\)

\(\mathcal {M}(d,p)\)

Eligible shift types in template
p on day
d

\(\mathcal {S}(d)\)

Shifts on day
d

\(\mathcal {T}\)

Number of planning periods per day,
\(t \in \mathcal {T}\)

\(\mathcal {S}(q,t)\)

Shifts covering demand for skill
q in period
t

\(\mathcal {T}^{\text {shS}}(m)\)

Shift starting times for the shift type
m

\(\mathcal {B}\)

Break patterns

\(\mathcal {T}^{\text {shE}}\)

Shift ending times

\(\mathcal {B}(s)\)

Break patterns for shift
s

\(\mathcal {T}^{\text {brS}}(r)\)

Break starting times for the
rth subbreak

\(\mathcal {D}\)

Planning days,
\(d \in \mathcal {D}\)

\(\mathcal {T}^{\text {brE}}\)

Break ending times of all subbreaks

\(\mathcal {D}(p)\)

Planning days in template
p

\(\mathcal {T}^{\text {brE}}(r)\)

Break ending times of the
rth subbreak

\(\mathcal {P}\)

Weekly templates,
\(p \in \mathcal {P}\)

\(\mathcal {Q}\)

Skill levels,
\(q \in \mathcal {Q}\)

At the European service company that provided our ground handler application, the templates for each worker for the upcoming week are derived from a cyclic template defined for a flight season (e.g., summer or winter), as well as each worker’s individual vacation plan, and are assumed to be given. The templates offer a concept that is in general useful to model many realworld requirements for tour scheduling such as individual holidays, personal preferences and employee carpools, aspects that we had to consider in the ground handling application but which we exclude from this study. For the general motivation behind the cyclic templates and its generation, we refer to Kiermaier et al. (
2016). In Kiermaier et al. (
2016), it is shown that incorporating stochastic information about employee demand when generating templates has a significantly positive impact especially when templates allow only limited flexibility, e.g., inflexible shift starting times and/or inflexible shift lengths.
The actual tasks for which the worker is responsible are assigned on the day of operation by a dispatcher. For the current tours, we want to assure that sufficient personnel are available to cover the demand. We now formalize the problem of creating a weekly tour for each member of the workforce based on his or her template. The underlying constraints reflect current operations; some are statutebased, while others are a result of union negotiations.
An overview of sets and indices used in the formulation is given in Table
2. The workforce is denoted by
\(\mathcal {W}\) such that each worker
\(w \in \mathcal {W}\) is assigned a template
\(p \in \mathcal {P}\), where
p defines the eligible shift types (e.g., early, off, late, combination) for each day
\(d \in \mathcal {D}\) in the week. The set
\(\mathcal {M}(d,p) \subseteq \mathcal {M}\) identifies the shift types that are allowed in template
p on day
d. A day in template
p can either be a mandatory working day, an optional working day or a day off.
The set of feasible shifts for day
d is given by
\(\mathcal {S}(d) \subseteq \mathcal {S}\). On mandatory working days, an employee must be uniquely assigned to a shift
\(s \in \mathcal {S}\), whereas on optional working days he may or may not be assigned to a shift, depending on the demand. Each day is divided into a set of periods
\(\mathcal {T} = \left\{ 1,\ldots ,T\right\} \) of equal length (typically, 15 min). A shift
\(s \in \mathcal {S}\) in weekly template
p has to satisfy the following rules.
S1.
Starting and ending time windows: Each shift type
m must start within the time band
\(\mathcal {T}^{\text {shS}}(m) \subset \mathcal {T}\) and must end within the time band
\(\mathcal {T}^{\text {shE}}\).
Multiple breaks are permitted per shift, but the actual number must fall between some lower and upper bound. This allows for maximum flexibility when making the break assignments. However, the length of each subbreak must also fall between some given bounds as must the time between them and their total duration. Adopting the nomenclature introduced by Rekik et al. (
2010) for fractionable breaks, we impose the following rules:
B1.
Number of breaks: There are
\(B^{\text {min}} \le r \le B^{\text {max}}\) subbreaks in a shift.
B2.
Workstretch between first break and shift start: The first break must start within
\(\left[ \Delta ^{\text {minBF}},\Delta ^{\text {maxBF}}\right] \) periods after the shift starts.
B3.
Single break duration: Break
\(r \in \left[ B^{\text {min}}, B^{\text {max}} \right] \) has a minimum and maximum duration of
\(\Delta ^{\text {minBD}}_{r}\) and
\(\Delta ^{\text {maxBD}}_{r}\) periods.
B4.
Overall break duration: The minimum and maximum overall break duration must be within the interval
\(\left[ \Delta ^{\text {minBD}},\Delta ^{\text {maxBD}}\right] \).
B5.
Workstretch duration: The workstretch duration after the
rth break has to be within
\(\left[ \Delta ^{\text {minBW}}_{r}, \Delta ^{\text {maxBW}}_{r}\right] \) periods.
B6.
Workstretch between last break and shift end: The last break must end within
\(\left[ \Delta ^{\text {minBL}},\Delta ^{\text {maxBL}}\right] \) periods before the shift ends.
Given the parameters in B1 to B6, the range of subbreak
r’s possible starting and ending times can be restricted to the subsets
\(\mathcal {T}^{\text {brS}}(r)\) and
\(\mathcal {T}^{\text {brE}}(r)\), respectively. In the following, we define a break pattern
\(b \in \mathcal {B}\) as a feasible set of subbreaks with starting times and durations such that (B1) to (B6) are satisfied. The subset of feasible break patterns within a shift
s that satisfies B5 and B6 is denoted by
\(\mathcal {B}(s)\). As we shall see in Sect.
4 these break regulations are the most general and flexible investigated to date. High flexibility, however, is accompanied by high complexity.
An additional attribute of the workforce is the level of skill that each individual brings to the job, whether he is a baggage handler, driver, ramp agent or other designation. Skill levels are ordered hierarchically, meaning that a worker at the higher end of the spectrum can fill in for one at the lower end when needed. Let
\(Q = \left\{ q_1,\ldots ,q_n\right\} \) be the ordered set of skills, where the relation
\( q_k \preceq q_l\) means that that a task requiring skill level
\(q_k \in \mathcal {Q}\) can be performed by any worker having a skill level of at least
\(q_l\) for
\(l \ge k\). The vector
\(K = \left( K_{q,t,d}\right) _{q \in \mathcal {Q}, t \in \mathcal {T}, d \in \mathcal {D}}\) is used to represent the demand of a task, where each element
\(K_{q,t,d}\) gives the required demand for skill level
q in time period
t on day
d. Each shiftcovering demand for skill level
q at time
t is contained in the set
\(\mathcal {S}(q,t)\).
At the beginning of the planning horizon, each worker
w has an accumulated bank of either overtime (
\(O_w \ge 0\)) or undertime (
\(O_w < 0\)) that must be kept within a target bandwidth
\(\left[ O^,O^+\right] \). Given a weekly template
\(p_w\) for worker
w, when generating a tour, the following rules must be taken into account.
T1.
Tour bandwidth: The length of a tour must be within the tour bandwidth
\(\left[ O^, O^+\right] \).
T2.
Forward rotation: The start time of shift type
m must be nondecreasing from one day to the next during the week.
T3.
Bandwidth: For each shift type, there is a maximum allowed bandwidth of
\(\Delta ^{\text {bw}}\) for shift starting times.
T4.
Starting times: The number of maximum allowed shift starting times per week for shift type
m is limited to
\(K^{\text {shift}}\).
The main objective of the problem is to minimize labor costs while covering as much demand as possible by fixing shift start and end times, days off, and breaks. Each worker incurs a cost of
\(c^{\text {work}}\) per period which is assumed to be less or equal than the unit cost of undercoverage
\(c^{\text {uc}}\), i.e.,
\(c^{\text {work}} \le c^{\text {uc}}\). In determining labor costs, the time that a worker is not on duty, such as during a break, is not factored into the calculations. Table
3 lists the cost parameters.
Table 3
Cost parameters
Parameter

Definition


\(c^{\text {work}}\)

Unit cost for a worker when on duty

\(c^{\text {uc}}\)

Unit cost of undercoverage

It is well known that tour scheduling problems are NPhard (see Lau
1996), which is one explanation for the lengthy runtime we experienced when trying to solve our first MIP model (see “Appendix
B”) of the ground handler staffing problem (GHSP) with CPLEX. In practice, breaks are often set at the beginning of the working day and not beforehand to better accommodate unforeseen changes in the demand profile. Therefore, to allow for this level of flexibility, as well as to reduce the difficulty of the problem, we have chosen to separate the BAP from the tour scheduling problem (see Sect.
5). In the next section, we categorize the full range of BAPs and undertake a complexity analysis of each.
4 Break assignment problem
The GHSP contains very general and flexible break regulations. Since the need for break assignments is common in many shift and tour scheduling problems, we classify and analyze the complexity of various BAPs found in the literature. A computational study of different versions of the problem is presented in Sect.
6.
4.1 Classification scheme
We use three sets of parameters to classify the BAP:

Single (S), multiple (M) or fractionable (F) breaks. Break assignment formulations can be classified as single, multiple or fractionable break models. In single break BAPs only one break per shift may be assigned, whereas a fixed number \(m \in \mathbb {Z}_+\) of breaks are required per shift for multiple BAPs. In contrast, fractionable break models have a lower and upper bound for the number of breaks that can be assigned to a shift.

Fixedtextbi(X) or variabletextbi(V) break length. For BAPs with single or multiple breaks, each subbreak can either have a fixed length or a lower and upper bound on its length. Considering fractionable breaks, the length of each is inherently variable, but there is an aggregate break length given which is then split into subbreaks for the shift.

Time windows (T) or workstretch (W) durations. Time windows define the periods of a shift in which a break can start. In contrast, the workstretch duration defines a lower and upper bound on the number of consecutive periods of work in a shift. Workstretch durations implicitly define time windows, with the difference being that the size and position of each are interdependent and therefore not static.
×
×
In what follows, we classify the various versions of the BAP using the 3tuple [
S,
M,
F
X,
V
T,
W]. Figure
1 gives a hierarchical overview of the complexity of the more interesting models based on the findings given below. Those models associated with the parameter combinations not shown are for the single break case where the workstretch restrictions lead to simple time windows and are therefore effectively the same problem class.
Figure
2 depicts four realizations of break types using the 3field notation and their possible positions in a shift. In panels (a)–(c), the gray rectangles define the time windows in which a break can take place due to work regulations. In panel (d), there are no predefined break windows as workstretch durations limit the solution space. However, there is a minimum workstretch of 2 periods before the first break and between the first and second breaks, and a minimum workstretch duration of 1 period after the last break. In all examples, the overall break duration is equal to 4 periods. The overall break length in (b) is split equally between the first and second breaks, while in (c), the lengths of the first and second breaks are variable.
The variety of possible break assignments provides increased flexibility but at a cost. This will be confirmed in a theoretical sense by studying the computational complexity of the different break regulations. Table
4 provides an overview of break regulations in the staff scheduling literature. As one can see, there has been little research on flexible break regulations despite their positive impact on solution quality (see Sect.
6).
Table 4
Break regulations in the staff scheduling literature
Break regulation

References


\(\left\{ SXT\right\} \)


\(\left\{ MXT\right\} \)


\(\left\{ MVT\right\} \)

Mirrazavi and Beringer (
2007)

\(\left\{ MXW\right\} \)


\(\left\{ FVT\right\} \)


\(\left\{ FVW\right\} \)

4.2 Complexity analysis
To the best of our knowledge, Widl and Musliu (
2014) are the only authors who previously addressed the complexity of the break assignment problem. Their NPcomplete proof is based on reduction from ‘Exact Cover by 3Sets’ (X3C) and is limited to arbitrary break patterns with 3 or more breaks. The assumptions needed for their proof do not hold for the break regulations discussed in this paper or for the regulated break patterns found in the literature.
In our analysis, we assume that a set of shifts
\(\mathcal {S}' \subset \mathcal {S}\) is given such that each
\(s \in \mathcal {S}'\) is associated with a unique worker
\(w \in \mathcal {W}\). The objective of the BAP is to assign breaks to each shift
s without violating the break constraints, i.e., B1 to B6, so that the costs associated with shift assignments and the uncovered demand are minimized. As mentioned in Sect.
3, each worker incurs a cost of
\(c^{\text {work}}\) per period which is assumed to be less than or equal to the unit cost of undercoverage
\(c^{\text {uc}}\), that is,
\(c^{\text {work}} \le c^{\text {uc}}\); off duty periods during a shift do not incur any cost. In the analysis, we work with a set partitioning formulation for the BAP in which all feasible break patterns
\(\mathcal {B}\) are enumerated. The set of feasible break patterns for shift
s is denoted by
\(\mathcal {B}(s)\). The following parameters and variables are used in the developments.
Parameters
Variables
Set partitioning formulation for the BAP
The objective function (
1) minimizes the sum of labor costs and the cost of uncovered demand over all periods. When a subset of periods has an initial shortage, i.e.,
\(D_{q,t} < 0\), it might be desirable to assign a larger positive weight than
\(c^{uc}\) to the corresponding variables to discourage additional undercoverage. Constraints (
2) account for demand reduction due to the break assignments to the shifts. The first term on the lefthand side reduces the demand in period
t for each shift that includes a break in period
t. The next two terms are complementary variables. The first represents the amount of remaining coverage in period
t after the breaks have been assigned and will be nonnegative if a shortage exists. The second variable represents the undercoverage in period
t after the breaks have been assigned and is minimized in (
1). The righthand side of (
2) is taken to be nonnegative to avoid penalizing existing undercoverage.

\(c^{\text {work}}_{s,b}\) = cost for a worker assigned shift s with break pattern b

\(a_{s,b,q,t}\) = 1, if break pattern b in shift s covers demand for skill q in period t, 0 otherwise

\(D_{q,t}\) = amount of overcoverage of demand for skill q in period t (can be negative)

\(z_{s,b}\) = 1, if break pattern b is assigned to shift s, 0 otherwise

\(y^_{q,t}\) = amount of uncovered demand for skill q in period t after break assignments

\(y^+_{q,t}\) = amount of excess demand for skill q in period t after break assignments
$$\begin{aligned}&\hbox {Minimize} \sum \limits _{s \in \mathcal {S}} \sum \limits _{b \in \mathcal {B}(s)} c^{\text {work}}_{s,b} \cdot z_{s,b} + \sum \limits _{q \in \mathcal {Q}} \sum \limits _{t \in \mathcal {T}} c^{\text {uc}} \cdot y^{}_{q,t} \end{aligned}$$
(1)
$$\begin{aligned}&\hbox {subject to} \nonumber \\&\sum \limits _{s \in \mathcal {S}'} \sum \limits _{b \in \mathcal {B}(s)} a_{s,b,q,t} \cdot z_{s,b} + y^{+}_{q,t}  y^{}_{q,t} = \max \left\{ D_{q,t},0\right\} \nonumber \\&\quad \forall \ q \in \mathcal {Q}, t \in \mathcal {T} \end{aligned}$$
(2)
$$\begin{aligned}&\sum \limits _{b \in \mathcal {B}(s)} z_{s,b} = 1 \quad \forall \ s \in \mathcal {S}' \end{aligned}$$
(3)
$$\begin{aligned}&z_{s,b} \in \left\{ 0,1\right\} \quad \forall \ s \in \mathcal {S}', b \in \mathcal {B}(s) \end{aligned}$$
(4)
$$\begin{aligned}&y^+_{q,t}, y^_{q,t} \ge 0 \quad \forall \ q \in \mathcal {Q}, t\in \mathcal {T} \end{aligned}$$
(5)
The convexity constraints (
3) enforce the requirement that each shift is assigned exactly one break pattern, and constraints (
4) and (
5) define the variables. In an optimal solution, at most
\(y^+_t\) or
\(y^_t\) will be positive but never both because we are trying to minimize the latter. Also, it can be seen that these variables will always be integral in an optimal solution so there is no need to impose such a restriction.
We now present several theoretical results that characterize the complexity of various versions of the BAP. Proofs can be found in “Appendix
A.”
Proposition 1
Corollary 1
Corollary 2
The implication of Proposition
1 is of particular interest when scheduling relief breaks, which are short breaks of 15 min or less and typically one period in length. Thompson and Pullman (
2007) reviewed 75 staff scheduling papers and found that 15% of them contained relief breaks. If considered separately, they can be assigned in polynomial time once the regular breaks are fixed.
When a break consists of more than one period, the sufficiency condition is lost so it is not possible to conclude that the full matrix for the set partitioninglike model (
1)–
5) is TU. We now show that solving the problem in which only a single break of arbitrary length is to be assigned is not polynomially solvable.
Theorem 1
The problem of assigning a single break to each shift to minimize the number of uncovered periods, that is, BAP
\(\{\)SXT
\(\}\), is strongly NPhard.
The BAP
\(\{MXT\}\) is equivalent to the break model that occurs as a subproblem in Aykin (
1996). By the principle of restriction stated by Garey and Johnson (
1979), the BAP
\(\{MXT\}\) is also NPhard in the strong sense since it includes the BAP
\(\{SXT\}\) as a special case; that is, when
\(m=1\). Similarly, because the BAP
\(\{SXT\}\) and the BAP
\(\{MXT\}\) are special cases of the BAP
\(\{SVT\}\) and the BAP
\(\{MVT\}\), respectively, the latter two problems are also strongly NPhard. Now, noting that the BAP
\(\{FVT\}\) is a generalization of the BAP
\(\{MVT\}\), with BAP
\(\{MVT\}\) being the special case of equalizing the lower and upper bound for the number of subbreaks of the BAP
\(\{FVT\}\), the relationships in Figure
1 follow. However, the BAP
\(\{MXT\}\) and the BAP
\(\{SVT\}\) cannot be hierarchically related to each other.
Proposition 2
The BAP
\(\{\)FVW
\(\}\) is strongly NPhard and includes the BAP
\(\{\)FVT
\(\}\) as a special case.
In a similar manner, the relations between BAP
\(\{MXT\}\) and BAP
\(\{MXW\}\), and between BAP
\(\{MVT\}\) and BAP
\(\{MVW\}\) can be shown. Each of these problems is strongly NPhard.
5 Decomposition procedure
In the GHSP under investigation, we have to tackle two NPhard problems: the tour scheduling problem (TShP) and the (fractionable) BAP
\(\{FVW\}\). Solving the integrated model given in “Appendix
B”, however, was seen to be intractable with CPLEX (see Sect.
6), so we adopted a sequential procedure. First, the TShP is solved to get feasible tours for each worker. Because this problem by itself is still intractable when two or more skill levels are considered simultaneously, we use downgrading. This approach starts with the highest skill level and works its way down to the lowest, covering as much demand as possible as the computations progress (Sect.
5.1). In light of the TShP solution, breaks are assigned to each shift by solving the BAP
\(\{FVW\}\) (Sect.
5.2).
5.1 Tour scheduling problem
Model formulation In the TShP, the start and end times of each shift for each worker, as well as their days off, are determined for the planning horizon. When applying the downgrading procedure, the TShP is solved for all workers
\(w \in \mathcal {W}(q_k)\) of a given single skill level
\(q_k \in \mathcal {Q}\) one level at a time. Let
\(\mathcal {Q}(q^{\text {+}},q_k)\) be the set of skills that are higher or equal to skill
\(q^{\text {+}}\) and lower or equal to skill
\(q_k\). In each iteration, the set of workers
\(\mathcal {W}(q_k)\) is scheduled such that they cover the demand for skill levels in
\(\mathcal {Q}(q^\text {+},q_k)\) with the proviso that they first cover higher level demand. In presenting the model, let TShP(
\(q^\text {+},q_k\)) be the tour scheduling problem being solved for workers with skill level
\(q_k\) with demand restricted to skill levels in
\(\mathcal {Q}(q^\text {+},q_k)\).
Variables
TShP(
\(q_k,q^+\))
Objective function The objective function (
7) minimizes the sum of labor costs and the cost of not meeting the demand. When workers with skill level
\(q_k\) are being considered, demand coverage for skill levels
\(q_{k}> \ldots >q_{1}\) is penalized with
\(p_{q_{k}} = 0< \ldots < p_{q_{1}}\) such that workers with skill level
\(q_k\) are prevented from covering demand that requires lower skills before covering demand requiring skill
\(q_k\).

\(y_{m,w,d,t} = 1\), if shift of type m for worker w starts in period t on day d, 0 otherwise

\(y^{\text {end}}_{w,d,t} = 1\), if shift for worker w ends in period t on day d, 0 otherwise

\(z_{w,q,d,t} = 1\), if worker w is active during period t on day d at skill level q, 0 otherwise

\(v_{m,w}\) = worker w’s earliest starting time for shift type m

\(w_{w,t} = 1\), if a shift for worker w starts in period t, 0 otherwise

\(y^{+}_{q,d,t}\) = shortfall in demand for skill level q in period t on day d
$$\begin{aligned}&\hbox {Minimize} \ \sum \limits _{q \in \mathcal {Q}(q^{\text {+}},k)} \sum \limits _{d \in \mathcal {D}}\sum \limits _{t \in \mathcal {T}} \left( \sum \limits _{w \in \mathcal {W}(q_k)} \left( c^{\text {work}} + p_q\right) \right. \nonumber \\&\qquad \left. \cdot z_{w,q,d,t} + c^{\text {uc}}\cdot y^{+}_{q,d,t} \right) \end{aligned}$$
(6)
$$\begin{aligned}&\hbox {subject to} \nonumber \\&Objective constraints \nonumber \\&\sum \limits _{w \in \mathcal {W}(q_k)} z_{w,q,d,t} + y^{+}_{q,d,t} \ge K_{q,d,t} \quad \forall \ q \in \mathcal {Q}(q^{\text {+}},k) \in \mathcal {D}, t \in \mathcal {T} \end{aligned}$$
(7)
$$\begin{aligned}&\sum \limits _{m \in \mathcal {M}(d,p_w)} \sum \limits _{l \in \mathcal {T}^{\text {shS}}(m) : l \le t } y_{m,w,d,l}  \sum \limits _{l \in \mathcal {T}^{\text {shE}}: l \ge t} y^{\text {end}}_{w,d,l}\nonumber \\&\quad = z_{w,q,d,t} \quad \begin{array}{ll} \forall \ w \in \mathcal {W}(q_k), d \in \mathcal {D}(p_w), \\ t \in \mathcal {T} \end{array} \end{aligned}$$
(8)
$$\begin{aligned}&\sum \limits _{q \in \mathcal {Q}(q^{\text {+}},k)} z_{w,q,d,t} \le 1 \quad \forall \ w \in \mathcal {W}(q_k), d \in \mathcal {D}(p_w), t \in \mathcal {T} \end{aligned}$$
(9)
$$\begin{aligned}&Shift constraints \nonumber \\&\mathbb {1}_{\mathcal {D}^{\text {fix}}(p_w)}(d) {\le } \sum \limits _{m \in \mathcal {M}(d,p_w)}\sum \limits _{t \in \mathcal {T}^{\text {shS}}(m)} y_{m,w,d,t} {\le } 1\nonumber \\&\qquad \forall \ w {\in } \mathcal {W}(q_k), d {\in } \mathcal {D}(p_w) \end{aligned}$$
(10)
$$\begin{aligned}&0 \le \sum \limits _{t \in \mathcal {T}^{\text {shE}}} t \cdot y^{\text {end}}_{w,d,t}  \nonumber \\&\quad \quad \sum \limits _{m \in \mathcal {M}(d,p_w)} \sum \limits _{t \in \mathcal {T}^{\text {shS}}(m)} \left( t + \Delta ^{\text {minS}}\right) \cdot y_{m,w,d,t}\nonumber \\&\qquad \le \Delta ^{\text {maxS}} \quad \forall \ w \in \mathcal {W}(q_k), d \in \mathcal {D}(p_w) \end{aligned}$$
(11)
$$\begin{aligned}&Tour constraints&\nonumber \\&O^  O_w \le \sum \limits _{d \in \mathcal {D}(p_w)} \left( \sum \limits _{t \in \mathcal {T}^{\text {shE}}} t \cdot y^{\text {end}}_{w,d,t}  \right. \nonumber \\&\quad \quad \left. \sum \limits _{m \in \mathcal {M}(d,p_w)}\sum \limits _{t \in \mathcal {T}^{\text {shS}}(m)} t \cdot y_{m,w,d,t} \right) \le O^+  O_w \quad \forall \ w \in \mathcal {W}(q_k) \end{aligned}$$
(12)
$$\begin{aligned}&\sum \limits _{t \in \mathcal {T}^{\text {shS}}(m)} t \cdot \left( y_{m,w,d,t}  y_{m,w,d',t} \right) \cdot y_{m,w,d',t}\nonumber \\&\qquad \le 0 \quad \begin{array}{ll} \forall \ m \in \mathcal {M}(d,p_w),w \in \mathcal {W}(q_k), \\ d,d' \in \mathcal {D}(p_w): d < d' \end{array} \end{aligned}$$
(13)
$$\begin{aligned}&t \cdot y_{m,w,d,t} \ge v_{m,w} \cdot y_{m,w,d,t} \quad \forall \ m \in \mathcal {M}(d,p_w),\end{aligned}$$
(14)
$$\begin{aligned}&w \in \mathcal {W}(q_k), d \in \mathcal {D}(p_w), t \in \mathcal {T}^{\text {shS}}(m) \end{aligned}$$
(15)
$$\begin{aligned}&\sum \limits _{t \in \mathcal {T}^{\text {shS}}(m)} t \cdot y_{m,w,d,t}  v_{m,w} \le \Delta ^{\text {bw}}\nonumber \\&\qquad \forall \ m \in \mathcal {M}(d,p_w), w \in \mathcal {W}(q_k), d \in \mathcal {D}(p_w) \end{aligned}$$
(16)
$$\begin{aligned}&w_{w,t} \cdot M \ge \sum \limits _{d \in \mathcal {D}(p_w)} y_{m,w,d,t} \nonumber \\&\qquad \forall \ m \in \mathcal {M}(p_w), w \in \mathcal {W}(q_k), t \in \mathcal {T}^{\text {shS}}(m) \end{aligned}$$
(17)
$$\begin{aligned}&\sum \limits _{t \in \bigcup \limits _{\begin{array}{c} d \in \mathcal {D}(p_w),\\ m \in \mathcal {M}(d, p_w) \end{array} }\mathcal {T}^{\text {shS}} (m)} w_{w,t} \le K^{\text {shifts}} \quad \forall \ w \in \mathcal {W}(q^{\text {work}}) \end{aligned}$$
(18)
$$\begin{aligned}&y_{m,w,d,t},w_{w,t},y^{\text {end}}_{w,d,t'},z_{w,q,d,t'} \in \left\{ 0,1\right\} \nonumber \\&\qquad \begin{array}{ll} \forall \ w \in \mathcal {W}(q_k), q \in \mathcal {Q}(q^{\text {+}},k), d \in \mathcal {D}(p_w), \\ m \in \mathcal {M}(d,p_w), t \in \mathcal {T}^{\text {shS}}(m), t' \in \mathcal {T}^{\text {shE}} \end{array} \end{aligned}$$
(19)
$$\begin{aligned}&v_{m,w} \in \mathbb {N} \quad \forall \ m \in \mathcal {M}, w \in \mathcal {W}(q_k) \end{aligned}$$
(20)
$$\begin{aligned}&y^{\text {uc}}_{q,d,t} \ge 0 \quad \forall \ q \in \mathcal {Q}(q^{\text {+}},k), d \in \mathcal {D}, t \in \mathcal {T} \end{aligned}$$
(21)
$$\begin{aligned}&z_{w,q,d,t} \in \left\{ 0,1\right\} \quad \forall \ w \in \mathcal {W}(q_k), q \in \mathcal {Q}(q^{\text {+}},k), d \in \mathcal {D}, t \in \mathcal {T} \end{aligned}$$
(22)
Objective function constraints Constraints (
7) ensure that either the demand for the skill levels in
\(\mathcal {Q}(q^{\text {+}},k)\) is covered or a shortage is identified. Variable
\(z_{w,q,d,t}\), which indicates whether or not worker
w is on duty in period
t on
d at skill level
q, i.e.,
\(z_{w,q,d,t} = 1\) or 0, is set in constraints (
8). Constraints (
9) guarantee that worker
w is assigned at most one skill level in each period.
Shift constraints (S1) Constraints (
10) set the start time of the shifts in worker
w’s weekly template,
\(p_w \in \mathcal {P}\). Here, the indicator function
\(\mathbb {1}_{\mathcal {D}^{\text {fix}}(p_w)}(d)\) is equal to 1 if day
d is an obligatory day on for worker
w, and 0 otherwise. (S2) The minimum and maximum shift length inclusive of breaks is bounded in the twosided constraints in (
11).
Tour constraints (T1) Bounds are placed on the maximum allowed undertime
\(O^\) and overtime
\(O^+\) for each worker
w in constraints (
12). (T2) The forward rotation of shift starting times over the week is enforced by constraints (
13). (T3) The earliest starting time for shift type
m is determined by constraints (
15), while the maximum permitted deviation between start times of each shift type during the week is restricted by constraints (
16). (T4) The maximum number of shift starts in a week is bounded by constraints (
17) and (
18). The remaining constraints define the variables.
Sequential assignment procedure The sequential procedure for assigning shifts to workers to cover demand for all skill levels in each time period of the planning horizon is outlined in Algorithm 1. Assume that Algorithm 1 is currently at skill level
\(q_2\) in step
3, i.e.,
\(q_k = q^\text {+} = q_2\). If it is possible to cover the entire demand
\(K_{q_2,t, d}\) for skill level
\(q_2\) in all periods
t on any day
\(d \in \mathcal {D}\) (see Step
8), Steps
9 through
11 are executed; that is, skill level
\(q^\text {+}\) is decremented by 1 such that
\(q^\text {+} = q_1\), and demand
\(K_{q_1, d,t}\) for skill level
\(q_1\) on day
d for all periods
t is added to constraints (
39). In objective function (
7), covering demand for skill level
\(q < q_k\) is penalized by
\(p_q\) to force the workers being scheduled to cover tasks requiring their skill level first. When TShP(
\(q_k,q^\text {+}\)) is solved for the first time, we set
\(q_k = q^\text {+} = q_n\) in Step
3.
×
The subprocedure in Steps
5 –
13 continues until undercoverage appears for some demand
\(K_{q,d,t}\) with
\(q \in \mathcal {Q}(q^\text {+},k)\) on any day
d in some period
t. Before decrementing
\(q_k\) and starting the next iteration in which TShP(
\(q_k,q^\text {+}\)) is solved for workers with the next lower skill level, we reduce the demand
\(K_{q,d,t}\) for
\(q \in \mathcal {Q}(q^\text {+},k)\) in Step
14 in periods that are covered by workers in
\(\mathcal {W}(q_k)\). For example, consider two time periods
\(t_1\) and
\(t_2\) on day
d and two skill levels
\(q_1\) and
\(q_2\) with the following demand.
For skill level
\(q_2\), assume that two workers are scheduled in
\(t_1\) and
\(t_2\), i.e., the demand for skill level
\(q_2\) is completely covered. Hence, the next lower skill level is added, i.e.,
\(q^{\text {+}} = q_1\). When running TShP(
\(q_k,q^\text {+}\)) again, the entire demand for skill level
\(q_2\) is covered, while one additional unit of demand is covered by one worker in period
\(t_2\) for skill level
\(q_1\). Finally, updating the residual demand for skill level
\(q_1\) gives
\(K_{q,d,t_1} = 1\) and
\(K_{q,d,t_1} = 0\).
$$\begin{aligned} K_{q_1,d,t_1} = 2, K_{q_1,d,t_2} = 1 \\ K_{q_2,d,t_1} = 1, K_{q_2,d,t_2} = 1 \\ \end{aligned}$$
5.2 Break assignment problem
Algorithm 1 terminates with a set of shifts
\(\mathcal {S}^*(d)\) for each day
d, where each shift
\(s \in \mathcal {S}^*(d)\) uniquely corresponds to one worker
\(w \in \mathcal {W}\). We now assign break patterns to these shifts by solving the BAP. Because there are no restrictions on break patterns from one day to the next, the computations can be done independently for each day
d.
5.2.1 Implicit formulations
The set partitioning formulation (
1)–(
5) explicitly assigns break patterns to shifts
\(\mathcal {S}(d)\). If we consider, for example, 400 shifts in which up to 3 subbreaks are permitted, and each subbreak can start within a time window of 12 periods and have a duration between 2 and 3, we obtain
\(\mathcal {B} = 5,529,600\). This value defines the number of columns (and hence variables) in the set partitioning formulation. The resultant problem is much too large to solve in practice. Consequently, we have adopted an implicit modeling approach to the BAP with nontrivial model extensions to consider a hierarchical multiskill workforce and investigate three different formulations.
The primary aim of implicit modeling is to reduce the number of decision variables by avoiding the need to enumerate each possible combination of shift and subbreak sequence. This is achieved by modeling the rules for building breaks as constraints. The implicit formulation associated with the GHSP is given in “Appendix
D”. The other two formulations are based on the shift scheduling work of Rekik et al. (
2010) who extended the multiple break models of Aykin (
1996) and Bechtold and Jacobs (
1990) to include fractionable breaks. However, they found that due to the large number of variables still required by Aykin’s formulation, computational difficulties arose when there is a high degree of break flexibility. With this in mind, we present an implicit formulation based on Bechtold and Jacobs (
1990) that can accommodate significant break flexibility as well as a hierarchical workforce. Insights into the computation times of the different formulations are provided in Sect.
6.
5.2.2 Notation and components of implicit BAP formulations
To help define our model, we introduce the terms
break profile and
shift profile. Each break profile
\(\beta \in \mathcal {BP}\) corresponds to a number of subbreaks denoted by
\(B_{\beta }\) and their respective lengths. For example, using minutes as the unit of time,
\(\beta _1 =\) 15/30/15 and
\(\beta _2 =\) 30/15/15 are two break profiles for a fractionable break with an overall length of 60 min. A subbreak
\(k \in \mathcal {K}\) is defined for each break profile, each position in the break profile, each possible starting time and each skill level. Notice that we need a unique subbreak for each skill level as we have to consider the skill of the worker that is taking the break. In Rekik et al. (
2010), a
shift profile (or a
shift in their terminology)
\(j \in \mathcal {J}\) is defined as a unique combination of start time, length, and admissible break profile. Because we are considering a hierarchical workforce, we have extended the definition of a shift profile to include a specific skill level. Some additional notation follows.
Sets
Parameters
Variables
The implicit aspect of the BAP formulation requires constraints that:
Before presenting our model, we outline the idea of using forward and backward constraints to ensure the feasibility of certain balanced transportation problems that were first introduced in Rekik et al. (
2004) and Çecik and Günlük (
2004). We also give a high level description of the transportation problems included in our models. In all cases, the sum of the supply equals the sum of the demand.

\(\mathcal {J}_{(\beta ,q)}\) = set of shift profiles associated with break profile \(\beta \) and skill q

\(\mathcal {B}_{(\beta ,r,q)}\) = set of subbreaks associated with break profile \(\beta \), position r and skill q

\(\rho _{t,k}\) = 1, if break k covers period t, 0 otherwise

\(h_{s,q}\) = number of workers assigned to shift s having skill q

\(l_{\hat{q},q,t}\) = number of shifts for workers with skill \(\hat{q}\) covering demand for jobs requiring skill q in period t

\(d_{k}\) = length of break k

\(S_j\) = number of workers assigned to shift profile \(j \in J\)

\(E_{k}\) = number of workers that are given subbreak k

\(P_{\hat{q},q,t}\) = number of workers having skill \(\hat{q}\) who are given a break in period t from a job requiring skill q

Match shifts with break profiles From the TShP, we obtain the set of shifts as well as the skill of the corresponding worker for each day of the planning horizon. When solving the BAP, we consider workers with the same shift and skill jointly. Therefore, instead of explicitly assigning each worker’s shift a break profile, we split the shifts into groups that are then associated with eligible break profiles. Example: Suppose that 5 workers with skill \(q_2\) are assigned a shift from 4 am to 11 am that is associated with two permissible break profiles \(\beta _1=\)15/15/15 and \(\beta _2=\)15/30. The workers are considered as a group, e.g., with 2 workers being assigned to \(\beta _1\) and 3 workers to \(\beta _2\).

Match subbreaks with shift profiles The number of subbreaks that are eligible in the rth position of break profile \(\beta \) is selected by means of forward and backward constraints. For each break profile, each position within it, and each skill level, these constraints ensure the feasibility of a transportation problem (to be defined presently) between the break profiles’ corresponding shift profiles (supply nodes) and the break profiles’ eligible subbreaks (demand nodes). Thus, it is not necessary to explicitly assign subbreaks to each shift profile.

Meet workstretch durations between subbreaks To ensure that the workstretch duration restriction between consecutive subbreaks is met, a set of forward and backward constraints is established. For each break profile, each position in the break profile but the last, and each skill level, these constraints ensure the feasibility of a transportation problem that balances the number of subbreaks with the number of their corresponding successor subbreaks.

Assign breaks to shifts When subbreak k covers period t, the demand coverage in period t has to be reduced by the number of workers that are given subbreak k. For each skill \(\hat{q}\), we must assure that the number of subbreaks associated with skill \(\hat{q}\) and covering period t does not exceed the number of workers with skill \(\hat{q}\) that are scheduled to work in period t in the TShP solution. Furthermore, in the context of downgrading, it is necessary to consider whether workers with skill \(\hat{q}\) are covering demand requiring lower skill. Accordingly, for each period t and skill q, the number of subbreaks of type k covering period t is assigned to demand q for \(q \le \hat{q}\) in an aggregated way such that the solution of TShP is respected. By using aggregation, we do not have to explicitly reduce the demand for a specific skill for each subbreak and each period the subbreak covers. Example In period 5, 4 workers with skill \(q_2\) are assigned to a job requiring skill \(q_2\) and 2 workers are assigned to a job requiring skill \(q_1\). BAP has to ensure that not more than 4 (2) workers with skill \(q_2\) are given a break in period 5 from a job requiring skill \(q_2\) ( \(q_1\)). If 3 workers with skill \(q_2\) have a break in period 5, their breaks can be assigned aggregately to jobs by either assigning 0, 1, or 2 breaks to a job requiring skill \(q_1\) while assigning 3, 2, or 1 breaks, respectively, to a job requiring skill \(q_2\).
Given a bipartite graph with a set of arcs
A connecting the two sets of nodes
\(N_1\) and
\(N_2\), with each node
\(i \in N_1\) having supply
\(O_i\) and each node
\(j \in N_2\) having demand
\(D_i\), we wish to determine the flow
\(Y_{i,j}\) from node
i to node
j for each
\((i,j) \in A\). The constraints for the corresponding transportation problem
\(T(N_1,N_2)\) can be stated as follows.
Under the assumptions that a total order relation
\(\prec \) can be defined on set
\(N_2\), each supply node
i is connected to a set of consecutive demand nodes
\(P_i\), and there exists no extraordinary overlap, i.e., there exists no two nodes
\(i_1\) and
\(i_2\) such that
\(P_{i_1} \subset P_{i_2}\), then the feasibility of transportation problem (
23) – (
24) is guaranteed by a set of forward, backward, and flow balance constraints. Using the following sets
and letting
\(n^s_2 = min(N_2)\) and
\(n^e_2 = max(N_2)\), the necessary constraints are
To match subbreaks with shift profiles, a transportation problem for each break profile, each position within the break profile, and each skill level has to be considered, i.e., a transportation problem
\(T(\mathcal {J}_{(\beta ,q)},\mathcal {B}_{(\beta ,r,q)})\) for each
\(\beta \in \mathcal {BP}\),
\(r \in \left\{ 1,\ldots ,B_{\beta }\right\} \) and
\(q \in \mathcal {Q}\). The supply associated with node
j is
\(S_j\), whereas the demand for node
k is
\(E_k\). An arc (
j,
k) exists between a shift
\(j \in \mathcal {J}_{(\beta ,q)}\) and a subbreak
\(k \in \mathcal {B}_{(\beta ,r,q)}\) if break
k is eligible in the
rth break position of shift
j. The subbreaks’ starting times define a total order on set
\(\mathcal {B}_{(\beta ,r,q)}\). Finally, we assume no extraordinary overlap between breaks of different shift profiles in
\(J_{\beta ,q}\). This is not a limitation for the tour scheduling problem under consideration or for most practical applications since there exist extensions that allow for extraordinary overlap by modifying the forward and backward constraints, e.g., see Addou and Soumis (
2007). Note that to adapt the forward and backward constraints presented in Rekik et al. (
2010) to respect hierarchical skills, besides associating each
\(j \in \mathcal {J}\) and
\(k \in \mathcal {K}\) with a specific skill level, a separate transportation problem has to introduced for each skill level.
$$\begin{aligned}&\sum \limits _{j: (i,j) \in \mathcal {A}} Y_{i,j} = O_i&\forall&\ i \in N_1 \end{aligned}$$
(23)
$$\begin{aligned}&\sum \limits _{i: (i,j) \in \mathcal {A}} Y_{i,j} = D_j&\forall&\ j \in N_2 \end{aligned}$$
(24)
$$\begin{aligned}&N^s_2 = \bigcup _{i=N_1}\left\{ min(P_i) \right\} \\&N^e_2 = \bigcup _{i=N_1}\left\{ max(P_i) \right\} \\&N^B_2(j) = \left\{ j' \in N_2j \preceq j' \right\} \quad \forall \ j \in N^s_2 \\&N^F_2(j) = \left\{ j' \in N_2j' \preceq j \right\} \quad \forall \ j \in N^e_2 \\&N^B_1(j) = \left\{ i \in N_1P_i \subseteq N^B_2(j) \right\} \quad \forall \ j \in N^s_2 \\&N^F_1(j) = \left\{ i \in N_1P_i \subseteq N^F_2(j) \right\} \quad \forall \ j \in N^e_2 \\ \end{aligned}$$
$$\begin{aligned}&\sum \limits _{j' \in N^F_2(j)} D_{j'} \ge \sum \limits _{i \in N^F_1(j)} O_i \quad \forall \ j \in N^e_2 \setminus \left\{ n^e_2 \right\} \\&\sum \limits _{j' \in N^B_2(j)} D_{j'} \ge \sum \limits _{i \in N^B_1(j)} O_i \quad \forall \ j \in N^s_2 \setminus \left\{ n^s_2 \right\} \\&\sum \limits _{i \in N_1} O_i  \sum \limits _{j \in N_2} D_j = 0 \\ \end{aligned}$$
To obtain a feasible solution with respect to workstretch durations, the feasibility of a second set of transportation problems,
\(T(\mathcal {B}_{(\beta ,r,q)},\mathcal {B}_{(\beta ,r+1,q)})\), must be assured. Here, the nodes correspond to breaks and are defined for all
\(\beta \in \mathcal {BP}\),
\(r \in \left\{ 1,\ldots ,B_{\beta }1\right\} \) and
\(q \in \mathcal {Q}\). The supply and demand of each node
k is
\(E_k\). Nodes
\(k_1 \in \mathcal {B}_{(\beta ,r,q)}\) and
\(k_2 \in \mathcal {B}_{(\beta ,r+1,q)}\) are connected if the workstretch duration between their corresponding breaks is within
\(\delta ^{\text {minBW}}\) and
\(\delta ^{\text {maxBW}}\). Further, based on the break starting times, a totally ordered relationship
\(\prec \) on
\(\mathcal {B}_{(\beta ,r,q)}\) is defined which per se excludes extraordinary overlap.
5.2.3 Implicit BAP formulation based on the Bechtold and Jacobs model
Our implicit formulation of the BAP is based on the model developed by Bechtold and Jacobs. It embodies the four components mentioned above along with a set of demand constraints. The objective here and for the two other formulations in Appendices C and D is to minimize the cost of uncovered periods minus the savings that result when workers are on their breaks.
Implicit BAP I (IBAP1)
Constraints (
26) determine the amount of demand for skill level
q on day
d in period
t that cannot be covered. While Rekik et al. (
2010) considered a shift scheduling problem, for the BAP that we are solving, the set of shifts are derived from the TShP and taken as input. To match shifts with permissible subbreaks, each shift needs to be associated with a break profile. In constraints (
27), the linking of shifts with break profiles is done implicitly, i.e., instead of explicitly assigning a break profile to each shift, identical shifts assigned to workers with the same skill are aggregated based on admissible break profiles. Constraints (
28) ensure that the number of subbreaks given in period
t for workers with skill
\(\hat{q}\) are only distributed among jobs that require at most skill
\(\hat{q}\). Note that this is only possible when each subbreak
k is associated with a specific skill. In constraints (
29), the assignment of subbreaks is bounded by
\(l_{\hat{q},q,t}\) such that breaks can only be given when the underlying jobs are being performed by workers having the specified skill. Again, workers with skill
\(\hat{q}\) who are performing a job that requires skill
q in period
t are grouped together. This arrangement guarantees that a feasible solution to the problem of explicitly assigning subbreaks to workers can be found in a postprocessing step.
$$\begin{aligned}&\hbox {Minimize} \sum \limits _{q \in \mathcal {Q}}\sum \limits _{t \in \mathcal {T}} c^{\text {uc}} \cdot y^{}_{q,t}  \sum \limits _{j \in \mathcal {J}}\sum \limits _{r \in \left\{ 1,\ldots ,B_j\right\} }\sum \limits _{k \in \mathcal {K}_{j(r)}} c^{\text {work}} \cdot d_{k} \cdot E_{k}&\end{aligned}$$
(25)
$$\begin{aligned}&\hbox {subject to} \nonumber \\&\sum \limits _{\hat{q} \ge q} P_{\hat{q},q,t} + y^{+}_{q,t}  y^{}_{q,t} = D_{q,d,t} \quad \forall \ q \in \mathcal {Q}, t \in \mathcal {T} \end{aligned}$$
(26)
$$\begin{aligned}&\sum \limits _{j \in \mathcal {J}_{s,q}} S_j = h_{s,q} \quad \forall \ s \in \mathcal {S}, q \in \mathcal {Q} \end{aligned}$$
(27)
$$\begin{aligned}&\sum \limits _{q \le \hat{q}} P_{\hat{q},q,t} = \sum \limits _{k \in \mathcal {K}_{\hat{q}}} \rho _{t,k} \cdot E_k \quad \forall \ \hat{q} \in \mathcal {Q}, t \in \mathcal {T} \end{aligned}$$
(28)
$$\begin{aligned}&P_{\hat{q},q,t} \le l_{\hat{q},q,t} \quad \forall \ \hat{q}, q \in \mathcal {Q}: q \le \hat{q}, t \in \mathcal {T} \end{aligned}$$
(29)
$$\begin{aligned}&\sum \limits _{k' \in \mathcal {B}^{F}_{(\beta ,r,q)}(k)} E_{k'}  \sum \limits _{j \in \mathcal {J}^{F}_{(\beta ,q)}(k)} S_{j} \ge 0 \quad \begin{array}{ll} \forall \ \beta \in \mathcal {BP}, r \in \left\{ 1,\ldots ,B_{\beta }\right\} , q \in \mathcal {Q}, \\ k \in \mathcal {B}^{\text {e}}_{(\beta ,r,q)} \setminus \left\{ k^{\text {e}}_{(\beta ,r,q)} \right\} \end{array} \end{aligned}$$
(30)
$$\begin{aligned}&\sum \limits _{k' \in \mathcal {B}^{B}_{(\beta ,r,q)}(k)} E_{k'}  \sum \limits _{j \in \mathcal {J}^{B}_{(\beta ,q)}(k)} S_{j} \ge 0 \quad \begin{array}{ll} \forall \ \beta \in \mathcal {BP}, r \in \left\{ 1,\ldots ,B_{\beta }\right\} , q \in \mathcal {Q}, \\ k \in \mathcal {B}^{\text {s}}_{(\beta ,r,q)} \setminus \left\{ k^{\text {s}}_{(\beta ,r,q)} \right\} \end{array} \end{aligned}$$
(31)
$$\begin{aligned}&\sum \limits _{k \in \mathcal {B}_{(\beta ,r,q)}} E_{k}  \sum \limits _{j \in \mathcal {J}_{(\beta ,q)}} S_{j} = 0 \quad \forall \ \beta \in \mathcal {BP}, r \in \left\{ 1,\ldots ,B_{\beta }\right\} ,q \in \mathcal {Q} \end{aligned}$$
(32)
$$\begin{aligned}&\sum \limits _{k' \in \mathcal {B}^{F}_{(\beta ,r+1,q)}(k)} E_{k'}  \sum \limits _{k' \in \mathcal {B}^{F}_{(\beta ,r,q)}(k)} E_{k'} \ge 0\nonumber \\&\qquad \begin{array}{ll} \forall \ \beta \in \mathcal {BP}, r \in \left\{ 1,\ldots ,B_{\beta }1\right\} ,q \in \mathcal {Q}, \\ k \in \mathcal {B}^{\text {e}}_{(\beta ,p+1,q)} \setminus \left\{ k^{\text {e}}_{(\beta ,p+1,q} \right\} \end{array} \end{aligned}$$
(33)
$$\begin{aligned}&\sum \limits _{k' \in \mathcal {B}^{B}_{(\beta ,r+1,q)}(k)} E_{k'}  \sum \limits _{k' \in \mathcal {B}^{B}_{(\beta ,r,q)}(k)} E_{k'} \ge 0\nonumber \\ {}&\qquad \begin{array}{ll} \forall \ \beta \in \mathcal {BP}, r \in \left\{ 1,\ldots ,B_{\beta }1\right\} ,q \in \mathcal {Q}, \\ k \in \mathcal {B}^{\text {s}}_{(\beta ,r+1,q)} \setminus \left\{ k^{\text {s}}_{(\beta ,r+1,q} \right\} \end{array} \end{aligned}$$
(34)
$$\begin{aligned}&\sum \limits _{k \in \mathcal {B}_{(\beta ,r+1,q)}} E_{k}  \sum \limits _{k \in \mathcal {B}_{(\beta ,r,q)}} E_{k} = 0 \quad \forall \ \beta \in \mathcal {BP}, r \in \left\{ 1,\ldots ,B_{\beta }1\right\} ,q \in \mathcal {Q} \end{aligned}$$
(35)
$$\begin{aligned}&P_{\hat{q},q,t} \in \mathbb {Z}_+ \quad \forall \ \hat{q}, q \in \mathcal {Q}: q \le \hat{q}, t \in \mathcal {T} \end{aligned}$$
(36)
$$\begin{aligned}&S_j, E_k \in \mathbb {Z}_+ \quad \forall \ j \in \mathcal {J}, k \in \mathcal {K} \end{aligned}$$
(37)
The feasibility of the transportation problems for workstretch duration restrictions between successive subbreaks is ensured by the forward, backward and flow balance constraints given in (
31), (
32) and (
33), respectively. Similarly, constraints (
33), (
34) and (
35) are respectively the forward, backward and flow balance constraints that ensure that enough subbreaks matching the shift profiles are assigned. Variables are defined in (
36) and (
37).
6 Computational study
The computations were performed on a Windows 7 platform with 4 GB RAM and a 2.8 GHz processor. All models were implemented in JAVA and solved with CPLEX 12.6. The data sets were provided by AeroGround GmbH, a major European ground handling service company. Each working day was divided into ninetysix, 15min periods.
Our study is based on two templates: ‘Fix’ and ‘Flex,’ differing in the length of the start time window, the duration of a shift (see Table
5), and in the flexibility of the possible shift types per day (see Table
6). Both templates are currently being used by AeroGround. The resulting number of shifts for the Fix template is at least the number of starting times, which is 8, while for Flex templates there are at least 319 (
\(= 29 \times 11 = \) number of start times multiplied by the number of shift lengths). Note that each hour is divided in four, 15minute periods. If on one day, two shift types are possible, e.g., see Table
6 in week 1 on Wednesday, then the number of feasible shifts doubles.
Table 5
Parameter values for the fixed and flexible work templates
Type

Start time window

Duration (Periods)



Early shift

Late shift


Fix

\(\left[ 4\,\text {am}, 6\,\text {am}\right] \)

\(\left[ 12\,\text {am}, 2\,\text {pm}\right] \)

41

Flex

\(\left[ 3\,\text {am}, 10\,\text {am}\right] \)

\(\left[ 11\,\text {am}, 6\,text{pm}\right] \)

\(\left[ 36, 46 \right] \)

We consider from 10 to 300 workers and five skill levels, where it is assumed that the demand for each level is
\(20\%\) of the total. The maximum amount of overtime and undertime per worker is given by
\(O^+ = O^ = 100\); the individual amount of overtime or undertime per worker was randomly assigned from the interval [0,100]. Since undercoverage in a period indicates missing workers, we assume that the cost per period of undercoverage is equal to the labor cost per period which is 1.
Table 6
Work templates—fix and flex
Week

Day



Mo

Tu

We

Th

Fr

Sa

Su


(a) Fix


1

E

E

L

L


2

L

L


3

E

E

E/L

L

L


4

E

E

E

E


5

L

L

E

E


6

E

E

L

L


7

E

E

L

L

L


8

L

E

E

E


9

L

E

E


10

E

E

L

L

L

L


(b) Flex


1

E

E

E/L

L

L

L/X


2

E

E

E/L

L


3

L

L/X

E


4

E

E/L

L

L

L/X


5

E

E

E/L

L

L


6

L/X

E

E


7

E/L

L

L

L/X


8

E

E

E/L

L

L

L/X


9

E

E

E/L


10

L

L

L/X

Table
7 presents the settings for the break regulations. The total break length (see column “Dur tot”) in each break regulation is set to 6 periods. The first subbreak starts between periods 8 and 24 periods after the shift start (column “FB”). The last break (column “LB”) for multiple or fractional breaks has to start between 3 and 16 periods before the shift ends. For all regulations with multiple breaks, 3 subbreaks have to be assigned. To guarantee a total break length of 6, in multiple break scenario
\(\left\{ M  X  T \right\} \) with fixed subbreak length, each subbreak is 2 periods, while in multiple break scenario
\(\left\{ M  V  T \right\} \) with variable subbreak length, each subbreak takes between 1 and 4 periods (column “Dur SB”). After the shift starts, the time windows of the second and third breaks are
\(\left[ 26, 29\right] \) and
\(\left[ 30, 33\right] \), respectively (column “TW”). In the two scenarios with fractional breaks,
\(\left\{ F  V  T \right\} \) and
\(\left\{ F  V  W \right\} \), 1 to 3 subbreaks can be assigned to each shift, which are either based on time windows or workstretch durations. The time windows for the second and third subbreaks associated with
\(\left\{ F  V  T \right\} \) are equal to those in the multiple break regulation case. For fractional break regulation
\(\left\{ F  V  T \right\} \), the workstretch duration between the successively subbreaks after the first subbreak is from 3 to 24 periods (column “WS”).
Table 7
Settings for the break regulations
Break regulation

Setting



#Breaks

Dur tot

Dur SB

WS

TW

FB

LB


\(\left\{ S  X  T \right\} \)

1

6

\(\left[ 8,24\right] \)


\(\left\{ M  X  T \right\} \)

3

6

2

\(\left[ 26,29\right] \),
\(\left[ 30,33\right] \)

\(\left[ 8,24\right] \)


\(\left\{ M  V  T \right\} \)

3

6

\(\left[ 1,4\right] \)

\(\left[ 26,29\right] \),
\(\left[ 30,33\right] \)

\(\left[ 8,24\right] \)

\(\left[ 3,16\right] \)


\(\left\{ F  V  T \right\} \)

\(\left[ 1,3\right] \)

6

\(\left[ 1,6\right] \)

\(\left[ 26,29\right] \),
\(\left[ 30,33\right] \)

\(\left[ 8,24\right] \)

\(\left[ 3,16\right] \)


\(\left\{ F  V  W \right\} \)

\(\left[ 1,3\right] \)

6

\(\left[ 1,6\right] \)

\(\left[ 3,24\right] \)

\(\left[ 8,24\right] \)

\(\left[ 3,16\right] \)

With respect to demand, both low and highlevel scenarios were investigated along with two different demand profiles: “varying demand” (VD) and “stable demand” (SD). Figure
3 depicts the profiles VD and SD for Monday to Sunday where each day is divided into 98 periods. The VD high level demand curve represents the true demand during the course of a week for each qualification of the sponsoring company. The VD lowlevel demand curves were derived from this curve by randomly lowering the demand. “Appendix
E” yields the three stable demand curves for the same days and periods.
×
To uniquely identify a test instance, we use the 4tuple representation
\(I\left\{ wor,pro,dem,temp\right\} \) specifying the workforce size
\(wor \in \left\{ 10,\ldots ,50,100, 150,200,250, 300,350,400\right\} \), the demand profile
\(pro\in \left\{ \text {VD, SD}\right\} \), the level
\(dem \in \left\{ \text {low}, \text {high}\right\} \), and the work template in Table
6
\(temp \in \left\{ \text {Fix}, \text {Flex}\right\} \).
The analysis is presented in two separate subsections: In Sect.
6.1, we compare the solution quality of our MIPheuristic with solutions obtained with the compact MIP (CMIP) formulation in “Appendix
B,” which integrates the tour scheduling problem and the BAP. In Sect.
6.2, we evaluate the “cost” of break flexibility by first generating tours by solving TShP (
7)–(
21). In light of those results, we study the different combinations of BAP formulations and BAP regulations to determine runtime and solution quality. To the best of our knowledge, this is the first study in which real data are used to determine the effect of break regulations on large tour scheduling problems.
Table 8
Results for the CMIP and the MIPheuristic for break regulation
\(\left\{ S  V  T \right\} \)
Instance

CMIP

MIPheuristic



Obj

Undercov

Runtime (s)

Obj

Undercov

Runtime (s)

GAP*


\(\left\{ 10,\text {low, SD},\text {fix}\right\} \)

7570

6520

15.77

7570

6520

3.68

0.00

\(\left\{ 50,\text {low, SD},\text {fix}\right\} \)

9805

2630

268.53

9975

2800

9.51

1.7

\(\left\{ 10,\text {low, SD},\text {flex}\right\} \)

7350

6033

33.9

7350

5690

8.82

0.00

\(\left\{ 50,\text {low, SD},\text {flex}\right\} \)

7350

3328

10, 074.84

7350

3010

12.72

0.00

\(\left\{ 10,\text {low, VD},\text {fix}\right\} \)

9086

8036

2.6

9086

8036

1.34

0.00

\(\left\{ 50,\text {low, VD},\text {fix}\right\} \)

10, 188

3013

830.01

10, 486

3311

12.58

2.84

\(\left\{ 10,\text {low, VD},\text {flex}\right\} \)

9084

7857

20.55

9089

7133

4.93

0.01

\(\left\{ 50,\text {low, VD},\text {flex}\right\} \)

9084

4546

8343.92

9185

3503

87.52

1.10

Table 9
Results for the CMIP and the MIPheuristic for break regulation
\(\left\{ F  V  W \right\} \)
Instance

CMIP

MIPheuristic



Obj

Undercov

Runtime (s)

Obj

Undercov

Runtime (s)

GAP*

GAP


\(\left\{ 10,\text {low, SD},\text {fix}\right\} \)

7510

6460

32.32

7510

6460

3.56

0.00


\(\left\{ 50,\text {low, SD},\text {fix}\right\} \)

9487

2312

2744.08

9640

2465

22.21

1.59


\(\left\{ 10,\text {low, SD},\text {flex}\right\} \)

7350

5690

203.92

7350

5690

9.05

0.00


\(\left\{ 50,\text {low, SD},\text {flex}\right\} \)

7350

3010

17.71

1.12


\(\left\{ 10,\text {low, VD},\text {fix}\right\} \)

9084

8034

31.97

9086

8036

3.54

0.02


\(\left\{ 50,\text {low, VD},\text {fix}\right\} \)

9784

2564

10800.3

10243

3, 068

18.21

4.48


\(\left\{ 10,\text {low, VD},\text {flex}\right\} \)

9084

7580

843.80

9084

7128

8.72

0.00


\(\left\{ 50,\text {low, VD},\text {flex}\right\} \)

9160

3478

98.51

1.35

6.1 Performance MIPHeuristic
To study the performance of the MIPheuristic in comparison with the CMIP, we restrict the workforce size to be between 10 and 65 employees for the low demand scenario. The break regulations investigated are
\(\left\{ S  X  T \right\} \), which represents the most common break regulations considered in literature (see Table
4), and BAP
\(\left\{ F  V  T \right\} \), which offers the greatest flexibility (see Fig.
1). In striving for a fair comparison, we solve Implicit BAP formulation III in “Appendix
D” in the second step of the MIPheuristic due to its structural similarity to the break assignment constraints in the CMIP.
The results for BAP
\(\left\{ S  V  T \right\} \) and BAP
\(\left\{ F  V  W \right\} \) for a workforce size of 10 and 50 employees are summarized in Tables
8 and
9, respectively. The results for all instances between 10 and 65 employees are shown in Tables
16 and
17 of “Appendix
F.” Column “Instance” identifies the scenario with respect to number of workers, work template, and demand characteristics. Columns “obj” and “undercov” report the objective value and undercoverage costs, respectively. The computation times are given in column “runtime” in seconds. Column “GAP*” gives the % gap between the optimal solution of the CMIP and the MIPheuristic. In Table
9, we have added the column “GAP” to report the % gap between the solution found by the MIPheuristic and the best LP bound obtained when no solution was found for the CMIP within the 5h (18,000 s) limit placed on each run.
The computations reveal that the MIPheuristic performs well with respect to the CMIP. The largest gaps of
\(7.52\%\) and
\(9.33\%\) for the variable and stable demand curves, respectively, are reached when no feasible or optimal solution for CMIP is found (see Table
17 of “Appendix
F,” instances
\(\left\{ 65, \text {low, SD,}, \text {fix}\right\} \)) and
\(\left\{ 65, \text {low, VD}, \text {fix}\right\} \))). If we restrict the results to those instances for which the optimal solution of CMIP is found, the gaps of the MIPheuristic are at most
\(4.48\%\) (see Table
9, instance
\(\left\{ 50, \text {low, SD, fix}\right\} \)). The gaps between CMIP and the MIPheuristic for the instances with the fix work templates are on average greater than those for the flex work template. In the first step of the MIPheuristic, the shifts obtained under flexible work templates provide more demand coverage than the shifts obtained with fix work templates and, therefore, lower the benefits of break flexibility.
Table 10
Number of workers considered for the two demand levels
Demand curve

# Workers


Low

\(\left[ 10,50,100\right] \)

High

\(\left[ 200,250,300\right] \)

Table 11
Results of the ThSP
Instance

Time (s)

# Workers

#Shifts

#Subbreaks



\(\left\{ S  V  T\right\} \)

\(\left\{ M  X  T\right\} \)

\(\left\{ M  V  T\right\} \)

\(\left\{ F  V  T\right\} \)

\(\left\{ F  V  W\right\} \)


\(\left\{ 10,\text {low, SD, fix}\right\} \)

0.79

4.28

1.1

87.43

82.29

97.71

1429.71

4278.86

\(\left\{ 50,\text {low, SD, fix}\right\} \)

4.25

29.29

3.86

240

308.57

3685.71

5093.14

11, 460

\(\left\{ 100,\text {low, SD, fix}\right\} \)

8.56

58.57

4.71

260.57

336.86

4122.86

5696.57

12, 303.43

\(\left\{ 10,\text {low, SD, flex}\right\} \)

3.4

7.14

1.43

316.29

128.57

1285.71

2108.57

6378

\(\left\{ 50,\text {low, SD, flex}\right\} \)

11.45

25

5

468

425.14

4251.43

6227.14

10, 354.29

\(\left\{ 100,\text {low,SD, flex}\right\} \)

1552.43

50

7.71

379.71

281.14

2811.43

4238.57

10, 675.34

\(\left\{ 10,\text {low, VD, fix}\right\} \)

1.96

4.28

2.09

104.57

122.57

1465.71

2027.14

4981.71

\(\left\{ 50,\text {low, VD, fix}\right\} \)

4.53

29.29

12.14

282

418.29

4662.86

6428.57

13, 182

\(\left\{ 100,\text {low,VD, fix}\right\} \)

9.22

58.57

11.29

281.14

421.71

4714.29

6498.86

13, 146.86

\(\left\{ 10,\text {low, VD, flex}\right\} \)

8.21

7.14

5.29

371.14

250.29

2502.86

4228.29

10, 798.29

\(\left\{ 50,\text {low, VD, flex}\right\} \)

66.15

28.14

26.71

578.57

795.42

7954.29

11, 544

16, 317.43

\(\left\{ 100,\text {low, VD, flex}\right\} \)

2567.69

51.71

20.28

478.29

798

7980

11.490

16, 263.43

\(\left\{ 200,\text {high, SD, fix}\right\} \)

51.82

11, 714

5.29

253.71

339.43

3, 394.29

5, 374.29

12, 022.29

\(\left\{ 250,\text {high, SD, fix}\right\} \)

60.75

146.43

8.71

273.43

397.71

3, 977.14

6, 147.43

12, 830.57

\(\left\{ 300,\text {high, SD, fix}\right\} \)

40.6

175.71

9.14

282

424.29

4, 242.86

6, 534

13, 182

\(\left\{ 200,\text {high, SD, flex}\right\} \)

2102.32

112

19

418

404.57

4, 045.71

6, 167.14

11, 882.57

\(\left\{ 250,\text {high, SD, flex}\right\} \)

2503.74

125

18.57

408.57

487.71

4877.14

7311.43

12, 538.29

\(\left\{ 300,\text {high, SD, flex}\right\} \)

7628.69

150

19.85

436.86

524.57

5254.29

7518

12, 467

\(\left\{ 200,\text {high, VD, fix}\right\} \)

33.15

117.14

11.57

282

400.29

4002.86

6182.57

13, 182

\(\left\{ 250,\text {high, VD, fix}\right\} \)

35.71

164.43

11.28

277.71

423.43

4234.29

6498.86

13, 006.29

\(\left\{ 300,\text {high, VD, fix}\right\} \)

40.50

175.71

11.28

279.43

405.43

4054.29

6252.86

13, 076, 57

\(\left\{ 200,\text {high, VD, flex}\right\} \)

3212.99

107.42

24.57

468.86

799.71

7997.14

12, 022.29

15, 997.71

\(\left\{ 250,\text {high, VD, flex}\right\} \)

4590.07

142.86

24.86

452.57

789.43

7894.29

11, 478.86

15, 223.71

\(\left\{ 300,\text {high, VD, flex}\right\} \)

4625.97

152.57

24.71

420.86

833.14

8331.43

12, 081.43

16, 368

A closer look at Tables
8 and
9 reveals the impact of break flexibility. Consider, for example, the instances with 50 workers. In the singe break scenario
\(\left\{ SVT\right\} \), if we compare instances for fixed and flexible work templates based on the stable demand curve, e.g., instances
\(\left\{ 50,\text {low, SD},\text {fix}\right\} \) and
\(\left\{ 50,\text {low, SD},\text {fix}\right\} \), flexible work templates improve the solution by 2, 455
\((= 9,805  7,350)\) or 25%. In contrast, comparing instance
\(\left\{ 50,\text {low, SD},\text {flex}\right\} \) for break regulations
\(\left\{ SVT\right\} \) and
\(\left\{ FVW\right\} \), we see that latter improves the solution by 318
\((=9,805  9,487)\), which represents
\(13\%\)
\((=100\% \times 318/2,455)\) of the improvement in the previous comparison. The improvement between the two break regulations becomes more significant when we focus on instances with varying demand. The difference between instances
\(\left\{ 50,\text {low, VD},\text {fix}\right\} \) and
\(\left\{ 50,\text {low, VD},\text {flex}\right\} \) with break regulation
\(\left\{ SVT\right\} \) is 1, 104
\((= 10,188  9084)\) or 10.8%. The comparisons between the two break regulations
\(\left\{ SVT\right\} \) and
\(\left\{ FVW\right\} \) for these instances leads to a decrease in the objective of 404
\((=10,188  9,784)\) which is equivalent to
\(37\%\) of the improvement that is obtained when flexible rather than fixed work templates are employed.
×
Our twostep approach is seen to provide highquality solutions in less than 100 seconds. Timely computations are critical when there is a frequent need to replan shifts and breaks due to workforce and demand fluctuations. Moreover, when the demand is largely uncertain from day to day, the only option is to reset the breaks since shift start and end times cannot be adjusted during the course of the day or even for the upcoming day without the likelihood of violating labor laws or incurring overtime costs. In the next section, break flexibility is explored in more detail.
6.2 Benefits of break flexibility
In the second phase of our experiments, we examined the relationships among break flexibility, undercoverage, and runtime for the various scenarios in Table
7. To begin, Algorithm 1 is solved to generate shifts and then the BAP is solved using the three different implicit formulations. The study demonstrates the degree to which the various break regulations can serve to reduce undercoverage when the shifts are given. For the variable and stable demand curves with both low and high demand, we consider the workforce sizes given in Table
10.
Table
11 provides the statistics obtained from Algorithm 1 in the first step of the MIPheuristic. Column “time (s)” reports the runtime in seconds. The average number of workers and the resulting number of shifts per day are shown in column “#worker” and “#shifts,” respectively. Based on these shifts, the columns under the major heading “#subbreaks” report the number of subbreaks for each break regulation in Table
7. It can be seen that for fixed work templates fewer shifts are generated, and hence there are fewer subbreaks for each break regulation compared to the instances that have flexible work templates. For example, for any number of workers associated with instances
\(\left\{ \cdot ,\text {high, VD, flex}\right\} \), there are significantly more subbreaks generated for any considered break regulation than for instances
\(\left\{ \cdot ,\text {high, VD, fix}\right\} \) with the same number workers.
The results in Table
11 reveal that as the workforce increases so does the runtime of Algorithm 1 when flexible work templates are used. Also, the type of demand curve is seen to affect runtime; instances with higher fluctuating demand take longer to converge. The number of shift types depends on the workforce size and on the work template type. For flexible work templates, more individual tours are generated to cover the demand. Of course, it is no surprise that the greater the flexibility available to generate shifts, the greater the number shifts and, hence, subbreaks. Similar to the hypothetical example in Fig.
2, the number of subbreaks increases geometrically with the flexibility of the break regulations. We also observed that as soon as a distinct number of shifts is used as a basis for the generation of subbreaks, increasing the number of shifts beyond that threshold leads to a decrease in the number of newly generated subbreaks. For example, for break regulations
\(\left\{ S  V  T\right\} \) and
\(\left\{ F  V  W\right\} \) the number of newly generated subbreaks only increases slightly when 5 or more shifts are used (see Figure
4). A similar effect can be observed for the other three break regulations in Table
11. Hence, for any break regulation there exist a bounded set of shifts leading to a bounded set of all possible subbreaks.
In Table
12, the three BAP formulations are compared: Implicit BAP I given in Sect.
5.2.3, Implicit BAP II given in “Appendix
C”, and Implicit BAP III given in “Appendix
D”, for break regulation
\(\left\{ F  V  W \right\} \). The results of the comparison for break regulation
\(\left\{ S  V  T \right\} \) can be found in Table
18 of “Appendix
F”. Column “comp (s)” reports the running time of CPLEX in seconds for each BAP formulation summed over the 7 planning days. For Implicit BAP I and II, it is necessary to derive the sets and parameters accompanying the models, given the set of shifts for each day, e.g., for Implicit BAP formulation I, we need subbreak set
\(\mathcal {B}\) and parameters
\(h_{s,q}\). The time in seconds for all the preprocessing summed over the 7 planning days is reported in column “pre (s).” The average number of variables and constraints for each BAP formulation per day is given in columns “#var” and “#constr,” respectively. If the fields in the table are empty, the corresponding BAP formulation could not find the optimal solution within the allowed time limit of 30 min (1800 seconds).
All problem instances with break regulation
\(\left\{ SVT\right\} \) could be solved for all of three BAP formulations (see Table
18). Comparing the total of runtime plus preprocessing time, Implicit BAP I and II slightly outperformed BAP III. The reason may be found in the increased number of variables in BAP III. However, when considering the results for the most flexible break regulation
\(\left\{ FVT\right\} \) in Table
12, Implicit BAP II performed worse than its other two competitors and is only solvable for small instances with less than 100 workers and fixed work templates. For a larger workforce, or for flexible work templates, the large number of subbreaks (
\(>10,000\) subbreaks, see Table
11), leads to more than 500, 000 variables in Implicit BAP formulation II, which makes the problem intractable. However, not all the instances associated with Implicit BAP III could be solved either due to the huge number of variables and constraints. On the other hand, for almost all instances with up to 100 workers, the fastest results were obtained with newly introduced formulation Implicit BAP III.
In addition to the above comparisons of the computational tractability of the different formulations, Table
14 highlights the objective function deviation in % of the four BAP regulations
\(\left\{ S  X  T\right\} \),
\(\left\{ S  V  T\right\} \),
\(\left\{ M  V  T\right\} \) and
\(\left\{ F  V  T\right\} \) from the most flexible break regulation
\(\left\{ F  V  W\right\} \). While the gaps between break regulations
\(\left\{ SVT\right\} \) and
\(\left\{ FVW\right\} \) are rather large with deviations up to 17.61% (see instance
\(\left\{ 50,\text {low, VD, fix}\right\} \)), break regulations with fractional breaks and time windows show gaps of at most 3.56% (see instance
\(\left\{ 100,\text {high,VD, fix}\right\} \)).
The improvements from models with less flexibility to models with more flexibility are highlighted in Table
13. For example, when break regulation
\(\left\{ MVT\right\} \) is used, undercoverage decreases by 4.11%, on average, compared to the results obtained with break regulation
\(\left\{ SVT\right\} \) (see row “Fix and Flex” in Table
13 which considers all templates in Tables
5 and
6). If we restrict the benefits of increased break flexibility to instances with fixed work templates only, then we obtain average improvements of
\(3.19\%\),
\(0.34\%\),
\(0.22\%\) and
\(0.24\%\), respectively (see Table
13 in row “Fix”). Hence, the greatest average benefits that result from increasing break flexibility are realized for the scenarios associated with fixed work templates and variable demand (Table
14).
One possible explanation for this result stems from the fact that flexible work templates do a better job at covering demand than fixed work templates in the first step of the MIPheuristic. For the highdemand scenarios, then, there is likely to be more uncovered demand when fixed work templates are used, so there is more opportunity to take advantage of break flexibility in the second step.
Table 12
Comparison of implicit BAP formulations for break regulation
\(\left\{ F  V  W\right\} \)
Instance

IBAP I

IBAP II

IBAP IIi



Comp (s)

Pre (s)

#Var

#Constr

Comp (s)

Pre (s)

#Var

#Constr

Time (s)

#Var

#Constr


\(\left\{ 10,\text {low, SD, fix}\right\} \)

3.9

1.49

7008

3173.14

56.49

41.42

87, 178.29

4, 160.29

1.17

790.29

2, 823.43

\(\left\{ 50,\text {low, SD, fix}\right\} \)

14.18

63.43

14, 689.71

4096.29

17.95

12, 573.43

2, 040.29


\(\left\{ 100,\text {low, SD, fix}\right\} \)

20.28

146.87

15, 546.86

4214.57

512.45

516, 442.3

11, 948.29

25.26

23, 994.86

3973.14


\(\left\{ 10,\text {low, SD, flex}\right\} \)

5.52

2.84

9568.86

3761.14

1.02

3847.71

920.29


\(\left\{ 50,\text {low, SD, flex}\right\} \)

11

8.18

13, 602.29

4202

3.2

9222

1, 786


\(\left\{ 100,\text {low,SD, flex}\right\} \)

30.36

8.37

14, 521.71

4590.43

50.23

37, 453.23

5433.33


\(\left\{ 10,\text {low, VD, fix}\right\} \)

5.63

10.16

7726.86

3311.14

3.19

11.09

52, 421.86

3690.43

0.56

2823.43

790.29

\(\left\{ 50,\text {low, VD, fix}\right\} \)

31.39

749.23

16, 544.29

5239.71

52.13

12, 573.43

2040.29


\(\left\{ 100,\text {low,VD, fix}\right\} \)

43.1

791.62

16, 495.43

5.121.43

125.23

2435.46

516, 442.3

11, 948.29

34.5

23, 994.86

3504.57

\(\left\{ 10,\text {low, VD, flex}\right\} \)

21.78

275.38

14, 050.86

4293.43

1.42

4143.71

962.57


\(\left\{ 50,\text {low, VD, flex}\right\} \)

81.2

1401

19, 912.86

7032.43

7.6

1, 809.56

38, 201.5


\(\left\{ 100,\text {low, VD, flex}\right\} \)

70.445

43.25

19, 756

6330.86

18.29

15, 996

2399.43


\(\left\{ 200,\text {high, SD, fix}\right\} \)

18.93

120.32

15, 274.86

4293.43

60.01

46, 837.71

7, 370.29


\(\left\{ 250,\text {high, SD, fix}\right\} \)

27.23

363.83

16, 138

4766.57


\(\left\{ 300,\text {high, SD, fix}\right\} \)

26.24

393.88

16, 496.29

4825.71

2, 109.57

69, 680.57

10, 767.43


\(\left\{ 200,\text {high, SD, flex}\right\} \)

43.5

1182.73

15, 973.43

6329.14

157

46, 837.71

7370.29


\(\left\{ 250,\text {high, SD, flex}\right\} \)

46.10

643.39

16, 074.14

6074.86


\(\left\{ 300,\text {high, SD, flex}\right\} \)

90.01

295.13

15, 973.43

6329.14


\(\left\{ 200,\text {high, VD, fix}\right\} \)

33.18

621.77

16, 535.14

5160.86


\(\left\{ 250,\text {high, VD, fix}\right\} \)

33.62

585.01

16, 354.86

5121.43


\(\left\{ 300,\text {high, VD, fix}\right\} \)

32.4

598.46

16, 425.14

5121.43


\(\left\{ 200,\text {high, VD, flex}\right\} \)

91.87

1580.92

19, 558.14

6628.14


\(\left\{ 250,\text {high, VD, flex}\right\} \)

82.06

1109.23

18, 782.57

6541.29


\(\left\{ 300,\text {high, VD, flex}\right\} \)

76.21

815.15

19, 728.29

6689

Table 13
Average benefits from break flexibility
Work template

Benefits (%)



\(\left\{ SVT\right\} \mapsto \left\{ MVT\right\} \)

\(\left\{ MXT\right\} \mapsto \left\{ MVT\right\} \)

\(\left\{ MVT\right\} \mapsto \left\{ FVT\right\} \)

\(\left\{ FVT\right\} \mapsto \left\{ FVW\right\} \)


Fix and flex

4.11

0.48

0.38

0.42

Flex

0.92

0.13

0.15

0.17

Fix

3.19

0.34

0.22

0.24

Table 14
Comparison of break flexibility with respect to
\(\left\{ F  V  W\right\} \)
Instance

Break regulation



\(\left\{ S  V  T\right\} \)

\(\left\{ M  X  T\right\} \)

\(\left\{ M  V  T\right\} \)

\(\left\{ F  V  T\right\} \)


\(\left\{ 10,\text {low, SD, fix}\right\} \)

0.15

0.07

0.07

0.00

\(\left\{ 50,\text {low, SD, fix}\right\} \)

5.44

1.23

0.00

0.00

\(\left\{ 100,\text {low, SD, fix}\right\} \)

0.78

0.78

0.70

0.25

\(\left\{ 10,\text {low, SD, flex}\right\} \)

0.00

0.00

0.00

0.00

\(\left\{ 50,\text {low, SD, flex}\right\} \)

6.02

3.34

0.98

0.97

\(\left\{ 100,\text {low, SD, flex}\right\} \)

1.71

0.41

0.20

0.17

\(\left\{ 10,\text {low, VD, fix}\right\} \)

17.61

3.02

1.62

0.00

\(\left\{ 50,\text {low, VD, fix}\right\} \)

2.85

1.16

0.45

0.14

\(\left\{ 100,\text {low,VD, fix}\right\} \)

4.96

3.56

3.04

3.04

\(\left\{ 10,\text {low,VD, flex}\right\} \)

1.09

0.12

0.02

0.00

\(\left\{ 50,\text {low,VD, flex}\right\} \)

0.06

0.00

0.00

0.00

\(\left\{ 100,\text {low,VD, flex}\right\} \)

2.88

1.22

1.2

0.43

\(\left\{ 200,\text {high,SD, fix}\right\} \)

13.04

0.99

0.15

0.04

\(\left\{ 250,\text {high,SD, fix}\right\} \)

16.68

1.25

0.69

0.31

\(\left\{ 300,\text {high,SD, fix}\right\} \)

8.96

0.95

0.19

0.10

\(\left\{ 200,\text {high,SD, flex}\right\} \)

11.43

1.32

1.13

0.01

\(\left\{ 250,\text {high,SD, flex}\right\} \)

3.37

1.78

1.65

1.23

\(\left\{ 300,\text {high,SD, flex}\right\} \)

0.56

0.02

0.02

0.02

\(\left\{ 200,\text {high,VD, fix}\right\} \)

9.62

0.37

0.03

0.00

\(\left\{ 250,\text {high,VD, fix}\right\} \)

11.39

3.65

2.07

0.67

\(\left\{ 300,\text {high,VD, fix}\right\} \)

4.59

2.56

2.27

1.35

\(\left\{ 200,\text {high,VD, flex}\right\} \)

0.25

0.20

0.20

0.01

\(\left\{ 250,\text {high,VD, flex}\right\} \)

2.11

1.43

1.43

1.02

\(\left\{ 300,\text {high,VD, flex}\right\} \)

3.83

1.23

1.02

0.42

7 Discussion and conclusions
The modeling and analysis in this paper addresses several unexplored aspects of tour scheduling. The first was the idea of generating tours based on individual work templates, thereby allowing planners to take into account the availability, skill level, and overtime budget of each employee. For a wide range of service organizations, reducing labor costs by exploiting shift and break flexibility can provide a critical competitive advantage. For greater insight into the different break regulations discussed in the literature, we introduced a threefield classification scheme for the various models. An accompanying complexity analysis showed that all but the simplest of problems are strongly NPhard. Our computations confirmed that as break flexibility increases, the corresponding break assignment problems become exponentially more difficult to solve.
Allowing variability in break length, fractionable breaks, and the use of workstretch durations in contrast to predefined break time windows was seen to reduce demand undercoverage and labor cost. The best improvement, though, was obtained by changing from single to multiple breaks per shift. A higher degree of break flexibility turned out to be especially valuable when shift regulations are rather rigid. Also, when the demand fluctuates greatly over the day, break flexibility can compensate for inflexible shift regulations and hence represents an alternative to loosening them up.
Because a compact formulation of the tour scheduling problem could not be solved for largescale instances, a MIPdecomposition heuristic was proposed that separates the break assignments from tour scheduling. The approach led to promising results with respect to runtimes and solution quality for all instances with up to 300 workers. In contrast, the compact formulation could only solve those instances with up to 50 workers and little shift flexibility.
To solve the break assignment problem, three implicit formulations were investigated. BAP III in “Appendix
D” has the advantage of not requiring any pre or postprocessing and could solve all instances with up to 100 workers in less than a minute. For all larger instances with 200 to 300 workers, only the formulation based on Bechtold and Jacobs (
1990) led to solution times of less than 30 min.
Currently, no procedure exists for solving the integrated problem to optimality in reasonable time. Its practical relevance offers ample justification for more algorithmic development. In the future, we plan to explore exact decomposition approaches to tackle the ThSP and the flexible BAPs in an integrated way. The study of the BAP alone is also of interest, especially for intraday schedule adjustments. During the course of the day, shifts cannot in general be adjusted when a the demand profile changes, but it may be possible to reassign the breaks. In this regard, we are now designing a rolling horizon framework for calibrating the value of flexible breaks in shortterm disruption scenarios.
Acknowledgements
Open Access funding provided by Projekt DEAL.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Appendix A: Proofs of complexity results
Proof of Proposition 1
First, let us assume that we have only one skill level for the workforce and the more general case in which breaks can be more than one period. Consider shift
s and its corresponding set of feasible break patterns
\(\mathcal {B}(s)\). By examining constraint (
2), we see that each column possesses the consecutive 1’s property. Let
\(A^1 \equiv (a^1_{i,j})\) be the matrix associated with the first shift in (
2). Such a matrix is TU (Nemhauser and Wolsey
1988). As an example, consider a shift of 10 periods that requires a break of either 3 or 4 periods starting in either periods 3, 4 or 5, as shown in Figure
5.
The row of 1’s below
\(A^1\) in this figure corresponds to constraint (
3); the second matrix, call it
Y, on the right corresponds to the
\(y^+_t\) or
\(y^_t\) variables. Although constraints (
3) destroy the consecutive 1’s property in general, when the break length for each shift is one period the portion of the
Amatrix in (
2) associated with each shift has a single 1 in each column. This entry appears in a row in which a break is permissible (this is not the case shown in Figure
5). The remaining row entries in the column are 0. Thus each column in the full matrix has at most two elements that are either 1 or
\(1\), and, in light of the special structure of constraints (
3), we see that it satisfies the sufficiency condition for TU. That is, there exits a partition of the set
M of rows into two sets
\(M_1\) and
\(M_2\) such each column
j containing two nonzero elements satisfies
\( \sum _{i \in M_1} a_{i,j}  \sum _{i \in M_2} a_{i,j} = 0\). Note that the
Ymatrix can be written as
\(Y = \left[ I,  I\right] \), where
I is the
\(T \times T\) identity matrix, so each column contains only a single nonzero element.
\(\square \)
×
Proof of Corollary 1
Again, let
\(A^1\) be the matrix associated with the first shift in (
2) and let
\(A^2\) be the matrix associated with constraints (
3), also for the first shift. As an example, Figure
6 depicts a portion of the constraint matrix for a shift with 7 periods that requires two breaks of one period each. For feasibility, the first must start in either period 2 or 3 and the second in either period 5 or 6. As indicated in the figure, when the length of each subbreak is equal to one period, each column of
\(A^1\) contains a single entry of 1 in the row where the subbreak exists with the remaining entries being 0. In a solution, one of the first two columns and one of the second two columns must be selected.
Now, when adding time windows to regulate subbreak starting times, there is no interdependency between the possible starting times of different subbreaks, i.e., the starting time of the
ith subbreak is independent of the starting time of the
jth subbreak for all
\(i,j \in \left[ 1, B^\text {max}\right] \). Each column of
\(A^2\) also contains a single entry of 1 or
\(1\) with the other entries being 0 due to the fact that each column of
\(A^1\) and
\(A^2\) corresponds to a single subbreak. Therefore, as in the proof of Proposition
1, the sufficiency condition for TU still holds in the case where the subbreak length is one period for each shift.
\(\square \)
×
Proof of Corollary 2
Following the proof of Corollary
1, let
\(A^1\) be the matrix associated with the first shift in (
2) and let
\(A^2\) be the matrix associated with constraints (
3), also for the first shift. As an example, Figure
7 shows a portion of the constraint matrix for a shift with 5 periods that requires one break. The break must start in either period 2, 3 or 4 of the shift and lasts for one period. We assume that there are two skill levels
\(q_1\) and
\(q_2\) and that the worker associated with the first shift is scheduled to work a job requiring skill
\(q_1\) in the second period and
\(q_2\) in the third and fourth periods, respectively. In periods 1 and 5, he is either working a job requiring
\(q_1\) or
\(q_2\) but, due to the time window, can not have a break. The submatrix above the horizontal line illustrates constraints (
2) for
\(q_1\) and the lower submatrix the corresponding constraints for
\(q_2\). When the length of the subbreak is equal to one period, each column of
\(A^1\) contains a single entry of 1 in the row where the subbreak exists (columns 1 and 2) with the remaining entries being 0. Column 3 shows that the consecutive 1’s property is lost when a subbreak incorporates more than a single skill.
Similar to the single skill case, when employing time windows to regulate subbreak starting times, there is no interdependency between the possible starting times of different subbreaks. Therefore, each column of
\(A^2\) also contains a single entry of 1 or
\(1\) with the other entries being 0 due to the fact that each column of
\(A^1\) and
\(A^2\) corresponds to a single subbreak. Now again, similar to the proof of Proposition
1, the sufficiency condition for TU still holds in the case where the subbreak length is one period for each shift.
\(\square \)
×
Proof of Theorem 1
We will show that an instance of the single machine scheduling problem with release times and deadlines, which Garey and Johnson (
1979) state is strongly NPhard, can be polynomially transformed into an instance of BAP{
S
X
T}.
INSTANCE: Set
\(\mathcal {J}\) of jobs, for each job
\(j \in \mathcal {J}\), a processing time
\(p_j \in \mathbb {Z}_+\), a release time
\(r_j \in \mathbb {Z}_+\), and a deadline
\(e_j \in \mathbb {Z}_+\).
QUESTION: Is there a single machine schedule for
\(\mathcal {J}\) that satisfies the release time constraints and meets all the deadlines?
Given an instance of the single machine scheduling problem, we equate a shift with a job, so
\(\mathcal {S}\) is equivalent to
\(\mathcal {J}\). For shift
\(s \in \mathcal {S}\), let
\(r_s\) be the period in which the break can start (release time),
\(e_s\) the last period in which the break is allowed (deadline), and
\(p_s\) the number of periods of the break (processing time). Also, let the surplus of coverage in each period be 1.
Claim: There exists a feasible assignment of breaks to shifts such that there are no manpower shortages in any period if and only if there is a feasible schedule of jobs for the single machine problem.
The condition of no manpower shortage in any period means that no two breaks overlap. This is equivalent to a schedule on a single machine in which each job is processed between its release time and deadline without conflicting with any other job. Given that the above transformation is linear in the number of shifts, and that any candidate solution to the BAP can be checked for feasibility in polynomial time, the statement of the theorem follows.
\(\square \)
Proof of Proposition 2
For the BAP
\(\{FVT\}\) with
n distinct time windows, assume that the overall break length ranges between
\(\Delta ^\text {minBD}\) and
\(\Delta ^\text {maxBD}\) periods and that the minimum and maximum number of subbreaks are between
\(B^\text {min}\) and
\(B^\text {max}\). With each time window
\(\left[ t^s_{r}, t^e_{r} \right] , r \in \left\{ 1,\ldots ,n \right\} \), we associate a minimum break length of
\(d^{\text {min}}_r\) and a maximum break length of
\(d^{\text {max}}_r\). Accordingly, for each
\(i \in \left\{ 1,\ldots ,B^\text {max}\right\} \) the
ith subbreak can start in the (
i)th,...,
\((nB^\text {min}+i)\)th time window and the length of the
ith subbreak is between
\(lb^\text {bl}_{i} = min_{r \in \left\{ i,\ldots ,nB^\text {min}+i \right\} }(d^{\text {min}}_r)\) and
\(ub^\text {bl}_{i} = max_{r \in \left\{ i,\ldots ,nB^\text {min}+i \right\} }(d^{\text {max}}_r)\) periods.
For the BAP
\(\{FVW\}\), we set the range for the overall break length as well as the minimum and maximum number of subbreaks equal to those of the BAP
\(\{FVT\}\). Further, for each subbreak
\(i \in \left\{ 1,\ldots ,B^\text {max} \right\} \), we set the minimum and the maximum break length equal to
\(lb^\text {bl}_{i}\) and
\(ub^\text {bl}_{i}\), respectively. To proof our statement, it is sufficient to set the minimum and maximum workstretch after each subbreak equal to 0 and the shift length, respectively. Based on the assumptions, BAP
\(\{FVW\}\) includes all the breaks of the BAP
\(\{FVT\}\) but not vice versa.
Now, place a cost of
M > 0 on each subbreak in the BAP
\(\{FVW\}\) that is not feasible to BAP
\(\{FVT\}\). The procedure can be done in polynomial time as for each shift, the overall number of breaks in the BAP
\(\{FVW\}\) is bounded by
\(\prod _{i \in \left\{ 1,\ldots ,B^\text {max} \right\} }(ub^\text {bl}_{i}lb^\text {bl}_{i}) \cdot \Delta ^\text {maxS}\). Given both models, we claim that the BAP
\(\{\)FVT
\(\}\) has a solution with no uncovered periods if and only if the BAP
\(\{FVW\}\) has a solution with no uncovered periods and a cost of 0. First suppose that the BAP
\(\{FVT\}\) has a solution with no uncovered periods. Then the same break patterns can be used for the BAP
\(\{FVW\}\) to obtain the same solution. This proves the “if” part of the statement. Now suppose that the optimal solution to the BAP
\(\{FVW\}\) has a cost greater than 0. By implication, this solution contains subbreaks that have a cost
M and hence is not feasible to the BAP
\(\{FVT\}\). Therefore, BAP
\(\{FVT\}\) does not have a solution with uncovered periods. This proves the “only if” part of the statement. Now observe that the BAP
\(\{FVT\}\) does not include the BAP
\(\{FVW\}\) since the break windows of two or more consecutive subbreaks can overlap. Consider a BAP
\(\{FVW\}\) with two subbreaks. Let
\(\Delta ^{\text {minBF}}\) and
\(\Delta ^{\text {maxBF}}\) be the minimum and maximum workstretch duration before the first subbreak, respectively. Further, let
\(\Delta ^{\text {durB}}\) be the minimum duration of the first subbreak and let
\(\Delta ^{\text {minBW}}\) be the minimum workstretch duration between the first and second subbreaks. When
\(\Delta ^{\text {minBF}} + \Delta ^{\text {durB}} + \Delta ^{\text {minBW}} < \Delta ^{\text {maxFB}}\), the break windows of the first and second subbreaks overlap. In general, in the presence of workstretch durations, the break window for a particular subbreak can only be derived after the realization of the other subbreaks.
\(\square \)
Appendix B: Compact mixedinteger program
The ground handler staffing problem (GHSP) is to minimize the total cost of the workforce plus the cost for undercoverage for a given planning horizon. The compact MIP (CMIP) below determines shifts with fractionable breaks for each day in the week and creates a duty roster for each worker such that as much demand as possible is covered in each period for the different skill levels.
Variables
CMIP
The objective function (
38) along with the constraints (
39)–(
41) is similar to (
7) and (
7)–(
9), respectively, but now all skill levels are included. Constraints (
42)–(
54) describe the break regulations. With respect to B1, for each worker
w at least
\(B^{\text {min}}\) subbreaks per shift are set in constraints (
42), while the minimum and maximum number of periods from the start of the shift to the first subbreak, as indicated in B2, are set in constraints (
43)). The length of each subbreak, as restricted by B3, and the overall break length, as restricted by B4, are bounded by constraints (
44) and (
45), respectively. The minimal and maximal bandwidth between two subbreaks, B5, is set in constraints (
46). The distance of the last subbreak to the end of the shift, B6, is modeled in constraints (
47). The decision variables
\(b^{\text {last}}_{w,t,d}\), which control the latest ending time over all subbreaks assigned to worker
w on day
d are determined by (
48)–(
51).

\(b^{\text {start}}_{r,w,d,t} = 1\), if subbreak r for worker w starts in period t on day d, 0 otherwise

\(b^{\text {end}}_{r,w,d,t} = 1\), if subbreak r for worker w ends in period t on day d, 0 otherwise

\(b^{\text {last}}_{w,d,t} = 1\), if the last subbreak for worker w ends in period t on day d, 0 otherwise
$$\begin{aligned}&\hbox {minimize} \sum \limits _{q \in \mathcal {Q}} \sum \limits _{d \in \mathcal {D}}\sum \limits _{t \in \mathcal {T}} \left( \sum \limits _{w \in \mathcal {W}} c^{\text {work}} \cdot z_{w,q,d,t} + c^{\text {uc}} \cdot y^{\text {uc}}_{q,d,t} \right)&\end{aligned}$$
(38)
$$\begin{aligned}&\hbox {subject to}~(10)(21) \nonumber \\&\sum \limits _{q' \in \mathcal {Q}: q' \ge q}\sum \limits _{w \in \mathcal {W} (q')} z_{w,q,d,t} + y^{\text {+}}_{q,d,t}  y^{\text {}}_{q,d,t} =K_{q,d,t}\nonumber \\&\qquad \forall \ d \in \mathcal {D}, t \in \mathcal {T}, q \in \mathcal {Q} \end{aligned}$$
(39)
$$\begin{aligned}&\sum \limits _{m \in \mathcal {M}(d,p_w)} \sum \limits _{ l \in \mathcal {T}^{\text {shS}}: l \le t } \left( y_{m,w,d,l}  \right. \nonumber \\&\quad \quad \left( \sum \limits ^{B^{\text {max}}}_{r = 1} \left( \sum \limits _{l \in \mathcal {T}^{\text {brS}}(r): l \ge t} b^{\text {start}}_{r,w,d,l}  \sum \limits _{l \in \mathcal {T}^{\text {brE}}(r): l \ge t}b^{\text {end}}_{r,w,d,l} \right) + \right. \end{aligned}$$
(40)
$$\begin{aligned}&\quad \quad \quad \left. \sum \limits _{l \in \mathcal {T}^{\text {shE}}: l \ge t}y^{\text {end}}_{w,d,l} \right) = z_{w,q,d,t}\nonumber \\&\qquad \forall \ w \in \mathcal {W}, d \in \mathcal {D}(p_w), t \in \mathcal {T} \nonumber \\&\sum \limits _{q \in \mathcal {Q}} z_{w,q,d,t} \le 1 \quad \forall \ w \in \mathcal {W}, d \in \mathcal {D}(p_w), t \in \mathcal {T} \end{aligned}$$
(41)
$$\begin{aligned}&\mathbf{Break} regulations \nonumber \\&\sum \limits ^{B^{\text {max}}}_{r = 1}\sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} b^{\text {start}}_{r,w,d,t} \ge \sum \limits _{t \in \mathcal {T}^{\text {brS}}(1)} b_{1,w,d,t} \cdot B^{\text {min}} \nonumber \\&\qquad \forall \ w \in \mathcal {W}, d \in \mathcal {D}(p_w) \end{aligned}$$
(42)
$$\begin{aligned}&\Delta ^{\text {maxBF}} \ge \left( \sum \limits _{t \in \mathcal {T}^{\text {brS}}(1)} t \cdot b^{\text {start}}_{1,w,d,t}  \right. \nonumber \\&\quad \quad \left. \sum \limits _{m \in \mathcal {M}(d,p_w)}\sum \limits _{t \in \mathcal {T}^{\text {shS}}(m)} \left( t  \Delta ^{\text {minBF}}\right) \cdot y_{m,w,d,t} \right) \ge 0 \nonumber \\&\qquad \forall \ w \in \mathcal {W}, d \in \mathcal {D}(p_w) \end{aligned}$$
(43)
$$\begin{aligned}&\Delta ^{\text {maxBD}}_{r} \ge \sum \limits _{t \in \mathcal {T}^{\text {brE}}(r)} t \cdot b^{\text {end}}_{r,w,d,t}  \sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} t \cdot b^{\text {start}}_{r,w,d,t} \ge \nonumber \\&\quad \quad \Delta ^{\text {minBD}}_{r} \cdot \sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} b^{\text {start}}_{r,w,d,t} \quad \forall \ w \in \mathcal {W}, d \in \mathcal {D}(p_w), 1 \le r \le B^{\text {max}} \end{aligned}$$
(44)
$$\begin{aligned}&\Delta ^{\text {maxBD}} \ge \sum \limits ^{B^{\text {max}}_p}_{r = 1} \left( \sum \limits _{t \in \mathcal {T}^{\text {brE}}(r)} t \cdot b^{\text {end}}_{r,w,d,t}  \sum \limits _{\mathcal {T}^{\text {brS}}(r)} t \cdot b^{\text {start}}_{r,w,d,t} \right) \ge \nonumber \\&\quad \quad \Delta ^{\text {minBD}} \cdot \sum \limits _{m \in \mathcal {M}(d,p_w)}\sum \limits _{t \in \mathcal {T}^{\text {shS}}(m)} y_{m,w,d,t} \quad \forall \ w \in \mathcal {W}, d \in \mathcal {D}(p_w) \end{aligned}$$
(45)
$$\begin{aligned}&\Delta ^{\text {maxBW}}_{r} \ge \sum \limits _{t \in \mathcal {T}^{\text {brS}}_{m}(r)} t \cdot b^{\text {start}}_{r+1,w,d,t}  \nonumber \\&\quad \quad \quad \sum \limits _{t \in \mathcal {T}^{\text {brE}}(r)} t \cdot b^{\text {end}}_{r,w,d,t} \ge \Delta ^{\text {minBW}}_{r} \cdot \sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} b^{\text {start}}_{r+1,w,d,t} \nonumber \\&\qquad \begin{array}{ll} \forall \ w \in \mathcal {W}, d \in \mathcal {D}(p_w), \\ 1 \le r < B^{\text {max}} \end{array} \end{aligned}$$
(46)
$$\begin{aligned}&\sum \limits _{t \in \mathcal {T}^{\text {shE}}} y^{\text {end}}_{w,d,t}  \Delta ^{\text {minBL}} \ge \left( \sum \limits _{t \in \mathcal {T}^{\text {brE}}} t \cdot b^{\text {last}}_{w,d,t} \right) \ge \nonumber \\&\quad \quad \quad \sum \limits _{t \in \mathcal {T}^{\text {shE}}} y^{\text {end}}_{w,d,t}  \Delta ^{\text {maxBL}} \quad \forall \ w \in \mathcal {W}, d \in \mathcal {D} \end{aligned}$$
(47)
$$\begin{aligned}&\sum \limits _{t \in \mathcal {T}^{\text {brE}}} t \cdot b^{\text {last}}_{w,d,t} \ge \left( \sum \limits _{t \in \mathcal {T}^{\text {brE}}(r)} t \cdot b^{\text {end}}_{r,w,d,t} \right) \nonumber \\&\qquad \forall \ w \in \mathcal {W},d \in \mathcal {D}, B^{\text {min}} \le r \le B^{\text {max}} \end{aligned}$$
(48)
$$\begin{aligned}&\sum \limits _{t \in \mathcal {T}^{\text {brE}}\backslash \left\{ 0\right\} } \left( t  1 \right) \cdot b^{\text {last}}_{w,d,t} \le \sum \limits _{t \in \mathcal {T}^{\text {brE}}(r)} t \cdot b^{\text {end}}_{r,w,d,t} + \nonumber \\&\quad \quad \quad \sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} b^{\text {start}}_{r+1,w,d,t} \cdot T \quad \forall \ w \in \mathcal {W}, d \in \mathcal {D},B^{\text {min}} \le r < B^{\text {max}} \end{aligned}$$
(49)
$$\begin{aligned}&\sum \limits _{t \in \mathcal {T}^{\text {brE}}\backslash \left\{ 0\right\} } \left( t  1 \right) \cdot b^{\text {last}}_{w,d,t} \le \sum \limits _{t \in \mathcal {T}^{\text {brE}}(B^{\text {max}})} t \cdot b^{\text {end}}_{B^{\text {max}},s,t} + \nonumber \\&\quad \quad \quad \left( 1  \sum \limits _{t \in \mathcal {T}^{\text {brS}}(B^{\text {max}})} b^{\text {start}}_{B^{\text {max}},w,d,t}\right) \cdot T \quad \forall \ w \in \mathcal {W}, d \in \mathcal {D} \end{aligned}$$
(50)
$$\begin{aligned}&\sum \limits _{t \in \mathcal {T}^{\text {brE}}\backslash \left\{ 0\right\} } b^{\text {last}}_{w,d,t} \le 1 \quad \forall \ w \in \mathcal {W}, d \in \mathcal {D} \end{aligned}$$
(51)
$$\begin{aligned}&\sum \limits _{t \in \mathcal {T}^{\text {brS}}(r1)} b^{\text {start}}_{r1,w,d,t} \ge \sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} b^{\text {start}}_{r,w,d,t} \nonumber \\&\qquad \forall \ w \in \mathcal {W}, d \in \mathcal {D}(p_w), 1 < r \le B^{\text {max}} \end{aligned}$$
(52)
$$\begin{aligned}&\sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} b^{\text {start}}_{r,w,d,t} \le 1 \wedge \sum \limits _{t \in \mathcal {T}^{\text {brE}}(r)} b^{\text {end}}_{r,w,d,t} \le 1 \nonumber \\&\qquad \forall \ w \in \mathcal {W}, d \in \mathcal {D}(p_w), 1 \le r \le B^{\text {max}} \end{aligned}$$
(53)
$$\begin{aligned}&\sum \limits ^{B^{\text {max}}}_{r = 1}\sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} b^{\text {start}}_{r,w,d,t} = \sum \limits ^{B^{\text {max}}}_{r = 1}\sum \limits _{t \in \mathcal {T}^{\text {brE}}(r)} b^{\text {end}}_{r,w,d,t} \nonumber \\&\qquad \forall \ w \in \mathcal {W}, d \in \mathcal {D}(p_w) \end{aligned}$$
(54)
$$\begin{aligned}&z_{w,q,d,t} \in \left\{ 0,1\right\} \quad \forall \ w \in \mathcal {W}, d \in \mathcal {D}(p_w), t \in \mathcal {T} \end{aligned}$$
(55)
$$\begin{aligned}&b^{\text {start}}_{r,w,d,t}, b^{\text {end}}_{r,w,d,t'},b^{\text {last}}_{w,d,t'} {\in } \left\{ 0,1\right\} \nonumber \\&\qquad \forall \ w {\in } \mathcal {W}, d {\in } \mathcal {D}(p_w), t {\in } \mathcal {T}^{\text {brS}}, t' {\in } \mathcal {T}^{\text {brE}} 1 {\le } r {\le } B^{\text {max}} \end{aligned}$$
(56)
The last set of constraints (
52)–(
54) define general modeling requirements. Logically, the
rth subbreak can only be started if its immediate predecessor subbreak
\(r1\) has been started [constraints (
52)]. Also, the unique starting period of each subbreak is defined in constraints (
53) and, due to constraints (
54), a subbreak can only end if it has been started.
If we consider breaks with time windows in the GHSP, i.e., BAP
\(\left\{ \cdot \cdot  T\right\} \), the above model has to be slightly modified. Let
\(\Delta ^{\text {minTW}}\) and
\(\Delta ^{\text {maxTW}}\) be the minimal and maximal number of periods of the
rth subbreak, respectively, for
\(r > 1\) from the shift start. Then we replace the twosided constraints (
46) with
which is analogous to constraints (
43) for the first subbreaks.
$$\begin{aligned}&\Delta ^{\text {maxTW}}_r \ge \sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} t \cdot b^{\text {start}}_{r,w,d,t}  \sum \limits _{m \in \mathcal {M}(d,p_w)}\sum \limits _{t \in \mathcal {T}^{\text {shS}}(m)} t\\&\quad \cdot y_{m,w,d,t} \Delta ^{\text {minTW}}_r \\&\quad \quad \ge \sum \limits _{m \in \mathcal {M}(d,p_w)} \Delta ^{\text {minTW}}_r \cdot y_{m,w,d,t}\\&\quad \forall \ w \in \mathcal {W}, d \in \mathcal {D}(p_w), 1 < r \le B^{\text {max}} \end{aligned}$$
(46')
Appendix C: Implicit BAP formulation based on Aykin’s approach
For shift scheduling, Rekik et al. (
2010) present a model with fractionable breaks based on the implicit formulation for multiple breaks first introduced by Aykin (
1996). In the following, we show how their approach can be adapted for the tour scheduling problem with a hierarchical workforce as was discussed in Sect.
5.2. The additional sets required for the model are listed in Table
15.
Table 15
Sets used in implicit break assignment model IBAP2
Sets

Description


\(\mathcal {J}_{s,q}\)

Set of shift profiles associated with shift
s and skill
q

\(\mathcal {K}_{j(r)}\)

Set of subbreaks admissible as
r’th subbreak in shift profile
j

\(\mathcal {Q}\)

Set of skills

We make use of the definitions of shift profiles and break profiles in Sect.
5.2 and similarly, define a subbreak
\(k \in \mathcal {K}\) for each break profile, each position in the break profile, each possible starting time, and each skill level. Also, we need a unique subbreak for each skill level since we have to consider the skill of the worker that is taking the break. Instead of assigning subbreaks explicitly to shifts, a variable
\(X_{j,k}\) is defined that stores how often subbreak
\(k \in \mathcal {K}\) is assigned to shift profile
\(j \in J\).
To obtain a feasible solution with regard to workstretch durations, the feasibility of transportation problems between successive breaks has to be ensured. The following set is used to construct the problems.
Based on the break starting times, a totally ordered relationship
\(\prec \) on
\(\mathcal {K}_{j(r)}\) is defined. Then, a transportation problem
\(T(\mathcal {K}_{j(r)},\mathcal {K}_{j(r+1)})\) from the nodes in
\(\mathcal {K}_{j(r)}\) to the nodes in
\(\mathcal {K}_{j(r+1)}\) can be established for each
\(j \in \mathcal {J}\) and each
\(r \in {1,\ldots ,B_j1}\). Nodes
\(k_1 \in \mathcal {K}_{j(r)}\) and
\(k_2 \in \mathcal {K}_{j(r+1)}\) are connected if the workstretch duration between their corresponding breaks is within the interval
\([ \delta ^{\text {minBW}}\),
\(\delta ^{\text {maxBW}}]\). The feasibility of the transportation problem ensures that there are enough successor breaks for all subbreaks
k that are assigned to shift profile
j and is guaranteed by a set of forward and backward constraints based on the principles described in Sect.
5.2.
$$\begin{aligned} \mathcal {K}_{j(r)}&= \textit{set of subbreaks admissible as rth sub}\\ {}&\quad \textit{break in shift profile j} \end{aligned}$$
Also, because there are no pairs of nodes
\(k_1, k_2 \in \mathcal {K}_{j(r)}\) for which
\(\mathcal {K}^{\text {suc}}_{k_1} \subset \mathcal {K}^{\text {suc}}_{k_2}\), there is no extraordinary overlap.
In the formulation, we make use of the following additional parameters and variables:
Parameters
Variables
Implicit BAP formulation II (IBAP2)
Constraints (
58) determine the amount of demand for skill level
q on day
d in period
t that cannot be covered, while constraints (
59) ensure that all shifts of type
s for workers with skill
q are connected to a shift profile
j. Due to constraints (
60), the number of subbreaks for shift
j in each break position
\(r \in \left\{ 1,\ldots ,B_j\right\} \) corresponds to the number of shifts of type
j. Further, there cannot be more workers with skill
\(\hat{q}\) that take a break from a job requiring skill
q in period
t then there are workers in the input tour plan with skill
\(\hat{q}\) carrying out a job in period
t that requires skill
q. This is enforced by (
61). In addition, all breaks taken in period
t by workers with skill level
\(\hat{q}\) must be distributed among jobs requiring at most skill
\(\hat{q}\). This is enforced by (
62). Constraints (
63) and (
64), respectively, are the forward and backward constraints used to ensure that the total number of subbreaks is correct. Equality constraints for the total subbreak supply and demand are not needed due to constraints (
60). Variables are defined in (
65) and (
66).

\(B_j\) = number of subbreaks in shift j

\(X_{j,k}\) = number of workers assigned to shift j that are given subbreak k
$$\begin{aligned}&\hbox {Minimize} \sum \limits _{q \in \mathcal {Q}}\sum \limits _{t \in \mathcal {T}} c^{\text {uc}} \cdot y^{}_{q,t} {} \sum \limits _{j \in \mathcal {J}}\sum \limits _{r \in \left\{ 1,\ldots ,B_j\right\} }\sum \limits _{k \in \mathcal {K}_{j(r)}} c^{\text {work}}\nonumber \\&\quad \cdot d_{k} \cdot X_{j,k} \end{aligned}$$
(57)
$$\begin{aligned} \hbox {subject to} \nonumber \\&\sum \limits _{\hat{q} \ge q} P_{\hat{q},q,t} + y^{+}_{q,t}  y^{}_{q,t} = D_{q,d,t} \quad \forall \ q \in \mathcal {Q}, t \in \mathcal {T} \end{aligned}$$
(58)
$$\begin{aligned}&\sum \limits _{j \in \mathcal {J}_{s,q}} S_j = h_{s,q} \quad \forall \ s \in \mathcal {S}, q \in \mathcal {Q} \end{aligned}$$
(59)
$$\begin{aligned}&\sum \limits _{k \in \mathcal {K}_{j(r)}} X_{j,k}  S_j = 0 \quad \forall \ j \in \mathcal {J}, r \in \left\{ 1,\ldots ,B_j\right\} \end{aligned}$$
(60)
$$\begin{aligned}&P_{\hat{q},q,t} \le l_{\hat{q},q,t} \quad \forall \ \hat{q}, q \in \mathcal {Q}: q \le \hat{q}, t \in \mathcal {T} \end{aligned}$$
(61)
$$\begin{aligned}&\sum \limits _{q \le \hat{q}} P_{\hat{q},q,t} {=} \sum \limits _{j \in \mathcal {J}_{\hat{q}}}\sum \limits _{r {\in } \left\{ 1,\ldots ,B_j\right\} }\sum \limits _{k \in \mathcal {K}_{j(r)}} X_{j,k} \cdot \rho _{t,k} \quad \forall \ \hat{q} {\in } \mathcal {Q}, t {\in } \mathcal {T} \end{aligned}$$
(62)
$$\begin{aligned}&\sum \limits _{k' \in \mathcal {K}^{F}_{j(r+1)}(k)} X_{j,k'}  \sum \limits _{k' \in \mathcal {K}^{F}_{j(r)}(k)} X_{j,k'} \ge 0\nonumber \\&\quad \begin{array}{ll} \forall \ j \in \mathcal {J}, r \in \left\{ 1,\ldots ,B_j1\right\} , \\ k \in \mathcal {K}^{\text {e}}_{j(r+1)} \setminus \left\{ k^{\text {e}}_{j(r+1)} \right\} \end{array} \end{aligned}$$
(63)
$$\begin{aligned}&\sum \limits _{k' \in \mathcal {K}^{B}_{j(r+1)}(k)} X_{j,k'}  \sum \limits _{k' \in \mathcal {K}^{B}_{j(r)}(k)} X_{j,k'} \ge 0\nonumber \\&\quad \begin{array}{ll} \forall \ j \in \mathcal {J}, r \in \left\{ 1,\ldots ,B_j1\right\} , \\ k \in \mathcal {K}^{\text {s}}_{j(r+1)} \setminus \left\{ k^{\text {s}}_{j(r+1)} \right\} \end{array} \end{aligned}$$
(64)
$$\begin{aligned}&S_j, w_{w,t},P_{\hat{q},q,t} \in \mathbb {Z}_+ \quad \forall \ j \in \mathcal {J}, \hat{q}, q \in \mathcal {Q}: q \le \hat{q}, t \in \mathcal {T} \end{aligned}$$
(65)
$$\begin{aligned}&X_{j,k} \in \mathbb {Z}_+ \quad \forall \ j \in \mathcal {J}, k \in \bigcup _{r \in \left\{ 1,\ldots ,B_j\right\} } \mathcal {K}_{j(r)} \end{aligned}$$
(66)
Appendix D: Implicit BAP formulation III
The BAP formulation contained in CMIP is stated below using the following additional notation.
Parameters
Variables
Implicit BAP formulation III (IBAP3)
Constraints (
68)–(
85) are equivalent to (
42)–(
54), but now workers’ shifts
\(\mathcal {S}^*(d)\) for each day
\(d \in \mathcal {D}\) are provided by Algorithm 1.

\(S^{\text {start}}_{s} =\) start time of shift s

\(S^{\text {end}}_{s} =\) end time of shift s

\(C^{\text {work}}_s\) = cost for shift s (without breaks)

\(b^\text {start}_{r,s,t} = 1\), if the rth subbreak for shift s starts at time t, 0 otherwise

\(b^{\text {end}}_{r,s,t} = 1\), if the rth subbreak for shift s ends at time t, 0 otherwise

\(b^{\text {last}}_{s,t} = 1\), if the last subbreak for shift s ends at time t, 0 otherwise

\(a_{s,t} = 1\), if there is a break in shift s at time t, 0 otherwise

\(z_{s,q,t} = 1\), if period t is a working period for shift s that covers skill level q, 0 otherwise
$$\begin{aligned}&\hbox {Minimize} \sum \limits _{t \in \mathcal {T}} \left( \sum \limits _{s \in \mathcal {S}} c^{\text {work}} \cdot a_{s,t} + \sum \limits _{q \in \mathcal {Q}} c^{\text {uc}} \cdot y^{}_{q,t} \right) \end{aligned}$$
(67)
$$\begin{aligned}&\hbox {subject to} \nonumber \\&\sum \limits _{s \in \mathcal {S}(q,t)} a_{s,t}  y^{}_{q,t} + y^{+}_{q,t} = D_{q,d,t} \quad \forall \ q \in \mathcal {Q}, t \in \mathcal {T} \end{aligned}$$
(68)
$$\begin{aligned}&\sum \limits ^{B^{\text {max}}}_{r = 1} \sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} b^{\text {start}}_{r,s,t} \ge B^{\text {min}} \quad \forall \ s \in \mathcal {S}^*(d) \end{aligned}$$
(69)
$$\begin{aligned}&\Delta ^{\text {minBF}} \le \left( \sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} t \cdot b^{\text {start}}_{1,s,t}  S^{\text {start}}_{s} \right) \le \Delta ^{\text {maxBF}} \quad \forall \ s \in \mathcal {S}^*(d) \end{aligned}$$
(70)
$$\begin{aligned}&\Delta ^{\text {minBD}}_{r} \cdot \sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} b^{\text {start}}_{r,s,t} \le \sum \limits _{t \in \mathcal {T}^{\text {brE}}(r)} t \cdot b^{\text {end}}_{r,s,t} \nonumber \\&\quad \quad \quad \sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} t \cdot b^{\text {start}}_{r,s,t} \le \Delta ^{\text {maxBD}}_{r} \quad \forall \ s \in \mathcal {S}^*(d), 1 \le r \le B^{\text {max}} \end{aligned}$$
(71)
$$\begin{aligned}&\Delta ^{\text {minBD}} \le \sum \limits ^{B^{\text {max}}}_{r = 1} \left( \sum \limits _{t \in \mathcal {T}^{\text {brE}}(r)} t \cdot b^{\text {end}}_{r,s,t}  \sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} t \cdot b^{\text {start}}_{r,s,t}\right) \nonumber \\&\quad \le \Delta ^{\text {maxBD}} \quad \forall \ s \in \mathcal {S}^*(d) \end{aligned}$$
(72)
$$\begin{aligned}&\Delta ^{\text {minBW}}_{r} \cdot \sum \limits _{t \in \mathcal {T}^{\text {brS}}(r+1)} b^{\text {start}}_{r+1,s,t} \le \sum \limits _{t \in \mathcal {T}^{\text {brS}}(r+1)} t \cdot b^{\text {start}}_{r+1,s,t}  \nonumber \\&\quad \quad \sum \limits _{t \in \mathcal {T}^{\text {brE}}(r)} t \cdot b^{\text {end}}_{r,s,t} \le \Delta ^{\text {maxBW}}_{r} \quad \forall \ s \in \mathcal {S}^*(d), 1 \le r \le B^{\text {max}}  1 \end{aligned}$$
(73)
$$\begin{aligned}&S^{\text {end}}_{s,d}  \Delta ^{\text {minBL}} \ge \left( \sum \limits _{t \in \mathcal {T}^{\text {brE}}} t \cdot b^{\text {last}}_{s,t} \right) \ge S^{\text {end}}_{s}  \Delta ^{\text {maxBL}} \quad \forall \ s \in \mathcal {S}^*(d) \end{aligned}$$
(74)
$$\begin{aligned}&\sum \limits _{t \in \mathcal {T}^{\text {brE}}} t \cdot b^{\text {last}}_{s,t} \ge \left( \sum \limits _{t \in \mathcal {T}^{\text {brE}}(r)} t \cdot b^{\text {end}}_{r,s,t} \right) \quad \forall \ s \in \mathcal {S}^*(d), B^{\text {min}} \le r \le B^{\text {max}} \end{aligned}$$
(75)
$$\begin{aligned}&\sum \limits _{t \in \mathcal {T}^{\text {brE}}} \left( t  1 \right) \cdot b^{\text {last}}_{s,t} \le \sum \limits _{t \in \mathcal {T}^{\text {brE}}(r)} t \cdot b^{\text {end}}_{r,s,t} + \nonumber \\&\quad \quad \quad \sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} b^{\text {start}}_{r+1,s,t} \cdot S^{\text {end}}_{s,d} \quad \forall \ s \in \mathcal {S}^*(d), B^{\text {min}} \le r < B^{\text {max}} \end{aligned}$$
(76)
$$\begin{aligned}&\sum \limits _{t \in \mathcal {T}^{\text {brE}}} \left( t  1 \right) \cdot b^{\text {last}}_{s,t} \le \sum \limits _{t \in \mathcal {T}^{\text {brE}}(B^{\text {max}})} t \cdot b^{\text {end}}_{B^{\text {max}},s,t} + \nonumber \\&\quad \quad \quad \left( 1 \sum \limits _{t \in \mathcal {T}^{\text {brS}}(B^{\text {max}})} b^{\text {start}}_{B^{\text {max}},s,t}\right) \cdot S^{\text {end}}_{s,d}\quad \forall \ s \in \mathcal {S}^*(d) \end{aligned}$$
(77)
$$\begin{aligned}&\sum \limits _{t \in \mathcal {T}^{\text {brE}}} b^{\text {last}}_{s,t} = 1 \quad \forall \ s \in \mathcal {S}^*(d) \end{aligned}$$
(78)
$$\begin{aligned}&\sum \limits ^{B^{\text {max}}}_{r = 1}\sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} b^{\text {start}}_{r,s,t} = \sum \limits ^{B^{\text {max}}}_{r = 1}\sum \limits _{t \in \mathcal {T}^{\text {brE}}(r)} b^{\text {end}}_{r,s,t} \quad \forall \ s \in \mathcal {S}^*(d) \end{aligned}$$
(79)
$$\begin{aligned}&\sum \limits ^{B^{\text {max}}}_{r = 1} \left( \sum \limits _{l \in \mathcal {T}^{\text {brS}}(r): l \ge t} b^{\text {start}}_{r,s,l}  \sum \limits _{l \in \mathcal {T}^{\text {brE}}(r): l \ge t} b^{\text {end}}_{r,s,l}\right) = a_{s,t}\nonumber \\&\quad \forall \ s \in \mathcal {S}^*(d), S^{\text {start}}_s \le t \le S^{\text {end}}_s \end{aligned}$$
(80)
$$\begin{aligned}&\sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} b^{\text {start}}_{r,s,t} \le 1 \wedge \sum \limits _{t \in \mathcal {T}^{\text {brE}}(r)} b^{\text {end}}_{r,s,t} \le 1 \quad \forall \ 1 \le r \le B^{\text {max}}, s \in \mathcal {S}^*(d) \end{aligned}$$
(81)
$$\begin{aligned}&\sum \limits _{t \in \mathcal {T}^{\text {brS}}(r+1)} b^{\text {start}}_{r+1,s,t} \le \sum \limits _{t \in \mathcal {T}^{\text {brS}}(r)} b^{\text {start}}_{r,s,t} \forall \ 1 \le r < B^{\text {max}}, s \in \mathcal {S}^*(d) \end{aligned}$$
(82)
$$\begin{aligned}&b^{\text {start}}_{r,s,t}, b^{\text {end}}_{r,s,t'},b^{\text {last}}_{s,t''} \in \left\{ 0,1\right\} \nonumber \\&\quad \begin{array}{ll} \forall \ s \in \mathcal {S}^*(d), B^{\text {min}} \le r \le B^{\text {max}}, t \in \mathcal {T}^{\text {brS}}(r), t' \in \mathcal {T}^{\text {brE}}(r), \\ t'' \in \mathcal {T}^{\text {brE}} \end{array} \end{aligned}$$
(83)
$$\begin{aligned}&a_{s,t} \in \left\{ 0,1\right\} \quad \forall \ s \in \mathcal {S}^*(d), q \in \mathcal {Q}, S^{\text {start}}_{s} \le t \le S^{\text {end}}_{s} \end{aligned}$$
(84)
$$\begin{aligned}&y^+_{q,t},y^_{q,t} \ge 0 \quad \forall \ q \in \mathcal {Q}, S^{\text {start}}_{s} \le t \le S^{\text {end}}_{s} \end{aligned}$$
(85)
×
Appendix E: Low demand curves
See Fig.
8.
Table 16
Results for the CMIP and the MIPheuristic for break regulation
\(\left\{ S  V  T \right\} \)
Instance

CMIP

MIPheuristic



Obj

Undercov

Runtime (s)

Obj

Undercov

Runtime

GAP*


\(\left\{ 10,\text {low, SD},\text {fix}\right\} \)

7, 570

6, 520

15.77

7, 570

6, 520

3.68

0.00

\(\left\{ 20,\text {low, SD},\text {fix}\right\} \)

7, 680

5, 055

30.92

7, 680

5, 055

4.45

0.00

\(\left\{ 30,\text {low, SD},\text {fix}\right\} \)

8, 035

4, 010

78.81

8, 035

4, 010

8

0.00

\(\left\{ 40,\text {low, SD},\text {fix}\right\} \)

8, 695

3, 095

272

8, 750

3, 150

9.42

0.63

\(\left\{ 50,\text {low, SD},\text {fix}\right\} \)

9, 805

2, 630

268.53

9, 975

2, 800

9.51

1.7

\(\left\{ 65,\text {low, SD},\text {fix}\right\} \)

11, 150

2, 050

55.3

11, 450

2, 360

11.8

2.71

\(\left\{ 10,\text {low, SD},\text {flex}\right\} \)

7, 350

6, 033

33.9

7, 350

5, 690

8.82

0.00

\(\left\{ 20,\text {low, SD},\text {flex}\right\} \)

7, 350

5, 447

94.78

7, 350

4, 595

6.83

0.00

\(\left\{ 30,\text {low, SD},\text {flex}\right\} \)

7, 350

4, 652

1, 147.93

7, 350

3, 620

8.53

0.00

\(\left\{ 40,\text {low, SD},\text {flex}\right\} \)

7, 350

3, 857

2, 868.06

7, 350

3, 220

13.45

0.00

\(\left\{ 50,\text {low, SD},\text {flex}\right\} \)

7, 350

3, 328

10, 074.84

7, 350

3, 010

12.72

0.00

\(\left\{ 65,\text {low, SD},\text {flex}\right\} \)

7, 380

2, 077

14, 074

7, 420

2, 495

57.436

0.54

\(\left\{ 10,\text {low, VD},\text {fix}\right\} \)

9, 086

8, 036

2.6

9, 086

8, 036

1.34

0.00

\(\left\{ 20,\text {low, VD},\text {fix}\right\} \)

9, 121

6, 496

8.48

9, 141

6, 517

2.14

0.22

\(\left\{ 30,\text {low, VD},\text {fix}\right\} \)

9, 283

5, 258

99.49

9, 307

5, 245

5.92

0.26

\(\left\{ 40,\text {low, VD},\text {fix}\right\} \)

9, 663

3, 957

748.99

9, 851

5, 599

10.64

1.91

\(\left\{ 50,\text {low, VD},\text {fix}\right\} \)

10, 188

3, 013

830.01

10, 486

3, 311

12.58

2.84

\(\left\{ 65,\text {low, VD},\text {fix}\right\} \)

11, 234

2, 134

499, 07

11, 671

2, 572

12, 76

3.74

\(\left\{ 10,\text {low, VD},\text {flex}\right\} \)

9, 084

7, 857

20.55

9, 089

7, 133

4.93

0.01

\(\left\{ 20,\text {low, VD},\text {flex}\right\} \)

9, 084

7, 070

436.42

9, 105

5, 759

11.72

0.23

\(\left\{ 30,\text {low, VD},\text {flex}\right\} \)

9, 084

6, 158

2, 243.9

9, 113

4, 740

21.34

0.32

\(\left\{ 40,\text {low, VD},\text {flex}\right\} \)

9, 084

5, 028

5, 326.08

9, 147

3, 850

36.08

0.69

\(\left\{ 50,\text {low, VD},\text {flex}\right\} \)

9, 084

4, 546

8, 343.92

9, 185

3, 503

87.52

1.10

\(\left\{ 65,\text {low, VD},\text {flex}\right\} \)

9, 368

3, 727

18, 000

9, 518

3, 225

614.95

1.58

Appendix F: Results of computational study
See Tables
16,
17 and
18.
Table 17
Results for the CMIP and the MIPheuristic for break regulation
\(\left\{ F  V  W \right\} \)
Instance

CMIP

MIPheuristic



Obj

Undercov

Runtime (s)

Obj

Undercov

Runtime (s)

GAP*

GAP


\(\left\{ 10,\text {low, SD},\text {fix}\right\} \)

7, 510

6, 460

32.32

7, 510

6, 460

3.56

0.00


\(\left\{ 20,\text {low, SD},\text {fix}\right\} \)

7, 590

4, 965

189.32

7, 590

4, 965

4.10

0.00


\(\left\{ 30,\text {low, SD},\text {fix}\right\} \)

7, 890

3, 865

1, 076.60

7, 900

3, 875

13.92

0.13


\(\left\{ 40,\text {low, SD},\text {fix}\right\} \)

8, 412

2, 813

2, 454.28

8, 550

2, 740

19.55

1.61


\(\left\{ 50,\text {low, SD},\text {fix}\right\} \)

9, 487

2, 312

2, 744.08

9, 640

2, 465

22.21

1.59


\(\left\{ 65,\text {low, SD},\text {fix}\right\} \)

11, 164

2, 064

29.47

7.52


\(\left\{ 10,\text {low, SD},\text {flex}\right\} \)

7, 350

5, 690

203.92

7, 350

5, 690

9.05

0.00


\(\left\{ 20,\text {low, SD},\text {flex}\right\} \)

7, 350

4, 595

11.16

0.32


\(\left\{ 30,\text {low, SD},\text {flex}\right\} \)

7, 350

3, 620

13.62

0.78


\(\left\{ 40,\text {low, SD},\text {flex}\right\} \)

7, 350

3, 220

15.20

0.96


\(\left\{ 50,\text {low, SD},\text {flex}\right\} \)

7, 350

3, 010

17.71

1.12


\(\left\{ 65,\text {low, SD},\text {flex}\right\} \)

7, 420

2, 495

59.18

0.94


\(\left\{ 10,\text {low, VD},\text {fix}\right\} \)

9, 084

8, 034

31.97

9, 086

8, 036

3.54

0.02


\(\left\{ 20,\text {low, VD},\text {fix}\right\} \)

9, 108

6, 483

164.98

9, 133

6, 500

4

0.27


\(\left\{ 30,\text {low, VD},\text {fix}\right\} \)

9, 247

5, 222

4, 345.21

9, 247

5, 222

13.32

0.43


\(\left\{ 40,\text {low, VD},\text {fix}\right\} \)

9, 545

3, 839

7, 938, 34

9, 545

3, 862

14.29

1.37


\(\left\{ 50,\text {low, VD},\text {fix}\right\} \)

9, 784

2, 564

10, 800.3

10, 243

3, 068

18.21

4.48


\(\left\{ 65,\text {low, VD},\text {fix}\right\} \)

11, 443

2, 343

42.01

9.33


\(\left\{ 10,\text {low, VD},\text {flex}\right\} \)

9, 084

7, 580

843.80

9, 084

7, 128

8.72

0.00


\(\left\{ 20,\text {low, VD},\text {flex}\right\} \)

9, 087

5, 741

12.20

0.12


\(\left\{ 30,\text {low, VD},\text {flex}\right\} \)

9, 093

4, 720

28.30

0.42


\(\left\{ 40,\text {low, VD},\text {flex}\right\} \)

9, 128

3, 831

43.16

1.00


\(\left\{ 50,\text {low, VD},\text {flex}\right\} \)

9, 160

3, 478

98.51

1.35


\(\left\{ 65,\text {low, VD},\text {flex}\right\} \)

10, 367

4, 286

628.68

1.64

Table 18
Comparison of implicit BAP formulations for break regulation
\(\left\{ S  V  T\right\} \)
Instance

IBAP I

IBAP II

IBAP IIi



Comp (s)

Pre (s)

#Var

#Constr

Comp (s)

Pre (s)

#Var

#Constr

Time (s)

#Var

#Constr


\(\left\{ 10,\text {low, SD, fix}\right\} \)

1.35

0.02

2, 803.71

2, 727.43

1.08

0.03

2, 730.86

2, 721.43

2.89

790.29

2, 823.43

\(\left\{ 50,\text {low, SD, fix}\right\} \)

1.74

0.07

3, 411.86

3, 204.86

1.63

0.4

3, 237.43

3, 195

5.26

12, 573

2, 040.29

\(\left\{ 100,\text {low, SD, fix}\right\} \)

1.97

0.09

3, 433.29

3, 211.71

1.26

0.9

3, 252.86

3, 201

25.26

23, 994.86

3, 973.14

\(\left\{ 10,\text {low, SD, flex}\right\} \)

0.67

0.05

3, 485.71

3, 185.43

0.57

0.04

3, 200.86

3, 178.86

0.58

2, 699.14

898.86

\(\left\{ 50,\text {low, SD, flex}\right\} \)

1.76

0.18

3, 641

3, 214

1.46

0.03

3, 283

3, 203

1.56

5, 982

1, 511

\(\left\{ 100,\text {low,SD, flex}\right\} \)

13.34

0.58

3, 555.43

3, 234.29

10.73

1

3, 345.43

3, 222

3.26

10, 418.57

2, 314

\(\left\{ 10,\text {low, VD, fix}\right\} \)

1.47

0.02

2, 821.86

2, 735.43

1.4

0.4

2, 748.86

2, 728.43

0.14

2, 013.43

756

\(\left\{ 50,\text {low, VD, fix}\right\} \)

2.18

0.17

3, 462.14

3, 271.14

1.86

0.4

3, 386.57

3253

2, 07

7, 653.43

1, 806

\(\left\{ 100,\text {low,VD, fix}\right\} \)

2.31

0.18

3, 460.43

3, 264.29

2.9

0.32

3, 371.14

3, 247

13.26

14, 154.86

3, 036

\(\left\{ 10,\text {low, VD, flex}\right\} \)

0.98

0.14

3, 544.43

3, 126.29

1.73

0.02

3, 276.43

3, 201

0.51

2, 826

941.14

\(\left\{ 50,\text {low, VD, flex}\right\} \)

1.83

0.63

3, 779.29

3, 385.43

0.34

0.04

3, 332.57

3, 357

2.51

6, 879.86

1, 725.43

\(\left\{ 100,\text {low, VD, flex}\right\} \)

1.77

2.19

3, 658.14

3, 267.14

1.07

0.23

3, 440.71

3, 251

4.71

10, 366.29

2, 243.43

\(\left\{ 200,\text {high, SD, fix}\right\} \)

1.72

0.23

3, 427

3, 216.29

2.75

0.05

3, 263.14

3, 205

18.97

27, 157.71

5, 496

\(\left\{ 250,\text {high, SD, fix}\right\} \)

3.15

0.29

3, 450.14

3, 243.71

2.73

0.06

3, 324.86

3229

19.5

33, 659.14

6, 726

\(\left\{ 300,\text {high, SD, fix}\right\} \)

2.55

0.2

3459.14

3, 247.14

2

0.04

3, 332.57

3232

20.96

40, 160.57

7, 956

\(\left\{ 200,\text {high, SD, flex}\right\} \)

2.02

0.44

3, 516.29

3, 318.57

1.8

0.08

3, 605

3, 301

10.16

25, 488

5, 571.43

\(\left\{ 250,\text {high, SD, flex}\right\} \)

1.55

0.59

3, 569

3, 329.71

0.23

0.27

3, 595.14

3, 298

11.92

26, 324.14

5591.71

\(\left\{ 300,\text {high, SD, flex}\right\} \)

1.2

0.16

3, 561, 86

3, 238.57

1.57

1.19

3, 624.71

3, 307

16.96

28, 550.86

5, 658.86

\(\left\{ 200,\text {high, VD, fix}\right\} \)

2.96

0.32

3, 461.57

3, 266.57

3.22

0.06

3, 376.29

3, 249

17.34

27, 157.71

5, 496

\(\left\{ 250,\text {high, VD, fix}\right\} \)

2.88

0.35

3, 457

3, 264.29

1.38

0.04

3, 371.14

3, 247

22.17

33, 659.14

6, 726

\(\left\{ 300,\text {high, VD, fix}\right\} \)

2.2

0.26

3, 458.71

3, 264.29

2.76

0.04

3, 371.14

3, 247

27.76

40, 160.57

7, 956

\(\left\{ 200,\text {high, VD, flex}\right\} \)

2.65

0.94

3, 613.86

3, 281.21

1.73

0.17

3, 486.71

3, 265

13.3

25, 488

5, 571.43

\(\left\{ 250,\text {high, VD, flex}\right\} \)

2.06

0.24

3, 573.43

3, 234

4.15

1.41

3, 345.43

3, 222

20.03

27, 343.34

6, 432.32

\(\left\{ 300,\text {high, VD, flex}\right\} \)

5.02

0.36

3, 596.71

3, 234.86

2.43

0.43

3, 348.71

3, 223

29.03

29.038.32

8, 231.21

Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.