Variable and Value Ordering Heuristics for Hard Constraint Satisfaction Problems: An Application to Job Shop Scheduling

Abstract

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 constraints and/or 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.