An O(n2log2n) 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 consistency test. And an O(n²log²n) algorithm dealing with the test is proposed, where n denotes the number of jobs. In literature, an O(n⁴) 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.