Accession Number : ADA322974
Title : Dynamic Backtracking.
Descriptive Note : Final rept.,
Corporate Author : OREGON UNIV EUGENE
Personal Author(s) : Ginsberg, Matthew L. ; Crawford, James M. ; Etherington, David W.
PDF Url : ADA322974
Report Date : FEB 1997
Pagination or Media Count : 148
Abstract : The goal of this project was to turn the intuitions behind dynamic backtracking into a series of formally verified algorithms, implement the algorithms, and test the results on realistic problems. These goals have been met and exceeded. Dynamic backtracking has been generalized to partial-order dynamic backtracking, and has been formalized, tested on academic benchmarks, and applied (by one of CTRL's industrial partners) to real industrial scheduling problems. Of equal importance, the search for novel search algorithms for scheduling problems has led beyond dynamic backtracking to include new techniques, such as limited discrepancy search and doubleback optimization, that are currently the best known techniques for benchmark scheduling problems of realistic size and character.
Descriptors : *ALGORITHMS, *SCHEDULING, TEST AND EVALUATION, OPTIMIZATION, INDUSTRIES, PROBLEM SOLVING, SEARCHING, STANDARDS.
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE