Premium
Infinite‐horizon Scheduling Algorithms for Optimal Search for Hidden Objects
Author(s) -
Levner Eugene
Publication year - 1994
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/1475-3995.d01-24
Subject(s) - mathematical optimization , sequence (biology) , algorithm , scheduling (production processes) , decision maker , set (abstract data type) , computer science , mathematics , time horizon , search algorithm , operations research , genetics , biology , programming language
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 we are concerned 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.