Applications of bulk queues to group testing models with incomplete identification. (English) Zbl 1127.90017

Bar-Lev, Shaul K.; Parlar, Mahmut; Perry, David; Stadje, Wolfgang; van der Duyn Schouten, Frank A.

Eur. J. Oper. Res. 183, No. 1, 226-237 (2007).

Summary: A population of items is said to be “group-testable”, (i) if the items can be classified as “good” and “bad”, and (ii) if it is possible to carry out a simultaneous test on a batch of items with two possible outcomes: “Success” (indicating that all items in the batch are good) or “failure” (indicating a contaminated batch). In this paper, we assume that the items to be tested arrive at the group-testing centre according to a Poisson process

•  Encyclopedia of Mathematics
•  Wikipedia
•  Wolfram MathWorld

and are served (i.e., group-tested) in batches by one server. The service time distribution is general but it depends on the batch size being tested. These assumptions give rise to the bulk queueing model \(M/G^{(m,M)}/1\), where \(m\) and \(M(>m)\) are the decision variables where each batch size can be between \(m\) and \(M\). We develop the generating function for the steady-state probabilities of the embedded Markov chain. We then consider a more realistic finite state version of the problem where the testing centre has a finite capacity and present an expected profit objective function. We compute the optimal values of the decision variables \((m, M)\) that maximize the expected profit. For a special case of the problem, we determine the optimal decision explicitly in terms of the Lambert function.

© Elsevier B.V.

MSC:

90B22	Queues and service in operations research
60K25	Queueing theory (aspects of probability theory)

Keywords:

applied probability; queueing; quality control

References:

[1]	Abolnikov, L.; Dukhovny, A., Markov chains with transition delta-matrix; ergodicity conditions, invariant probability measures and applications, Journal of Applied Mathematics and Stochastic Analysis, 5, 1, 83-98, 1992
[2]	Abolnikov, L.; Dukhovny, A., Queueing processes and optimization problems in quality control systems with a group-individual testing procedure, Engineering Simulation, 16, 165-178, 1999
[3]	Abolnikov, L.; Dukhovny, A., Optimization in HIV screening problems, Journal of Applied Mathematics and Stochastic Analysis, 16, 4, 361-374, 2003 · Zbl 1044.92027
[4]	Bar-Lev, S. K.; Stadje, W.; Van der Duyn Schouten, F. A., Group testing procedures with incomplete identification and unreliable testing results, Applied Stochastic Models in Business and Industry, 22, 281-296, 2006 · Zbl 1113.62145
[5]	Bar-Lev, S. K.; Stadje, W.; Van der Duyn Schouten, F., Hypergeometric group testing with incomplete information, Probability in the Engineering and Informational Sciences, 17, 335-350, 2003 · Zbl 1336.62042
[6]	Bar-Lev, S. K.; Stadje, W.; Van der Duyn Schouten, F., Optimal group testing with processing times and incomplete identificationm, Methodology and Computing in Applied Probability, 6, 55-72, 2004 · Zbl 1041.62099
[7]	Bar-Lev, S. K.; Stadje, W.; Van der Duyn Schouten, F., Multinomial group testing models with incomplete identification, Journal of Statistical Planning and Inference, 135, 384-401, 2005 · Zbl 1074.62051
[8]	Bocharov, P. P.; D’Apice, C.; Pechinkin, A. V.; Salerno, S., Queueing Theory, 2004, Brill Academic Publishers: Brill Academic Publishers Utrecht · Zbl 1061.60093
[9]	Chaudhry, M. L.; Templeton, J. G.C., A First Course in Bulk Queues, 1983, Wiley: Wiley New York · Zbl 0559.60073
[10]	M.L. Chaudhry, J.G.C. Templeton, Bulk Queues, Selecta Statistica Canadiana, No. V., Department of Mathematics, McMaster University, Hamilton, Ontario, 1986.
[11]	Dorfman, R., The detection of defective members of large populations, Annals of Mathematical Statistics, 14, 436-440, 1943
[12]	Du, D.-Z.; Hwang, F. K., Combinatorial Group Testing and Its Applications, 2000, World Scientific: World Scientific Singapore · Zbl 0952.90001
[13]	Hammick, P. A.; Gastwirth, J. L., Group testing for sensitive characteristics: Extension to higher prevalence levels, International Statistical Review, 62, 319-331, 1994 · Zbl 0828.62095
[14]	Hung, M. C.; Swallow, W. H., Use of binomial group testing in tests of hypotheses for classification or quantitative covariables, Biometrics, 56, 204-212, 2000 · Zbl 1060.62626
[15]	Litvak, E.; Tu, X. M.; Pagano, M., Screening for the presence of a disease by pooling sera samples, Journal of the American Statistical Association, 89, 424-434, 1994 · Zbl 0925.62469
[16]	Macula, A. J., Probabilistic nonadaptive and two-stage group testing with relatively small pools and DNA library screening, Journal of Combinatorial Optimization, 2, 385-397, 1999 · Zbl 1002.92551
[17]	Macula, A. J., Probabilistic nonadaptive group testing in the presence of errors and DNA library screening, Annals of Combinatorics, 3, 61-69, 1999 · Zbl 1063.62599
[18]	Nair, S. S.; Neuts, M. F., Distribution of occupation time and virtual waiting time of a general class of bulk queues, Sankhyā, Series A, 34, 17-22, 1972 · Zbl 0251.60058
[19]	Neuts, M. F., A general class of bulk queues with Poisson input, Annals of Mathematical Statistics, 38, 759-770, 1967 · Zbl 0157.25204
[20]	Saaty, T. L., Mathematical Methods of Operations Research, 1959, McGraw-Hill: McGraw-Hill New York · Zbl 0084.15801
[21]	Tu, X. M.; Litvak, E.; Pagano, M., On the informativeness and accuracy of pooled testing in estimating prevalence of a rare disease: Application to HIV screening, Biometrika, 82, 287-297, 1995 · Zbl 0823.62095
[22]	Valluri, S. R.; Jeffrey, D. J.; Corless, R. M., Some applications of the Lambert W function to physics, Canadian Journal of Physics, 78, 823-831, 2000
[23]	Wein, L. M.; Zenios, S. A., Pooled testing for HIV screening: Capturing the dilution effect, Operations Research, 44, 543-569, 1996 · Zbl 0865.90091