Workflow modeling using an acyclic directed graph data structure

1. A process for modeling at least a portion of a workflow for logistics planning of an enterprise, comprising:

accessing a computer data structure that represents an acyclic directed graph, the acyclic directed graph represents the workflow for logistics planning of the enterprise and comprises a plurality of nodes and one or more edges, each of the edges linking two adjacent nodes within the acyclic directed graph;

requesting the value of a first function at a selected node, the value of the first function at the selected node depending at least in part on values of the first function at one or more adjacent nodes lying in a first direction from the selected node within the acyclic directed graph, a cached value of at least a second function at the selected node depending only on the value of the first function at the selected node and one or more other values associated with the selected node;

determining whether a cached value of the first function at the selected node is assured to be valid;

if the cached value of the first function at the selected node is assured to be valid, then:

return the cached value of the first function at the selected node without recomputing the value of the first function at the selected node;

if the cached value of the first function at the selected node is not assured to be valid, then:

requesting the value of a second function at the adjacent node corresponding to an edge lying in a first direction from the selected node;

adding the returned value of the second function at the adjacent node to a value associated with movement in a second direction opposite the first direction from the adjacent node to the selected node along the edge, this addition generating a total value for the edge;

if the total value for the edge is greater than the cached value of the first function at the selected node, then exit the first iteration and perform the second iteration; and

if the total value for the edge is not greater than the cached value of the first function at the selected node, then either process the next edge within the first iteration or, if there are no more edges to be processed within the first iteration:

providing an indication associated with the selected node that the cached value of the first function at the selected node is assured to be valid; and

returning the cached value of the first function at the selected node.

2. The process of claim 1 , wherein the workflow comprises a planned flow of resources through a sequence of processing steps to transform less finished resources into more finished resources, the flow of resources being represented by the edges within the acyclic directed graph and giving a time-based directionality to the acyclic directed graph.

3. The process of claim 1 , wherein:

the selected node is associated with a Boolean variable indicating whether the cached value of the first function at the selected node is assured to be valid; and

determining whether the cached value of the first function at the selected node is assured to be valid comprises determining the value of the Boolean variable at the selected node.

4. The process of claim 1 , wherein requesting the value of the first function at the selected node comprises calling a corresponding node-local method of the selected node, the node-local method determining whether the cached value of the function at the selected node is assured to be valid and returning either the recomputed value or the cached value, as appropriate, of the function at the selected node.

5. The process of claim 1 , further comprising imposing an indication of possible invalidity on the cached values of the first function at all nodes in a second direction from the selected node in response to determining that the cached value of the first function at the selected node is not assured to be valid, the second direction being the opposite direction from the first direction.

6. The process of claim 1 , wherein the value of the first function at the selected node is selected from the group consisting of:

a value of an earliest possible starting time (EPST) for a portion of the workflow associated with the selected node;

a value of an EPET for a portion of the workflow associated with the selected node;

a value of a latest possible starting time (LPST) for a portion of the workflow associated with the selected node; and

a value of an LPET for a portion of the workflow associated with the selected node.

7. The process of claim 1 , wherein the value of the first function at the selected node is selected from the group consisting of:

a maximum quantity of an output of a portion of the workflow associated with the selected node for which production can be started, given an available supply of at least one input at a selected time; and

a maximum quantity of an output of a portion of the workflow associated with the selected node for which production can be completed, given an available supply of at least one input at a selected time.

8. The process of claim 1 , wherein the value of the first function at the selected node is selected from the group consisting of:

a minimum quantity of an input required to start production within at least a portion of the workflow, given a desired minimum quantity of an output that is to be produced by that portion of the workflow by a specified time;

a minimum quantity of an input required to complete production within at least a portion of the workflow, given a desired minimum quantity of an output that is to be produced by that portion of the workflow by a specified time.

9. The process of claim 1 , wherein the process is implemented using at least one component selected from the group consisting of a planner, a scheduler, and an optimizer.

10. A computer-implemented system for modeling at least a portion of a workflow for logistics planning of an enterprise, the system operating on one more computer processors collectively operable to:

access a computer data structure that represents an acyclic directed graph, the acyclic directed graph represents the workflow for logistics planning of the enterprise and comprises a plurality of nodes and one or more edges, each of the edges linking two adjacent nodes within the acyclic directed graph;

request the value of a first function at a selected node, the value of the first function at the selected node depending at least in part on values of the first function at one or more adjacent nodes lying in a first direction from the selected node within the acyclic directed graph, a cached value of at least a second function at the selected node depending only on the value of the first function at the selected node and one or more other values associated with the selected node;

determine whether a cached value of the first function at the selected node is assured to be valid;

if the cached value of the first function at the selected node is assured to be valid, then:

return the cached value of the first function at the selected node without recomputing the value of the first function at the selected node;

if the cached value of the first function at the selected node is not assured to be valid, then:

requesting the value of a second function at the adjacent node corresponding to an edge lying in a first direction from the selected node;

adding the returned value of the second function at the adjacent node to a value associated with movement in a second direction opposite the first direction from the adjacent node to the selected node along the edge, this addition generating a total value for the edge;

if the total value for the edge is greater than the cached value of the first function at the selected node, then exit the first iteration and perform the second iteration; and

if the total value for the edge is not greater than the cached value of the first function at the selected node, then either process the next edge within the first iteration or, if there are no more edges to be processed within the first iteration:

provide an indication associated with the selected node that the cached value of the first function at the selected node is assured to be valid; and

return the cached value of the first function at the selected node.

11. The system of claim 10 , wherein the workflow comprises a planned flow of resources through a sequence of processing steps to transform less finished resources into more finished resources, the flow of resources being represented by the edges within the acyclic directed graph and giving a time-based directionality to the acyclic directed graph.

12. The system of claim 10 , wherein:

the selected node is associated with a Boolean variable indicating whether the cached value of the first function at the selected node is assured to be valid; and

determining whether the cached value of the first function at the selected node is assured to be valid comprises determining the value of the Boolean variable at the selected node.

13. The system of claim 10 , wherein requesting the value of the first function at the selected node comprises calling a corresponding node-local method of the selected node, the node-local method determining whether the cached value of the function at the selected node is assured to be valid and returning either the recomputed value or the cached value, as appropriate, of the function at the selected node.

14. The system of claim 10 , wherein the one or more computer processors are further operable to impose an indication of possible invalidity on the cached values of the first function at all nodes in a second direction from the selected node in response to determining that the cached value of the first function at the selected node is not assured to be valid, the second direction being the opposite direction from the first direction.

15. The system of claim 10 , wherein the value of the first function at the selected node is selected from the group consisting of:

a value of an earliest possible starting time (EPST) for a portion of the workflow associated with the selected node;

a value of an EPET for a portion of the workflow associated with the selected node, node;

a value of a latest possible starting time (LPST) for a portion of the workflow associated with the selected node; and

a value of an LPET for a portion of the workflow associated with the selected node, node.

16. The system of claim 10 , wherein the value of the first function at the selected node is selected from the group consisting of:

a maximum quantity of an output of a portion of the workflow associated with the selected node for which production can be started, given an available supply of at least one input at a selected time; and

a maximum quantity of an output of a portion of the workflow associated with the selected node for which production can be completed, given an available supply of at least one input at a selected time.

17. The system of claim 10 , wherein the value of the first function at the selected node is selected from the group consisting of:

a minimum quantity of an input required to start production within at least a portion of the workflow, given a desired minimum quantity of an output that is to be produced by that portion of the workflow by a specified time; and

a minimum quantity of an input required to complete production within at least a portion of the workflow, given a desired minimum quantity of an output that is to be produced by that portion of the workflow by a specified time.

18. The system of claim 10 , wherein the process is implemented using at least one component selected from the group consisting of a planner, a scheduler, and an optimizer.

19. A method of modeling at least a portion of a workflow for logistics planning of an enterprise, comprising:

accessing a computer data structure that represents an acyclic directed graph, the acyclic directed graph represents the workflow for logistics planning of the enterprise and comprises a plurality of nodes and one or more edges, each of the edges linking two adjacent nodes within the acyclic directed graph, the acyclic directed graph having a time-based directionality;

requesting the value of a first function at a selected node, the value of the first function at the selected node depending at least in part on values of the first function at one or more adjacent nodes lying in a first direction from the selected node;

determining whether a cached value of the first function at the selected node is assured to be valid;

if the cached value of the first function at the selected node is assured to be valid, then:

return the cached value of the first function at the selected node without recomputing the value of the first function at the selected node; and

if the cached value of the first function at the selected node is not assured to be valid, then:

perform a first iteration through the edges lying in the first direction from the selected node, the first iteration comprising:

determining whether an edge might make invalid the value of the first function at the selected node;

if the edge will not make invalid the value of the first function at the selected node, then either processing the next edge within the first iteration or, if there are no more edges to be processed within the first iteration, providing an indication associated with the selected node that the cached value of the first function at the selected node is assured to be valid and returning the cached value of the first function at the selected node;

if the edge might make invalid the value of the first function at the selected node, then providing an indication associated with the edge that the edge does not make invalid the value of the first function at the selected node;

if the edge corresponds to an adjacent node lying in the first direction from the selected node that is at least partially responsible for the value of the first function at the selected node, then exit the first iteration and perform a second iteration through the edges lying in the first direction from the selected node; and

if the edge corresponds to an adjacent node lying in the first direction from the selected node that is not at least partially responsible for the value of the first function at the selected node, then:

requesting the value of a second function at the adjacent node corresponding to the edge;

adding the returned value of the second function at the adjacent node to a value associated with movement in a second direction opposite the first direction from the adjacent node to the selected node along the edge, this addition generating a total value for the edge;

if the total value for the edge is greater than the cached value of the first function at the selected node, then exit the first iteration and perform the second iteration; and

if the total value for the edge is not greater than the cached value of the first function at the selected node, then either process the next edge within the first iteration or, if there are no more edges to be processed within the first iteration, providing an indication associated with the selected node that the cached value of the first function at the selected node is assured to be valid and returning the cached value of the first function at the selected node;

the second iteration through the edges lying in the first direction from the selected node comprising:

requesting the value of the second function at the adjacent nodes corresponding to the edges;

adding the returned values of the second function at the adjacent nodes to the values associated with movement in the second direction from the adjacent nodes to the selected node along the edges to generate total values for the edges;

determining a maximum total value over all the adjacent nodes;

perform a third iteration through the edges lying in the first direction from the selected node comprising:

providing an indication associated with all edges that produced the maximum total value that these edges are at least partially responsible for the value of the first function at the selected node;

providing an indication associated with all edges that did not produce the maximum total value that these edges are not at least partially responsible for the value of the first function at the selected node; and

providing an indication associated with each edge that the edge will not make invalid the value of the first function at the selected node;

if the maximum total value is equal to the cached value of the first function at the selected node, then:

providing an indication that the cached value of the first function is valid; and

returning the cached value of the first function at the selected node without recomputing the value of the first function at the selected node; and

if the maximum total value is different from the cached value of the first function at the selected node, then:

providing an indication that the cached value of the second function is not valid;

updating the cached value of the first function at the selected node to the maximum total value;

providing an indication associated with the selected node that the cached value of the first function at the selected node is assured to be valid; and

returning the cached value of the first function at the selected node.

20. The method of claim 19 , wherein:

the value of the first function at a node comprises an earliest possible start time for a manufacturing operation represented by the node; and

the value of the second function at a node comprises an earliest possible end time for a manufacturing operation represented by the node.