Parallel tests contain different items but have the same measurement properties. They are administered at the same or different time slots and their measurement results must be comparable. The problem of automated parallel tests assembly is studied for a long time, and many (mostly improvement) heuristic solutions are proposed and elaborated in literature. Such approaches frequently suffer from algorithms of unpredictable execution time, forcing the methods to terminate execution when some time limit or solution quality is reached. This paper proposes an efficient method of polynomial complexity, as a complete solution to the automated parallel tests assembly problem. The method uses the idea of Nawaz, Enscore, and Ham constructive heuristic algorithm to reduce the number of examined permutations, originally exploited for solving the permutation flow-shop sequencing problem. We compared the experimental results of the proposed method with two methods based on improvement heuristics that solve the same problem formulation, simulated annealing and variable neighborhood search. The main advantages of the proposed method are predictable execution time and implementation simplicity. Achieved quality of assembled tests, combined with predictable test assembly execution time, may be of particular interest in cases when computational resources for test assembly and administering are overloaded.

Parallel test forms are ubiquitous in the educational, aptitude, achievement, and licensure testing. The problem of automated assembling of parallel test forms has been extensively explored for almost 40 years. Many different mathematical models of the problem formulations and a plenty of different solutions have emerged over the last two decades, indicating that the problem has matured. However, its investigation is still challenging, especially today, when the importance of distance learning and remote knowledge testing is rapidly growing. The diversity of proposed approaches originated notably from the variety of scientific fields involved such as psychometrics, applied mathematics, operations research, and artificial intelligence. Majority of solutions of the problem are (meta)heuristics-based, since they consider the problem as a combinatorial optimization problem which is NP-hard. In this paper, a comprehensive review of this research field, referring to related works since 1985, is conducted. Problem formulations and solutions of the problem are separately classified. Possible avenues of future research are pointed out.