GRAPH SEARCH METHODS FOR NON-ORDER-PRESERVING EVALUATION FUNCTIONS - APPLICATIONS TO JOB SEQUENCING PROBLEMS

Graph search with A is frequently faster than tree search. But A* gra ph search operates correctly only when the evaluation function is orde r-preserving. In the non-order-preserving case, no paths can be discar ded and the entire explicit graph must be stored in memory. Such situa tions arise in one-machine minimum penalty job sequencing problems whe n setup times are sequence dependent. GREC, the unlimited memory versi on of a memory-constrained search algorithm of the authors called MREC , has a clear advantage over A in that it is able to find optimal sol utions to such problems. At the same time, it is as efficient as A in solving graph search problems with order-preserving evaluation functi ons. Experimental results indicate that in the non-order-preserving ca se, GREC is faster than both best-first and depth-first tree search, a nd can solve problem instances of larger size than best-first tree sea rch.