In this paper, we propose two new variants of the Biased Random-Key Genetic Algorithm. In the first, the algorithm assigns a gender to each chromosome and only allows crossover between chromosomes of different gender. In the second variant, more than two parents are used to generate a new offspring. Computational experiments are conducted on instances of set covering and set packing problems. We empirically show that the multi-parent modification is able to overcome the original biased random-key genetic algorithm although it requires slightly more time and iterations to converge.