Nesta dissertação é apresentado um algoritmo de coloração em grafos para o projeto de células de manufatura em Tecnologia de Grupo. O algoritmo proposto computa as dissimilaridades entre as peças e estabelece uma partição de peças e máquinas por meio da construção e coloração de uma árvore de peso máximo em um número de cores igual ao número requerido de células. Este algoritmo permite a resolução eficiente de exemplos da literatura, apesar do caráter não polinomial do problema estudado. O programa correspondente foi escrito em Turbo-Pascal e está implantado em um microcomputador.

In this thesis a graph colouring algorithm is presented for cellular manufacturing design in Group Technology. The proposed algorithm computes dissimilarities between parts and establishes a partition of parts and machines through the construction and colouring of a maximum spanning tree in a number of colours equals to the desired number of cells. This algorithm allows us to solve efficiently some examples of the literature, despite the non-polynomial nature of the problems studied. The corresponding program is written in Turbo-Pascal and runs on a micro-computer.