Unnetworks, with Applications to Idle Time Scheduling

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.