Cyclic Scheduling via Integer Programs with Circular Ones

John J. Bartholdi, James B. Orlin and H. Donald Ratliff
Additional contact information
John J. Bartholdi: University of Michigan, Ann Arbor, Michigan
James B. Orlin: Massachusetts Institute of Technology, Cambridge, Massachusetts
H. Donald Ratliff: Georgia Institute of Technology, Atlanta, Georgia

Operations Research, 1980, vol. 28, issue 5, 1074-1085

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.

Date: 1980
References: Add references at CitEc
Citations: View citations in EconPapers (24)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.28.5.1074 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:28:y:1980:i:5:p:1074-1085

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().