An integrated approach to shift-starting time selection and tour-schedule construction

A common practice in personnel tour scheduling is to limit the number of permissible daily shift starting times. Accordingly, an important subproblem that arises in tour-scheduling problems is the selection of those starting times that are conducive to efficient satisfaction of labour requirements. A previously published heuristic for this problem is sequential in nature, whereby a subset of starting times is selected in the first stage and tours are constructed using the chosen starting times in the second stage. We propose an integrative procedure that overcomes many of the limitations inherent in the sequential approach. Our procedure, which uses tabu search for starting time selection and a cutting plane method for tour construction, was compared to integer programming and the previously published heuristic in two experiments using test conditions from the airport staffing literature. Although all methods performed well when the labour requirement patterns were consistent across days of the week, the new procedure yielded the best performance when such patterns were inconsistent.