An ordered independence system and its applications to scheduling problems

This paper proposes an independence system on a finite ordered set, in which the maximum independent set (MIS) problem is investigated. Although this system is not necessary to be a matroid, some kind of ‘circuit-breaking algorithm’ for finding MIS can be established. Applying this framework to a class of scheduling problems, several existing algorithms are improved, while some new problems can be solved simultaneously.