Improved Genetic Operators for the Multiobjective Generalized Assignment Problem

**
Robert F. Subtil,
Eduardo G. Carrano,
Ricardo H. C. Takahashi,
Marcone J. F. Souza,
Sérgio R. de Souza.
**

The original formulation of the Generalized Assignment Problem (GAP) consists in, given a set of n different tasks and m different agents, as- signing each task to an agent in such a way that a cost function is minimized. A previous work introduced the Equilibrium Function as a new objective function in the problem formulation. The purpose of this second objective function is to minimize the maximum difference between the amount of work assigned to the agents. This allows better distributions of the tasks between the agents than the results found from the original problem, with a small increase in the cost. This paper proposes new crossover and mutation operators that produce improve- ments in the algorithm presented in [Subtil et al. 2010], leading to consider- ably better Pareto approximations than the ones obtained in the previous work, within the same number of function evaluations. The proposed operators exploit problem-specific information in a probabilistic way, performing operations that lead to objective function enhancement or feasibility enhancement with greater probability than operations that do not cause such enhancements. A statistical comparison procedure is employed for supporting such conclusions.

http://www.lbd.dcc.ufmg.br/colecoes/enia/2011/0040.pdf

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br