A Polynomial-Time Approximation Scheme for Sequential Batch Testing of Series Systems

Danny Segev () and Yaron Shaposhnik ()
Additional contact information
Danny Segev: Department of Statistics and Operations Research, School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv 69978, Israel
Yaron Shaposhnik: Simon Business School, University of Rochester, Rochester, New York 14627

Operations Research, 2022, vol. 70, issue 2, 1153-1165

Abstract: We study a recently introduced generalization of the classic sequential testing problem for series systems, consisting of multiple stochastic components. The conventional assumption in such settings is that the overall system state can be expressed as an AND function, defined with respect to the states of individual components. However, unlike the classic setting, rather than testing components separately, one after the other, we allow aggregating multiple tests to be conducted simultaneously, while incurring an additional set-up cost. This feature is present in numerous practical applications, where decision makers are incentivized to exploit economy of scale by testing subsets of components in batches. The main contribution of this paper is to devise a polynomial-time approximation scheme (PTAS) for the sequential batch-testing problem, thereby significantly improving on the constant-factor performance guarantee of 6.829 + ε due to Daldal et al. [Daldal R, Özlük O, Selçuk B, Shahmoradi Z, Ünlüyurt T (2017) Sequential testing in batches. Ann. Oper. Res . 253(1):97–116.]. Our approach is based on developing and leveraging a number of techniques in approximate dynamic programming, based on ideas related to efficient enumeration methods, state-space collapse, and charging schemes. These theoretical findings are complemented by extensive computational experiments, where we demonstrate the practical advantages of our methods.

Keywords: Optimization; sequential testing; approximation algorithms; PTAS; dynamic programming (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2019.1967 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:2:p:1153-1165

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().