A standard genetic algorithm for clustering with precedence constraints

Abstract

Our paper reports on the clustering of N items into a maximum of M non-overlapping groups subject to capacity and precedence constraints when grouping the items. The clustering criterion employed is that of total dissimilarity of items grouped together. This classification problem can, for instance, be applied to the clustering of tasks in Software production projects, The authors developed a genetic heuristic, based on a specific encoding to identify the group in which each element is inserted. Results of the computational experiments, involving comparison of the genetic heuristic with another improvement heuristic and a hybrid heuristic, indicate a favourable behaviour of the basic genetic for the smaller problems, as well as for the uncapacitated problems, in terms of the quality of the solution. However, for problems with a larger number of items, the genetic and the hybrid heuristics did not perform so well as the standard improvement heuristic. Although, in terms of computing time. the genetic heuristic is more expensive compared with the standard improvement heuristic, these experiments Will encourage us to redefine the genetic procedure

O problema neste artigo refere-se à classificação de N elementos num número máximo de M grupos disjuntos, satisfazendo as restrições de capacidade destes e as de precedência no agrupamento dos elementos, Como critério de agregação usa-se a minimização da dissemelhança total entre elementos colocados no mesmo grupo. Este problema de classificação pode ser aplicado, por exemplo. Ao desenho de software. É apresentada uma heurística genética com base numa codificação dos agrupamentos, identificação do índice do grupo em que cada elemento é colocado. Os resultados da experiência envolvendo a comparação da heurística genética com uma heurística melhorativa, e uma híbrida, indicam um melhor comportamento da heurística genética para problemas de pequena dimensão e para os problemas sem restrições de capacidade. Em relação ao tempo computacional a genética demonstrou-se mais desfavorável do que a melhorativa