Gaining Efficiency and Flexibility in the Simple Temporal Problem

Deals with the problem of managing quantitative temporal networks without disjunctive constraints. This problem is known as the "simple temporal problem". Dynamic management algorithms are considered to be coupled with incremental constraint posting approaches for planning and scheduling. A basic algorithm for incremental propagation of a new time constraint is presented which is a modification of the Bellman-Ford algorithm for the single-source shortest-path problem. For this algorithm, a sufficient condition for inconsistency is given, based on cycle detection in the shortest-paths graph. Moreover, the problem of constraint retraction from a consistent situation is considered, and properties for repropagating the network locally are exploited. Some experiments are also presented that show the usefulness of these properties.

Authors

• Amedeo Cesta
• Angelo Oddi

Keywords

• Heuristic algorithms
• Intelligent networks
• Councils
• Scheduling algorithm
• Dynamic scheduling
• Time factors
• Shortest path problem
• Remuneration
• Computer network management
• Information management
• Nitrogen Metabolism
• Shortest Path
• Planning And Scheduling
• Lower Bound
• Upper Bound
• Number Of Time Points
• Set Of Distances
• Temporal Constraints
• Negative Cycle
• Part Of The Graph
• Node Distance