Variable and Value Ordering Heuristics for Hard Constraint Satisfaction Problems: An Application to Job Shop Scheduling
CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST
Pagination or Media Count:
Hard Constraint Satisfaction Problems HCSPs are Constraint Satisfaction Problems CSPs with very large search spaces and very few solutions. Real-life problems such as design or factory scheduling are examples of HCSPs. These problems typically involve several hundred or even several thousand variables, each with up to several hundred possible values, only a very tiny fraction of which ultimately allows for a satisfying solution. This paper addresses the issue of how to generate advice to decide which variable to instantiate next i.e. variable ordering heuristics, and which value to assign to that variable i.e. value ordering heuristics in order to reduce search for a solution. Our investigation is conducted in the domain of job shop scheduling. It is shown that, in this domain, generic CSP heuristics are usually not sufficient to guide the search for a feasible solution. This is because these heuristics fail to properly account for the tightness of constrain andor the connectivity of the constraint graph. Instead, a probabilistic model of the search space is used to define new heuristics, which better account for these problem characteristics. Experimental results indicate that these new heuristics yield important improvements in both search efficiency and search time.
- Administration and Management
- Operations Research