Unnetworks, with Applications to Idle Time Scheduling

Publisher Website
Google Scholar
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.

This publication has 0 references indexed in Scilit: