Optimal Search Policies for Searches with I/O Bound Tasks

This paper develops an optimal policy for conducting simple searches under the assumption that the tasks within the search tree are complex and may be I/O bound. The objective is to schedule the search of nodes to achieve the minimum expected time to completion of the search. A good strategy favors the search paths that have a high probability of success and have a low computation cost. Such a strategy also initiates the I/O bound tasks early enough that they make reasonable progress while executing the non-I/O bound tasks. An optimal policy balances all of these effects against each other to achieve the earliest expected completion time. © 1989 IEEE