Variable neighborhood search heuristics for a test assembly design problem

Jordi Pereira, Mariona Vilà

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


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.

Original languageEnglish
Pages (from-to)4805-4817
Number of pages13
JournalExpert Systems with Applications
Issue number10
StatePublished - 15 Jun 2015
Externally publishedYes


  • Bin packing
  • Test assembly design
  • Test splitting
  • Variable neighborhood search


Dive into the research topics of 'Variable neighborhood search heuristics for a test assembly design problem'. Together they form a unique fingerprint.

Cite this