A stochastic optimization approach to shift scheduling with breaks adjustments. (July 2019)

• Record Type: Journal Article
• Authors: Hur, Youngbum; Bard, Jonathan F.; Frey, Markus; Kiermaier, Ferdinand
• Is Part Of: Computers & operations research. Volume 107(2019)
• Page Start: 127
• Page End: 139
• Publication Date: 2019-07
• Subjects: Shift scheduling -- Flexible breaks -- Stochastic optimization -- Baggage handlers -- Lagrangian relaxation; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2019.03.012
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A multi-stage stochastic model for the shift scheduling problem with flexible breaks and the presentation of a more tractable two-stage stochastic optimization model. An analysis of the benefits of using flexible breaks for a daily shift scheduling problem under stochastic demand. A Lagrangian-based lower bound for the stochastic solution. An analysis of the value of a stochastic model for scheduling airport ground handlers using two metrics: VSS and EVPI . A comparison of results obtained for the stochastic model with those from a rolling horizon procedure that makes break adjustments in a real-time. Abstract : The purpose of this paper is to investigate a daily shift scheduling problem with flexible breaks under stochastic demand that allows for break adjustments on the day of operation. For a given workforce, we wish to provide managers with a means of quickly constructing shifts that are sufficiently robust to handle uncertain demand as it unfolds. The problem is formulated as a multi-stage stochastic program and then transformed into a two-stage model to achieve computational tractability. Five different break models are considered for both fixed and flexible shift types. Using data from an airport ground services company, 61 scenarios are employed for testing purposes. In the first phase of the analysis, we establish a baseline by solving the two-stage recourse problem ( RP ). To evaluate the benefits of this approach rather than simply using expected values ( EV ), we considered two common metrics: the value of the stochastic solution and the expected value of perfect information. For those cases in which it was not possible to find a feasible integer solution to RP, Lagrangian decomposition was used to get one of two lower bounds. Extensive testing was performed for a wide range of shifts and break models. The use of flexible shifts led to improvements of up to 9.01%, while using flexible breaks reduced objective function values by up to 3.61%. We also observed that the shift schedules obtained from the EV solution were insufficient to cover the random demand over all scenarios due to large variations in manpower requirements. The implication of this result is that the EV problem is a poor substitute for the two-stage model.