Non-Order-Preserving Evaluation Functions: Recursive Graph-Search Methods for Job Sequencing Problems

Abstract

A* sometimes runs significantly faster than a tree-search branch-and-bound procedure if the search graph is represented as a graph and not as a tree. But graph search with A* is suitable only when the evaluation function is orderpreserving, i.e., in situations where a path in the explicit graph from the root to a node can be discarded when a better path to the node is found. 1bere exist interesting classes of problems, however, such as one-machine minimum-penalty job sequencing problems with sequencedependent setup times, for which the evaluation function is non-order-preserving. The search method cannot then discard any paths, and must store the entire explicit graph. GREC, a variant of an earlier recursive memory-constrained algorithm of the authors called MREC, has the desired properties and can be used in place of A•. Experimental results indicate that when the penalty is linear or quadratic, GREC is faster than tree search schemes and is able to solve problem instances of larger size.