Dynamic Backtracking.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1997
Accession Number
ADA322974

Entities

People

  • David W. Etherington
  • James M. Crawford
  • Matthew L. Ginsberg

Organizations

  • University of Oregon

Tags

Communities of Interest

  • Autonomy
  • C4I
  • Ground and Sea Platforms
  • Human Systems
  • Weapons Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Aircrafts
  • Algorithms
  • Artificial Intelligence
  • Artificial Intelligence Computing
  • Computational Science
  • Computer Programming
  • Computer Science
  • Computers
  • Debugging
  • Engineering
  • Heuristic Methods
  • Lisp Programming Language
  • Manufacturing
  • Military Research
  • Scheduling (Production)
  • Trees (Data Structures)

Fields of Study

  • Computer science

Readers

  • Aerospace Test and Evaluation
  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Systems Analysis and Design