In recent years, with the rapid development of computing technology, developing parallel procedures to solve large-scale ranking and selection (R&S) problems has attracted a lot of research attention. In this paper, we take fixed-budget R&S procedure as an example to investigate potential issues of developing parallel procedures. We argue that to measure the performance of a fixed-budget R&S procedure in solving large-scale problems, it is important to quantify the minimal growth rate of the total sampling budget such that as the number of alternatives increases, the probability of correct selection (PCS) would not decrease to zero. We call such a growth rate of the total sampling budget the rate for maintaining correct selection (RMCS). We show that a tight lower bound for the RMCS of a broad class of existing fixed-budget procedures is in the order of [Formula: see text], where k is the number of alternatives. Then, we propose a new type of fixed-budget procedure, namely the fixed-budget knockout-tournament ([Formula: see text]) procedure. We prove that, in terms of the RMCS, our procedure outperforms existing fixed-budget procedures and achieves the optimal order, that is, the order of k. Moreover, we demonstrate that our procedure can be easily implemented in parallel computing environments with almost no nonparallelizable calculations. Last, a comprehensive numerical study shows that our procedure is indeed suitable for solving large-scale problems in parallel computing environments. History: Accepted by Bruno Tuffin, Area Editor for Simulation. Funding: Y. Zhong was supported by the National Natural Science Foundation of China [Grant 72101047]. L. J. Hong was supported by the National Natural Science Foundation of China [Grants 72091211 and 72161160340]. G. Jiang was supported by the National Natural Science Foundation of China [Grants 72121001 and 72171060]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1221 .

With the rapid development of computing technology, using parallel computing to solve large-scale ranking-and-selection (R&S) problems has emerged as an important research topic. However, direct implementation of traditionally fully sequential procedures in parallel computing environments may encounter various problems. First, the scheme of all-pairwise comparisons, which is commonly used in fully sequential procedures, requires a large amount of computation and significantly slows down the selection process. Second, traditional fully sequential procedures require frequent communication and coordination among processors, which are also not efficient in parallel computing environments. In this paper, we propose three modifications on one classical fully sequential procedure, Paulson’s procedure, to speed up its selection process in parallel computing environments. First, we show that if no common random numbers are used, then we can significantly reduce the computation spent on all-pairwise comparisons at each round. Second, by batching different alternatives, we show that we can reduce the communication cost among the processors, leading the procedure to achieve better performance. Third, to boost the procedure’s final-stage selection, when the number of surviving alternatives is less than the number of processors, we suggest to sample all surviving alternatives to the maximal number of observations that they should take. We show that, after these modifications, the procedure remains statistically valid and is more efficient compared with existing parallel procedures in the literature. Summary of Contribution: Ranking and selection (R&S) is a branch of simulation optimization, which is an important area of operations research. In recent years, using parallel computing to solve large-scale R&S problems has emerged as an important research topic, and this research topic is naturally situated in the intersection of computing and operations research. In this paper, we consider how to improve a fully sequential R&S procedure, namely, Paulson’s procedure, to reduce the high computational complexity of all-pairwise comparisons and the burden of frequent communications and coordination, so that the procedure is more suitable and more efficient in solving large-scale R&S problems using parallel computing environments that are becoming ubiquitous and accessible for ordinary users. The procedure designed in this paper appears more efficient than the ones available in the literature and is capable of solving R&S problems with over a million alternatives in a parallel computing environment with 96 processors. The paper also extended the theory of R&S by showing that the all-pairwise comparisons may be decomposed so that the computational complexity may be reduced significantly, which drastically improves the efficiency of all-pairwise comparisons as observed in numerical experiments.