Infinite-horizon scheduling algorithms for optimal search for hidden objects

Infinite-horizon scheduling algorithms for optimal search for hidden objects

0.00 Avg rating0 Votes
Article ID: iaor1995563
Country: United Kingdom
Volume: 1
Issue: 2
Start Page Number: 241
End Page Number: 250
Publication Date: Apr 1994
Journal: International Transactions in Operational Research
Authors:
Keywords: programming: dynamic
Abstract:

This paper considers discrete search problems in which a decision-maker has to find objects lost or hidden in a given set of locations so as to minimize the expected losses incurred. Given a chance to look for a hidden object in the same location infinitely many times, this type of problem, in contrast to standard scheduling problems, has an infinite sequence as its solution. Thus the concern is to find an algorithm that yields an optimal solution, rather than the optimal sequence itself. Using combinatorial techniques, fast optimal algorithms for solving the problems are obtained, and optimality conditions are presented for search criteria, under which the local-search algorithms yield the global optimum.

Reviews

Required fields are marked *. Your email address will not be published.