|
|
|
|
RI | Publications | Variable and Value Ordering Heuristics for the Job Shop Scheduling Constraint Satisfaction Problem
|
|
Text only version of this site
Variable and Value Ordering Heuristics for the Job Shop Scheduling Constraint Satisfaction Problem
N. Sadeh-Koniecpol and M.S. Fox
tech. report CMU-RI-TR-95-39, Robotics Institute, Carnegie Mellon University, November, 1995.
Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference
| Download [Help] |
Adobe portable document format (pdf) [144 KB] Compressed postscript (ps.gz) [101 KB]
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
| 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.
| Notes |
Grant ID: DACA76-89-C-0014, DAAE07-90-C-R059
Number of pages: 50
| Text Reference |
N. Sadeh-Koniecpol and M.S. Fox, Variable and Value Ordering Heuristics for the Job Shop Scheduling Constraint Satisfaction Problem, tech. report CMU-RI-TR-95-39, Robotics Institute, Carnegie Mellon University, November, 1995.
| BibTeX Reference |
@techreport{Sadeh-Koniecpol_1995_391,
author = "Norman Sadeh-Koniecpol and Mark S. Fox",
title = "Variable and Value Ordering Heuristics for the Job Shop Scheduling Constraint Satisfaction Problem",
institution = "Robotics Institute, Carnegie Mellon University",
month = "November",
year = "1995",
number = "CMU-RI-TR-95-39",
address = "Pittsburgh, PA"
}