Ferdinand Kiermaier

The paper examines the complexity of assigning multiple breaks to shifts in the context of large-scale tour scheduling. A mixed-integer programming (MIP) model is presented that includes shift and days-off scheduling along with break assignments for a multi-skilled workforce. To achieve tractability, a two-stage decomposition procedure is proposed that separates the tour scheduling problem (TShP) from the break assignment problem (BAP). The former MIP is first solved to determine the shifts and days off for the workforce that minimize labor and shortages costs over the planning horizon. The results are used as input to a second MIP that optimally places the breaks to minimize the costs of working hours and uncovered periods. Three implicit BAP formulations are investigated. To better understand the literature and the models previously developed, a 3-field break classification scheme is introduced. The first field characterizes the number of breaks permitted per shift, the second specifies whether the length of the breaks is fixed or variable, and the third limits their position in a shift. A complexity analysis of the resulting 12 BAPs along with a few special cases is also included. Most problems are shown to be strongly NP-hard. Computations are presented for a wide variety of scenarios for both the TShP and the BAP using data provided by a European airport ground handler company. In all, over 500 instances were investigated using high and low demand fluctuation curves and the various break and shift flexibility options. The results indicate that increasing flexibility in break regulations can make a significant difference in coverage, but the degree depends on the underlying structure of the demand curve as well as on the types of shifts permitted. Formulations with the most flexible shift and break regulations reduced undercoverage by up to 16.68% compared to the most common scenarios in which shifts are limited to a single lunch break.

Companies in the service industry frequently depend on cyclic rosters to schedule their workforce. Such rosters offer a high degree of fairness and long-term predictability of days on and off, but they can hinder an organization’s ability to respond to changing demand. Motivated by the need for improving cyclic planning at an airport ground handling company, this article introduces the idea of flexible cyclic rostering as a means of accommodating limited weekly adjustments of employee schedules. The problem is first formulated as a multi-stage stochastic program; however, this turned out to be computationally intractable. To find solutions, two approximations were developed that involved reductions to a two-stage problem. In the computational study, the flexible and traditional cyclic rosters derived from these approximations are compared and metrics associated with the value of stochastic information are reported. In the testing, we considered seven different perturbations of the demand curve that incorporate the types of uncertainty that are common throughout the service industry. To the best of our knowledge, this is the first analysis of cyclic rostering that applies stochastic optimization. The results show that a reduction in undercoverage of more than 10% on average can be achieved with minimal computational effort. It was also observed that the new approach can overcome most of the limitations of traditional cyclic rostering while still providing most of its advantages.