The flexible break assignment problem for large tour scheduling problems with an application to airport ground handlers

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 (days-off 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 non-peak demand can be as large as three to one over the day. Meeting the demand without an excess of under- or over-coverage 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.

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 stand-alone problem, the BAP arises in daily break planning as well as intraday break assignment and the presented implicit models can incorporate a hierarchical multi-skill workforce. Other decomposition approaches based on branch and price turned out to be intractable for such large-scale real-world application considering individual workers and complex break regulations. The presented heuristic is flexible enough to be adopted to many real-world 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 mixed-integer 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.

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.

The first integer programming formulation for personnel scheduling problems was given by Dantzig (1954) who introduced a set-covering 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 set-covering-based formulation for the tour scheduling problem for check-in 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 multi-activity 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 cost-based 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 set-covering formulation proposed by Stolletz (2010) could be solved to optimality with off-the-shelf 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 15-day planning horizon with 34 periods per day, and an upper bound of 435 shifts per day (without breaks). In contrast, we consider a 7-day 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 NP-hard, finding optimal solutions to real-world 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 programming-based algorithm. Taking a behavior-based 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 days-on and days-off assignments matched employee requests. Finally, Lusby et al. (2011) tackled a ground crew rostering problem for a European airline using a column generation-based heuristic. Their goal was to create long-term rosters based on 6 days-on, 3 days-off 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 set-covering-type 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 post-processing 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 sub-breaks 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 sub-breaks with the restriction that the number of sub-breaks is within a predefined range. In their work, sub-break 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 post-processor 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.

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, mid-day or late). The set of all feasible shifts is denoted by \(\mathcal {S}\).

To illustrate the concept of a template, consider a one-week 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.

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 real-world 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 statute-based, 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.

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 sub-break 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:

Given the parameters in B1 to B6, the range of sub-break 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 sub-breaks 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 shift-covering 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.

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.

It is well known that tour scheduling problems are NP-hard (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.

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.

In the GHSP under investigation, we have to tackle two NP-hard problems: the tour scheduling problem (TShP) and the (fractionable) BAP\(\{F|V|W\}\). 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\(\{F|V|W\}\) (Sect. 5.2).

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 ninety-six, 15-min 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, 15-minute 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.

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 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 sub-break 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 sub-breaks have to be assigned. To guarantee a total break length of 6, in multiple break scenario \(\left\{ M | X | T \right\} \) with fixed sub-break length, each sub-break is 2 periods, while in multiple break scenario \(\left\{ M | V | T \right\} \) with variable sub-break length, each sub-break 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 sub-breaks can be assigned to each shift, which are either based on time windows or workstretch durations. The time windows for the second and third sub-breaks 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 sub-breaks after the first sub-break is from 3 to 24 periods (column “WS”).

With respect to demand, both low- and high-level 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 low-level 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 4-tuple 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 MIP-heuristic 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.

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 three-field classification scheme for the various models. An accompanying complexity analysis showed that all but the simplest of problems are strongly NP-hard. 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 large-scale instances, a MIP-decomposition 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 post-processing 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 short-term disruption scenarios.