Problems in investigation theory

Abstract

Investigation theory treats discrete combinatorial optimization problems in which there are several objects passing through a region containing one or more investigators who are to investigate, according to some criteria, objects prior to their escape across a portion of the boundary of the region. In general investigation times are sequence-dependent functions of the time investigation is initiated. This research treats problems with one investigator under the criteria of minimization of the number of objects to escape uninvestigated. Those problems for which optimal solutions can be efficiently obtained are identified and algorithms developed. For the general problem, heuristic solution methods are suggested and evaluated through comparison of results obtained with optimal solutions. An analysis is presented for problems with uncertain investigation times and also for problems in which objects are not immediately available for investigation. Generalizations to more than one investigator and an alternate objective are discussed. The relationship between investigation and job shop scheduling problems is illustrated throughout.