Cyclic Scheduling via Integer Programs with Circular Ones

A fundamental problem of cyclic staffing is to size and schedule a minimum-cost workforce so that sufficient workers are on duty during each time period. This may be modeled as an integer linear program with a cyclically structured 0-1 constraint matrix. We identify a large class of such problems for which special structure permits the ILP to be solved parametrically as a bounded series of network flow problems. Moreover, an alternative solution technique is shown in which the continuous-valued LP is solved, and the result rounded in a special way to yield an optimum solution to the ILP.