This payer presents an effective solution strategy for an important ca
tegory of personnel scheduling problems. Specifically, we address the
restricted starting-time tour-scheduling problem (RSTP), which involve
s the determination of the hours of the day (shifts) and days of the w
eek (days on) that employees are assigned to work. RSTP is characteriz
ed by restrictions on the number of daily time periods in which employ
ees may begin their shifts. Moreover, the RSTP we consider contains co
nstraints that require separation of starting times. Such restrictions
are widely encountered in practice and are based on a number of facto
rs including managerial concerns for control of employee movements, un
ion contractual obligations, and employee preferences for common shift
starting times. A two-stage heuristic solution strategy is proposed f
or RSTP. We developed eight heuristic procedures based on this strateg
y and applied them to four sets of labor requirements, for each of 27
United Airlines (UA) airport ground stations. One of the best of these
procedures yielded solution costs that averaged only 1.36 full-time-e
quivalent employees above very conservative LP-based lower bounds. Mor
eover, the solution costs obtained using this procedure were, on avera
ge, 28 percent closer to the lower bounds than solution costs obtained
using UA's current scheduling system. We conclude that the two-stage
heuristic solution strategy is a valuable platform from which to devel
op procedures for generating near-optimal solutions to this difficult
class of personnel scheduling problems.