Time-critical testing and search problems
From MaRDI portal
Publication:2242292
DOI10.1016/J.EJOR.2021.03.038zbMATH Open1490.90115arXiv2101.05473OpenAlexW3147724617MaRDI QIDQ2242292FDOQ2242292
Authors: Alessandro Agnetis, Ben Hermans, Roel Leus, Salim Rostami 
Publication date: 9 November 2021
Published in: European Journal of Operational Research (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/2101.05473
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
Deterministic scheduling theory in operations research (90B35) Search theory (90B40) Integer programming (90C10)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- An algorithm for the single machine sequencing problem with precedence constraints
- Complexity of Scheduling under Precedence Constraints
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- Search Theory
- Sequencing unreliable jobs on parallel machines
- Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
- Sequential testing of complex systems: a review
- Sequencing with Series-Parallel Precedence Constraints
- Optimal task sequencing with precedence constraints
- Optimal ordering of independent tests with precedence constraints
- Quiz show problems
- Multiple searchers searching for a randomly distributed immobile target on a unit network
- A Remark on Search and Sequencing Problems
- Sequential testing in batches
- The list scheduling algorithm for scheduling unreliable jobs on two parallel machines
- Sequential testing of \(n\)-out-of-\(n\) systems: precedence theorems and exact methods
- Approximation algorithms for sequential batch-testing of series systems
- Finding a hider by an unknown deadline
- On Submodular Search and Machine Scheduling
- Search and rescue in the face of uncertain threats
- The largest-Z-ratio-first algorithm is 0.8531-approximate for scheduling unreliable jobs on \(m\) parallel machines
- On efficient salvo policies
- Timely exposure of a secret project: which activities to monitor?
- On efficient algorithms for finding efficient salvo policies
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)
