Unnetworks, with Applications to Idle Time Scheduling

John J. Bartholdi, III and H. Donald Ratliff
Additional contact information
John J. Bartholdi, III: University of Michigan
H. Donald Ratliff: University of Florida

Management Science, 1978, vol. 24, issue 8, 850-858

Abstract: Integer linear programs with 0-1 constraint matrices arise frequently in scheduling and staffing models. For many such problems it is natural to model processor availability by columns of the constraint matrix, where 1's indicate processor availability for production and 0's indicate idle periods. Efficiently solvable problems have generally been identified in terms of special patterns of 1's within the matrix. Exploiting the fact that idle time is the complement of production time, we identify classes of problems that are efficiently solvable because of special patterns of 0's. In particular, several interesting idle-time scheduling problems are shown to be solvable as finite and bounded series of network flow or matching problems.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.24.8.850 (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:ormnsc:v:24:y:1978:i:8:p:850-858

Access Statistics for this article

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