Variable neighborhood search heuristics for a test assembly design problem

Test assembly design problems appear in the areas of psychology and education, among others. The goal of these problems is to construct one or multiple tests to evaluate the test subject. This paper studies a recent formulation of the problem known as the one-dimensional minimax bin-packing problem with bin size constraints (MINIMAX-BSC). In the MINIMAX-BSC, items are initially divided into groups and multiple tests need to be constructed using a single item from each group, while minimizing differences among the tests. We first show that the problem is NP-Hard, which remained an open question. Second, we propose three different local search neighborhoods derived from the exact resolution of special cases of the problem, and combine them into a variable neighborhood search (VNS) metaheuristic. Finally, we test the proposed algorithm using real-life-based instances. The results show that the algorithm is able to obtain optimal or near-optimal solutions for instances with up to 60 000-item pools. Consequently, the algorithm is a viable option to design large-scale tests, as well as to provide tests for online small-sized situations such as those found in e-learning platforms.