Cyclic scheduling via integer programs with circular ones

Oper Res. 1980 Sep-Oct;28(5):1074-85. doi: 10.1287/opre.28.5.1074.

Abstract

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.

MeSH terms

  • Operations Research*
  • Personnel Management*
  • Personnel Staffing and Scheduling*