| Abstract | A large number of manufacturing operation planning problems can be formulatedas state-space search problems. In case of sheet-metal bending operation planning,
processing a search node involves extensive geometric reasoning. Such computation-
intensive node-processing limits the number of search nodes that can be expanded in
a reasonable amount of time, making it difficult to solve real-life operation planning
problems.
In this paper, we describe a scheme to speed up operation planning by virtual gen-
eration of state-space nodes. In this scheme, we eliminate unnecessary computation
at the time of node generation by extracting the required information from already
generated nodes. Although generation of two different search nodes rarely involves
identical computation steps, there is considerable overlap in node generation steps.
We have divided the node generation step into a number of computation subproblems.
When we need to generate a new node, we first try to see if any of the node gener-
ation subproblems have been solved for any of the already generated nodes. If any
subproblem has already been solved for some other node, then we use the solution of
that subproblem to save computation time. In such cases, we do not perform node
generation computation steps, and therefore we call such node generation virtual.
The scheme presented in this paper increases the node generation capability and
allows us to consider many more search nodes. The ability to consider more search
nodes helps us in solving more complex problems and finding better operation plans.
|
