Time-critical testing and search problems

doi:10.1016/j.ejor.2021.03.038

Time-critical testing and search problems

2022-01-01

2

OA

AI

DOI：10.1016/j.ejor.2021.03.038

Original

Save

View PDF

Abstract

En 中文

This paper introduces a problem in which the state of a system needs to be determined through costly tests of its components by a limited number of testing units and before a given deadline. We also consider a closely related search problem in which there are multiple searchers to find a target before a given deadline. These natural generalizations of the classical sequential testing problem and search problem are applicable in a wide range of time-critical operations such as machine maintenance, diagnosing a patient, and new product development. We show that both problems are NP-hard, develop a pseudo-polynomial dynamic program for the special case of two time slots, and describe a partial-order-based as well as an assignment-based mixed integer program for the general case. Based on extensive computational experiments, we find that the assignment-based formulation performs better than the partial-order-based formulation for the testing variant, but that this is the other way round for the search variant. Finally, we propose a pairwise-interchange-based local search procedure and show that, empirically, it performs very well in finding near-optimal solutions. (c) 2021 Elsevier B.V. All rights reserved.

Keywords:

Scheduling

System testing

Search theory

Complexity theory

Integer programming

Time-critical testing and search problems

Abstract

AI Summary

Journal

Organization