A Hybrid Genetic Algorithm for the One-Dimensional Minimax Bin-Packing Problem with Assignment Constraints

Vilà, M.; Pereira, J.; Fonseca, R.; Weber, GW.; Telhada, J.

Abstract

In this paper, the one-dimensional minimax bin-packing problem with assignment constraints is studied. Among other applications, this problem is used in test-splitting, which consists in assigning several sets of questions into different questionnaires so that every one of these questionnaires contains one question from each one of the original sets. Questions have a weight associated, which typically corresponds to a measure of their difficulty, and the objective is to split the questions among the questionnaires in such a way that the weights are distributed as evenly as possible. We propose a hybrid genetic algorithm for solving this problem, which is then tested on a benchmark set of practically-sized instances. The results show its efficiency in solving large size instances from the literature.

Más información

Editorial: Springer
Fecha de publicación: 2016
Año de Inicio/Término: May 29-31, 2014
Página de inicio: 183
Página final: 188
Idioma: English
URL: http://link.springer.com/chapter/10.1007/978-3-319-20430-7_23
DOI:

10.1007/978-3-319-20430-7_23

Notas: Indexed in Scopus