Accession Number : ADA255269


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


Descriptive Note : Technical rept.


Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST


Personal Author(s) : Sadeh, Norman M ; Fox, Mark S


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a255269.pdf


Report Date : Nov 1991


Pagination or Media Count : 56


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 constrain 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.


Descriptors :   *HEURISTIC METHODS , *JOB SHOP SCHEDULING , SCHEDULING , VALUE , INDUSTRIAL PLANTS , PAPER


Subject Categories : Administration and Management
      Operations Research


Distribution Statement : APPROVED FOR PUBLIC RELEASE