Model Justified Search Algorithms for Scheduling Under Uncertainty

Abstract

We have identified clear trade-offs in algorithm design for the scheduling under uncertainty problem that relate to the sources of the uncertainty. We also identified plateaus as a significant barrier to superb performance of local search on scheduling and have studied several canonical discrete optimization problems to discover and model the nature of plateaus. From this, we have developed lower and upper bound predictive models of plateau size in a significant optimization problem: MAXSAT. We also develop new theoretical results on the nature of plateaus in Elementary Landscapes.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 25, 2008
Accession Number
ADA492118

Entities

People

  • Adele Howe
  • L. D. Whitley

Organizations

  • Colorado State University

Tags

Communities of Interest

  • Human Systems
  • Space

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Artificial Intelligence
  • Computations
  • Computer Science
  • Department Of Defense
  • Equations
  • Evolutionary Algorithms
  • Genetic Algorithms
  • Heuristic Methods
  • Mathematics
  • Optimization
  • Plateaus
  • Radar
  • Scheduling (Production)
  • Theoretical Computer Science
  • Uncertainty

Readers

  • Seismology
  • Statistical inference.
  • Systems Analysis and Design