Incremental Maximum Flows for Fast Envelope Computation

Abstract

Resource envelopes provide the tightest exact bounds on the resource consumption and production caused by all possible executions of a temporally flexible plan. We present a new class of algorithms that computes an envelope in O(Maxflow(n, m, U)) where n, m and U measure the size of the flexible plan. This is an O(n) improvement on the best complexity bound for an envelope algorithm known so far and makes envelopes more amenable to practical use in scheduling. The reduction in complexity depends on the fact that when the algorithm computes the constant segment i of the envelope it makes full reuse of the maximum flow used to obtain segment i-l.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 2004
Accession Number
ADP020845

Entities

People

  • Nicola Muscettola

Organizations

  • National Aeronautics and Space Administration

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Artificial Intelligence Computing
  • British Columbia
  • Computations
  • Construction
  • Consumers
  • Cost Reductions
  • Costs
  • Equations
  • Flow
  • Flow Network
  • Flow Separation
  • Graphs
  • Intelligent Systems
  • Iterations
  • Residuals

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Operations Research