Constraint propagation techniques for the disjunctive scheduling problem

Constraint propagation is an elementary method for reducing the search spac e of combinatorial search and optimization problems which has become more a nd more important in the last decades. The basic idea of constraint propaga tion is to detect and remove inconsistent variable assignments that cannot participate in any feasible solution through the repeated analysis and eval uation of the variables, domains and constraints describing a specific prob lem instance. The contribution of this paper is twofold. The first contribution is a desc ription of efficient constraint propagation methods also known as consisten cy tests for the disjunctive scheduling problem (DSP) which is a generaliza tion of the classical job shop scheduling problem (JSP). Applying an elemen tary constraint based approach involving a limited number of search variabl es, we will derive consistency tests that ensure 3-b-consistency. We will f urther present and analyze both new and classical consistency tests which t o some extent are generalizations of the aforementioned consistency tests i nvolving a higher number of variables, but still can be implemented efficie ntly with a polynomial time complexity. Further, the concepts of energetic reasoning and shaving are analyzed and discussed. The other contribution is a classification of the consistency tests derived according to the domain reduction achieved. The particular strength of usi ng consistency tests is based on their repeated application, so that the kn owledge derived is propagated, i.e., reused for acquiring additional knowle dge. The deduction of this knowledge can be described as the computation of a fixed point. Since this fixed point depends upon the order of the applic ation of the tests, we first derive a necessary condition for its uniquenes s. We then develop a concept of dominance which enables the comparison of d ifferent consistency tests as well as a simple method for proving dominance . An extensive comparison of all consistency tests is given. Quite surprisi ngly, we will find out that some apparently stronger consistency tests are subsumed by apparently weaker ones. At the same time an open question regar ding the effectiveness of energetic reasoning is answered. (C) 2000 Elsevie r Science B.V. All rights reserved.