Working set generation methods for labor tour scheduling

Working set methods in labor scheduling generally consist of a generation and implementation phase. The generation phase involves the selection of a subset of work schedules from the complete (master) set of all allowed work schedules. In the implementation phase, either heuristic or integer optimal solutions are obtained upon the basis of the schedules in the working set. We classify previous working set generation procedures as being either structural, demand-based, or refinement. Two new working set procedures within the first category and one new procedure within the second category are developed. Subsequently, we compare the efficacy of the new and previously published generation procedures within the context of a discontinuous tour scheduling environment where the sole objective is minimization of total labor hours scheduled. All comparative analysis was based upon the global integer optimal solutions to problems posed by the master set associated with 36 different labor requirements distributions. The second of the new structural methods resulted in the best performance for all working set sizes. In particular, it resulted in global integer optimal solutions, for all test problems, with working set sizes of 40 and 50. The new demand-based method resulted in the second best performance at a working set size of 50. We conclude with a discussion of the implications of the results for future research and practice.