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