Sequential testing in batches with resource constraints

doi:10.1016/j.eswa.2024.124858

Sequential testing in batches with resource constraints

2024-12-01

0

PRE

AI

DOI：10.1016/j.eswa.2024.124858

Original

Original request for help

Save

Abstract

En 中文

This paper studies a problem of determining the state of a system through costly tests of its components, where components can be tested simultaneously in batches to exploit economies of scale. This problem is a generalization of the classical sequential testing problem and it has applications in various settings, including machine maintenance, disease diagnosis, and new product development. We prove that the problem is strongly NP-hard, model it as a mixed-integer programming formulation, and we also propose a dynamic program for it. Additionally, we design a tabu search and a hybrid solution method that combines a tabu search metaheuristic and a proximity search matheuristic. Based on extensive computational experiments, we find that the dynamic program can solve instances with up to 25 components within a 15-minute time limit and 16 GB of RAM. With respect to larger instances, the proposed metaheuristic and hybrid method are better than a greedy heuristic.

Keywords:

Sequential testing

Serial system

Batch processing

Tabu search

Proximity search

Sequential testing in batches with resource constraints

Abstract

Journal

Organization