M. Middendorf, Institut für Angewandte Informatik und Formale Beschreibungsverfahren, University of Karlsruhe, Germany
Email: middendorf@aifb.uni-karlsruhe.de
We describe an Ant System AS-PM for solving the Plan Merging problem (PM). This problem is to find a cheap execution sequence for the operations of a plan (i.e. a directed acyclic graph where each vertex represents an operation and the arcs define a precedence relation between the vertices) by exploiting the property that it is cheap to execute operations of the same type together. PM has applications in production planning and mechanical engineering.
In AS-PM the ants are guided by the values of parameters (trail information) that are assigned to the operations of the plan when applying a fast constructive heuristic to build up an execution sequence. We compare AS-PM with a genetic algorithm and heuristics for PM on several test instances.
Our tests show that it is advantageous when the ants use a lookahead function when they make their decisions. Thus the decisions about which operations to be scheduled next depend on the quality of the resulting state which is measured as the amount of trail information on the operations that can possibly be scheduled afterwards. For an important subproblem of PM where the connected components of the plan are paths with similar sequences of operations the tests show good results when working with two different poulations of ants that exchange trace information - ants of the ``forward population'' move along the direction of the arcs through the plan whereas the ``backward ants'' take the opposite direction.