A SEQUENTIAL INTEGER PROGRAMMING METHOD FOR DISCONTINUOUS LABOR TOUR SCHEDULING

General set-covering formulations (GSCFs) of labor tour scheduling pro blems have recently received substantial attention in the research lit erature. The most successful heuristic approaches to these problems ha ve used the linear programming (LP) solution to the GSCF as a starting point and subsequently applied heuristic augmentation and improvement procedures to obtain feasible integer solutions. Integer programming (TP) methods eliminate the need for augmentation and improvement proce dures, but have generally been considered intractable for large GSCFs. In this paper we present a sequential mixed-integer programming (SMIP ) heuristic for discontinuous (< 24 hours/day) tour-scheduling problem s which takes advantage of the structure of the GSCF. The new heuristi c substantially outperformed two prominent LP-based methods across 432 full-time workforce test problems, yielding optimal solutions for 429 of the problems. For a set of 36 test problems associated with a mixe d-workforce scheduling environment that allowed both full-time and par t-time employees with varying levels of cost and productivity, the SMI P heuristic yielded solution costs that were significantly better than previously published costs obtained with competitive methods.