Accession Number : ADA311303

Title :   Variable and Value Ordering Heuristics for the Job Shop Scheduling Constraint Satisfaction Problem.

Descriptive Note : Technical rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST

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

PDF Url : ADA311303

Report Date : NOV 1995

Pagination or Media Count : 58

Abstract : Practical Constraint Satisfaction Problems (CSPs) such as design of integrated circuits or scheduling generally entail large search space with hundreds or even thousands of variables, each with hundreds or thousands of possible values. Often, only a very tiny fraction of all these possible assignments participates in a satisfactory solution. This article discusses techniques that aim at reducing the effective size of the search space to be explored in order to find a satisfactory solution by judiciously selecting the order in which variables are instantiated and the sequence in which possible values are tried for each variable. In the CSP literature, these techniques are commonly referred to as variable and value ordering heuristics. Our investigation is conducted in the job shop scheduling domain. We show that, in contrast with problems studied earlier in the CSP literature, generic variable and value heuristics do not perform well in this domain. This is attributed to the difficulty of these heuristics to properly account for the tightness of constraints and/or the connectivity of the constraint graphs induced by job shop scheduling CSPs. A new probabilistic framework is introduced that better captures these key aspects of the job shop scheduling search space. Empirical results show that variable and value ordering heuristics derived within this probabilistic framework often yield significant improvements in search efficiency and significant reductions in the search time required to obtain a satisfactory solution.

Descriptors :   *HEURISTIC METHODS, *JOB SHOP SCHEDULING, MATHEMATICAL MODELS, ALGORITHMS, OPTIMIZATION, COMPUTER AIDED DESIGN, COMPUTER COMMUNICATIONS, PROBABILITY, EFFICIENCY, INPUT OUTPUT PROCESSING, SEARCHING, SYSTEMS ANALYSIS.

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE