Time-critical testing and search problems
From MaRDI portal
Abstract: 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.
Recommendations
- Approximation algorithms for sequential batch-testing of series systems
- Sequential testing of \(n\)-out-of-\(n\) systems: precedence theorems and exact methods
- Sequential testing of complex systems: a review
- Using multiple searchers in constrained-path, moving-target search problems
- A polynomial-time approximation scheme for sequential batch testing of series systems
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- A Remark on Search and Sequencing Problems
- An algorithm for the single machine sequencing problem with precedence constraints
- Approximation algorithms for sequential batch-testing of series systems
- Complexity of Scheduling under Precedence Constraints
- Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
- Finding a hider by an unknown deadline
- Multiple searchers searching for a randomly distributed immobile target on a unit network
- On Submodular Search and Machine Scheduling
- On efficient algorithms for finding efficient salvo policies
- On efficient salvo policies
- Optimal ordering of independent tests with precedence constraints
- Optimal task sequencing with precedence constraints
- Quiz show problems
- Search Theory
- Search and rescue in the face of uncertain threats
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- Sequencing unreliable jobs on parallel machines
- Sequencing with Series-Parallel Precedence Constraints
- Sequential testing in batches
- Sequential testing of \(n\)-out-of-\(n\) systems: precedence theorems and exact methods
- Sequential testing of complex systems: a review
- The largest-Z-ratio-first algorithm is 0.8531-approximate for scheduling unreliable jobs on \(m\) parallel machines
- The list scheduling algorithm for scheduling unreliable jobs on two parallel machines
- Timely exposure of a secret project: which activities to monitor?
Cited in
(3)
This page was built for publication: Time-critical testing and search problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2242292)
