Circular Ones and Cyclic Staffing.
Abstract
A large class of cyclic staffing problems, when formulated as (linear) integer programs, possess zero-one constraint matrices for which the ones in each row occur in consecutive components (the first and last components are considered consecutive). Included within this class is the problem of minimizing the linear cost of assigning workers to a multi-period cyclic schedule such that the demand in each period is satisfied, and each person works a shift of a common number of consecutive periods and is idle for the other periods (the first and last periods are considered consecutive). Any problem in this class may be transformed via a change of variables so that the resulting constraint matrix is, after deletion of a distinguished column, the transpose of a node-arc incidence matrix. The problem can then be solved in polynomial time parametrically in the distinguished variable as a sequence of network flow problems. Alternately, the optimal value of the distinguished variable can be found to within integer roundoff as its optimal value in the associated linear program with integer constraints ignored. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 20, 1977
- Accession Number
- ADA053202
Entities
People
- H. Donald Ratliff
- James B. Orlin
- John J. Bartholdi Iii
Organizations
- Stanford University