A standard genetic algorithm for clustering with precedence constraints

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 as 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.