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.

Agnetis, A., Hermans, B., Leus, R., Rostami, S. (2022). Time-critical testing and search problems. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 296(2), 440-452 [10.1016/j.ejor.2021.03.038].

Time-critical testing and search problems

Agnetis A.;
2022

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.
Agnetis, A., Hermans, B., Leus, R., Rostami, S. (2022). Time-critical testing and search problems. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 296(2), 440-452 [10.1016/j.ejor.2021.03.038].
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0377221721002642-main.pdf

non disponibili

Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 654.19 kB
Formato Adobe PDF
654.19 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2101.05473.pdf

accesso aperto

Descrizione: Link al pdf editoriale: https://doi.org/10.1016/j.ejor.2021.03.038
Tipologia: Pre-print
Licenza: PUBBLICO - Pubblico con Copyright
Dimensione 328.52 kB
Formato Adobe PDF
328.52 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/1191825