Weekly staff scheduling with workstation group restrictions

This paper addresses the weekly adjustment problem for staff scheduling when movement restrictions exist between workstation groups (WSGs). In practice, it is common for employees to be organized into physical or logical groups to match the layout of a facility or to facilitate managerial oversight. A complication in the problem arises when each employee is required to spend more time at his or her assigned home base during the week than at any other WSG. This conflicts with a common strategy of reassigning employees to different WSGs when idle time exists in their schedules. Ordinarily, the full problem is tackled with a two-phase approach, where optimal shifts and overtime allocations are first derived and then tasks are assigned. When movement restrictions exist in a facility, this approach is no longer practical or even possible for all but the smallest instances. Alternatively, a new model is proposed that integrates WSG restrictions with the shift scheduling and task assignment constraints. The model takes the form of a large-scale integer program and is solved with one of two decomposition heuristics. The first splits the movement restrictions network into manageable pieces; the second uses column generation to identify good individual schedules that are used to construct a set-covering-type master problem. A solution to the master problem provides a feasible solution to the original integer program. Extensive testing was done with data obtained from the U.S. Postal Service mail processing and distribution center in Dallas. The results show that good feasible solutions can be obtained in less than an hour.