AN O(n 2 log 2 n) ALGORITHM FOR INPUT-OR-OUTPUT TEST IN DISJUNCTIVE SCHEDULING

This paper is concerned with the input-or-output test that is a kind of interval capacity consis- tency tests. And an O(n 2 log 2 n) algorithm dealing with the test is proposed, where n denotes the number of jobs. In literature, an O(n 4 ) algorithm has been known. The tests can be effectively used to reduce the search space of time- and resource-constrained scheduling problems. Computational results show that our new algorithm is about 3 times faster for instances of 30 jobs than the existing algorithm.