SEARCHING GRAPHS WITH A-ASTERISK - APPLICATIONS TO JOB SEQUENCING

The best-first search algorithm A allows search graphs that are trees , directed acyclic graphs or directed graphs with cycles. In real life applications of A the search graph is generally implemented as a tre e. It is shown here that for certain well known one-machine job sequen cing problems that arise in Sob shops, graph search is much faster tha n best-first tree search when problem instances are of small and mediu m size. Moreover, graph search uses less memory and so is able to solv e larger problems. Depth-first search needs little memory, and is ther efore capable in principle of solving problems of arbitrary size, but is slower than graph search by orders of magnitude for the examples th at were studied.