An Effective Near-Optimal State-Space Search Method: An Application to a Scheduling Problem

This paper presents aneffective near-optimal search method forstate-space problems. The method, LTAast(Learning Threshold Aast), accepts athreshold parameter, p, as an input and finds asolution within that range of the optimum. Thelarger the parameter, the faster the methodfinds a solution. LTAast is based on acombination of recursion and dynamic memoryand, like Aast, keeps information about allstates in memory. In contrast to Aasthowever, which represents each node as acomplete state, LTAast represents each nodeusing an operator. This representation of thenodes makes LTAast dramatically efficientwith respect to memory usage. Another advantageof LTAast is that it eliminates any need forcomputational effort to maintain a priorityqueue, and this elimination significantlyincreases speed. To test the effectiveness andefficiency of the method we have applied it toNP-hard problems in scheduling. The testresults indicate that the method is effectivein trading speed with the quality of solutionsand that it is efficient in producing solutionsfor p = 0.