Generation of Circuits and Minimal Forbidden Sets

inclusion-minimal subsets of jobs that must not be scheduled simultaneously.
These so-called minimal forbidden sets are given only implicitly by a linear
inequality system, and can be interpreted in a more general context as the
circuits of an independence system. We discuss several complexity results
related to generation and enumeration of the circuits of an independence
system, with particular focus on the type of systems that arise in
scheduling. We also briefly discuss an implementation of a simple
backtracking algorithm that generates all minimal forbidden sets for
resource constrained scheduling problems.