ALGORITMOS E MODELOS PARA A TECNOLOGIA DE GRUPO
Ricardo Cézar Ferreira
Sandra Malta Barbosa
Universidade Estadual de Londrina, DMA, Londrina (PR)
José Francisco Ferreira Ribeiro
Cassilda Maria Ribeiro
Universidade de São Paulo, SCE, São Carlos (SP)
Abstract
In this paper is presented an overview about some algorithms and models for group
technology and cellular manufacturing design. The techniques analysed, studied and
presented are : codification of parts, clustering of matrices 0/1, mathematical
programming, graph theory, expert systems, data analysis and fuzzy set.
Keywords : group technology; manufacturing cells; discrete systems
1. Introdução
O emprego da Tecnologia de Grupo em sistemas de produção intermitente
dedicados à fabricação sob encomenda ou em lotes de pequeno e médio porte, pode aportar
a estes sistemas maior eficiência, produtividade e “just-in-time”. As similaridades de projeto
e fabricação existentes entre as peças agrupadas em uma mesma célula de manufatura
permite redução do tempo de preparação das máquinas ou “set up time”, padronização do
ferramental utilizado, diminuição do tempo de transporte das peças devida à concentração
da produção em células de porte reduzido, etc.
A primeira tarefa que deve ser realizada para a introdução da Tecnologia de Grupo
em uma indústria é o inventário e a codificação das peças manufaturadas, a realização de
um estudo para a determinação dos roteiros de fabricação para as peças, a criação de bases
de dados com o objetivo de auxiliar no projeto de uma nova peça ou roteiro de fabricação
e, se possível, a aplicação de sistemas automatizados para o sequenciamento, a
programação de operações e o CAD/CAM.
Em seguida, a organização física da fábrica deve passar por uma reestruturação,
passando a operar em sub-fábricas ou células de manufatura, mais fáceis de gerenciar que o
sistema global de fabricação disponível inicialmente. Para tanto, as peças a fabricar são
particionadas em famílias e as máquinas disponíveis em grupos, de tal modo que a cada
família corresponde um único grupo e vice-versa. Os pares [famílias de peças - grupos de
máquinas] constituem as células de manufatura. Deve-se ressaltar que o termo “células de
máquinas” é um sinônimo igualmente utilizado para designar os grupos de máquinas.
O problema do projeto das células de manufatura, necessárias à implantação da
Tecnologia de Grupo em uma indústria, tem sido muito estudado nos últimos anos por
autores que se utilizam das mais diferentes técnicas para a sua resolução. Trata-se de um
problema NP-completo (Garey e Johnson, 1979) e, assim, não se dispõe até o presente
momento, de um algoritmo “polinomial” ou eficiente para resolvê-lo. A regra geral consiste
em se projetar as células de manufatura a partir de métodos heurísticos ou de combinação
de métodos exatos e aproximados. Entre as técnicas que têm procurado contribuir para a
evolução da pesquisa na área e que têm apresentado resultados de boa qualidade, destacamse os métodos de codificação e classificação, o rearranjo de matrizes 0/1 de modo a definir
uma estrutura bloco-diagonal para as mesmas, as técnicas de programação matemática e
mais especificamente aquelas de programação inteira combinadas ou não com heurísticas, a
teoria dos grafos : particionamento e coloração, os sistemas especialistas, a análise de dados
e os conjuntos nebulosos.
O crescente interesse pela aplicação da Tecnologia de Grupo nas indústrias pode ser
avaliado, por exemplo, através dos estudos realizados e descritos em Hyer e Wemmerlöw
(1989) acerca de 32 companhias americanas que introduziram a Tecnologia de Grupo no
chão de fábrica, Arruda e Vila Fo (1995) sobre o estágio atual da implantação da Tecnologia
de Grupo em 33 indústrias paulistas e no levantamento de Ferreira e Resende (1995) em
outras 3 indústrias. Nas seções deste artigo, apresentadas a seguir, é proposta uma revisão
de algoritmos e modelos propostos nos últimos anos para auxiliar no projeto de células de
manufatura e incrementar a implantação eficiente da Tecnologia de Grupo nas indústrias
brasileiras.
2. Codificação e Classificação
Os métodos de codificação e classificação agrupam as peças de acordo com
características específicas, tais como : complexidade e forma geométrica, tipo do material,
forma da matéria prima ou precisão do acabamento das peças. Usando um sistema de
codificação, por exemplo : Opitz, Vuoso, Brisch, etc., as peças recebem um código
numérico, alfabético ou alfanumérico. Cada dígito deste código representa uma
característica da peça e as famílias são formadas realizando-se uma comparação entre os
dígitos dos respectivos códigos. Um método que realiza o projeto de células de manufatura
com base nesta técnica pode ser encontrada em Vila Fo (1982).
3. Rearranjo Matricial
Na formulação matricial, uma matriz de incidência [aij] constituída de elementos 0/1
é utilizada para representar o sistema de fabricação : aij = 1 (0) indica que a máquina j é
usada (não usada) para processar a peça i. Os algoritmos de rearranjo matricial alteram de
posição as linhas e colunas de aij com o objetivo de dar uma estrutura bloco-diagonal à
mesma e definir as células de manufatura. Dentre os métodos de rearranjo matricial
disponíveis na literatura, podemos citar : ROC-Rank Order Clustering (King, 1980), DCADirect Clustering Algorithm (Chan e Milner, 1981), BEA-Bond Energy Algorithm
(McCormick et al., 1972), CBM-Cost Based Method (Askin e Subramanian, 1987) e CIACluster Identification Algorithm (Kusiak e Chow, 1988).
4. Programação Matemática
O modelo matemático mais utilizado para auxiliar no projeto de células de
manufatura é um modelo de programação inteira, denominado modelo da “p-mediana”,
quando dispõe-se de um único roteiro de fabricação para as peças e da “p-mediana
generalizado”, quando se dispõe de mais de um roteiro (Kusiak, 1987b). Nestes modelos,
procura-se minimizar a soma total das dissimilaridades entre as peças reunidas em uma
mesma família e uma “peça-semente”, em torno do qual esta família está sendo formada. As
restrições do problema asseguram que as peças serão atribuídas a uma única família, e
especificam o número desejado de células.
Um estudo detalhado acerca dos coeficientes de similaridade é apresentado em
Witte (1980). Outros modelos matemáticos de programação inteira descritos na literatura e
que podem auxiliar na obtenção das células de manufatura são os seguintes : o modelo de
programação quadrática (Kusiak e Chow, 1988), o modelo de programação fracionária
(Lashkari et al., 1987) e o modelo de programação fracionária via transformação de Glover
e Woolsey (1974), igualmente proposto por Lashkari et al. (1987).
5. Teoria dos Grafos
Os métodos baseados em teoria dos grafos para efetuar o projeto de células de
manufatura são, via de regra, algoritmos iterativos de coloração dos nós de um grafo
G(N,A), onde N é o conjunto de nós, ou peças, e A é o conjunto de arestas, determinadas a
partir de uma dissimilaridade crítica estabelecida entre as peças que serão, em uma etapa
ulterior, atribuídas a diferentes células. Os algoritmos de Ferreira Ribeiro e Ribeiro (1993),
Ferreira Ribeiro e Alves (1994), Ferreira e Ferreira Ribeiro (1995), efetuam a coloração de
G com o auxílio respectivo das seguintes técnicas : procedimento “greedy”, técnica de
“ligações-contrações” e coloração de “árvores geradoras de peso máximo”.
Lee et al. (1982) e Vanelli e Kumar (1986) efetuam a partição de um grafo
representativo de um sistema de produção a partir de uma máquina definida como
“máquina-gargalo”. Ronconi e Armentano (1993) utilizam o algoritmo de Gomory e Hu
(1961) para particionar G e obter as células de manufatura. Barbosa e Ferreira Ribeiro
(1994) propõem um procedimento heurístico iterativo de subdivisão cruzada de peças e
máquinas, através da construção e avaliação de um grafo G, onde o critério de parada é a
determinação de uma partição do sistema de manufatura com um número mínimo de
movimentos inter-células.
6. Sistemas Especialistas
A utilização de sistemas especialistas para se efetuar o projeto de células de
manufatura é descrita, por exemplo, em Kusiak (1987a, c) e Kusiak e Chow (1988). Nestas
implementações, considera-se roteiros de fabricação alternativos para as peças e a geração
de cada solução parcial é realizada através de um algoritmo de partição selecionado
automaticamente pelo procedimento. Em Kusiak (1987c), procura-se determinar as células
de máquinas e as famílias de peças, bem como selecionar um AGV (transportador
automático de material), com correspondente custo mínimo, levando-se em conta que o
tempo de processamento disponível em cada máquina, que o limitante superior sobre a
freqüência de viagens do AGV e que o número máximo de máquinas em cada célula, não
podem ser excedidos. Por outro lado, pode-se trabalhar com outras hipóteses diferentes,
tais como a necessidade de se incluir determinadas máquinas em uma mesms célula devido a
necessidades tecnológicas.
7. Análise de Dados
A matriz representativa aij = 0/1 [peças x máquinas] de um sistema de produção é
suscetível de partição por meio de métodos estatísticos em geral e, em particular, pela
técnica de partição em torno de centros móveis, tais como o método das “nuvens
dinâmicas” (Diday, 1971). Este método parte de “peças-sementes” iniciais, uma para cada
família de peças a ser formada, em torno das quais é induzida uma partição do sistema em
células. Em seguida, escolhe-se como novas “peças-sementes” para induzir a formação de
novas células, as peças que apresentam a menor soma de dissimilaridades em relação às
outras peças atribuídas à família da qual ela faz parte. O procedimento é repetido até que
duas iterações sucessivas conduzam à mesma partição ou até que o número de iterações
atinja um número fixado previamente. O método proposto em Ferreira Ribeiro e Pradin
(1993) para o projeto de células de manufatura faz uso do método das “nuvens dinâmicas”,
inicializado por procedimentos específicos otimizados, uma vez que a convergência de tal
método depende fortemente da solução inicial.
8. Conjuntos Nebulosos
A maior parte dos trabalhos descritos na literatura para efetuar o projeto de células
de manufatura faz uso de uma matriz de incidência binária aij = 0/1, ou seja : uma peça i
utiliza uma máquina j e, neste caso aij = 1; caso contrário = 0. A técnica dos conjuntos
nebulosos permite trabalhar-se com matrizes não-binárias e, por conseguinte, a introdução
da incerteza usualmente encontrada na indústria quanto à máquina exata que vai realizar o
processamento de uma determinada operação. Os trabalhos propostos por Montevechi
(1995) e Montevechi e Gorgulho Jr. (1995) trabalham nesta linha de pesquisa. Em
Montevechi (1995), trabalha-se com uma matriz não binária, adaptando-se o conceito de
dominante e dominado, e utilizando-se um valor de pertinência representativo da
adequabilidade mínima de uma máquina executar ou não uma determinada operação
presente no roteiro de fabricação de uma peça. A grande vantagem de se utilizar uma matriz
não binária consiste em poder-se incluir máquinas alternativas para o processamento de uma
mesma operação.
9. Conclusão e Comentários
A Tecnologia de Grupo é de grande relevância para a elevação dos índices de
eficiência e implantação do “just-in-time” em indústrias caracterizadas essencialmente pela
produção intermitente, que trabalham sob encomenda ou em lotes, com cadências variando
de 1 a 50 peças por lançamento. O projeto de células de manufatura, condição necessária
para a partição do sistema global de fabricação em sub-sistemas ou células, pode ser
realizado por diferentes técnicas, como aquelas destacadas ao longo deste artigo, a saber :
a) codificação e classificação, b) rearranjo matricial, c) programação matemática, d) teoria
dos grafos, e) sistemas especialistas, f) análise de dados e g) conjuntos nebulosos, ou por
um outro método qualquer, como o antigo método de “inspeção visual” do inventário. A
escolha de uma técnica ou outra para se efetuar a seleção das células de manufatura
depende acentuadamente do problema concreto que se pretende resolver e são inúmeros os
fatores que podem influenciar nesta decisão. Entre estes fatores, dois são fundamentais : 1o)
a dimensão do problema a resolver, ou seja, o número de peças e máquinas a particionar.
Caso o problema seja de grande porte, a aplicação de técnicas de determinação da solução
ótima via programação inteira fica inviabilizada, dado que estas técnicas têm um custo
computacional altíssimo quando o número de variáveis a determinar apresenta mais de dois
dígitos; 2o) a disponibilidade ou não de roteiros de fabricação alternativos para as peças,
uma vez que se esta disponibilidade não existe, os métodos para os quais a matriz
representativa dos sistemas de produção é estritamente binária, ou seja, aij = 0/1, são
comprovadamente suficientes para a resolução do problema. Caso existam roteiros
alternativos de fabricação, as opões de formulação matemática e algoritmos de resolução
mais interessantes se concentram em modelos como o da “p-mediana generalizado”, a
técnica dos sistemas especialistas ou dos conjuntos nebulosos.
10. Referências Bibliográficas
Arruda, P. E. S., Vila Fo, E. G., Levantamento do estágio atual de implantação da TG e
células de manufatura no Estado de São Paulo, XV ENEGEP/ I ICIE, São Carlos, SP,
pp. 1559-1562, 1995
Askin, R., Subramanian, S., A cost-based heuristic for GT configuration, Int. J. Prod. Res.,
25, 1, pp. 101-114, 1987
Barbosa, S. M., Ferreira Ribeiro, J. F., Projeto de células de manufatura com número
mínimo de movimentos inter-células, XVIII Cong. Nac. Mat. Apl. Comp., Curitiba, PR,
pp. 430-434, 1995
Burbidge, J. L., The introduction of Group Technology, John Wiley, 1975
Chan, H. M., Milner, D. A., Direct clustering algorithm for GT in cellular manufacturing, J.
Manuf. Syst., 1, 1, pp. 65-74, 1981
Diday, E., Une nouvelle méthode en classification automatique et reconnaissance de formes,
Rev. Stat. Appl., 19, 2, pp. 213-220, 1971
Ferreira Ribeiro, J. F., Pradin, B., A methodology for cellular manufacturing design, Int. J.
Prod. Res., 31, 1, pp. 235-250, 1993
Ferreira Ribeiro, J. F., Ribeiro, C. M., Um algoritmo de coloração em grafos para o projeto
de células de manufatura, XIV Cong. Iber. Lat. Amer. Mét. Comp. Eng., São Paulo, SP,
pp. 898-903, 1993
Ferreira Ribeiro, J. F., Alves, M. R. P. A., Projeto de células de manufatura por meio de
ligações-contrações, XV Cong. Iber. Lat. Amer. Mét. Comp. Eng., Belo Horizonte, MG,
pp. 1470-1476, 1994
Ferreira, R. C., Ferreira Ribeiro, J. F., Coloração em grafos : uma aplicação em TG, XV
ENEGEP/ I ICIE, São Carlos, SP, pp. 1142-1147, 1995
Ferreira, M. S., Resende, M. O., Um exame à prática do controle de produção em células
de manufatura, XV ENEGEP/ I ICIE, São Carlos, SP, pp. 1579-1583, 1995
Garey, M. R., Johnson, D. S., Computers and intractability : a guide to the theory of Npcompleteness, Freeman, 1979
Glover, F., Woolsey, E., Converting the 0/1 polynomial problem to a 0/1 linear
programming, Oper. Res., 22, pp. 180-182, 1974
Gomory, R. E., Hu, T. C., Multi-terminal network flows, Siam J. Appl. Math., 9, 4, pp.
551-570, 1961
Hyer, N. L., Wemmerlöw, U., GT in the US manufacturing industry : a survey of current
practices, Int. J. Prod. Res., 27, 8, pp. 1287-1304. 1989
King, J. B., Machine-component grouping formation in GT : review and extension, Int. J.
Prod. Res., 25, 12, pp. 1715-1728, 1980
Kusiak, A., Artificial intelligence and operations research in FMS, Inform. Syst. Oper. Res.,
25, pp. 2-12, 1987a
Kusiak, A., The generalized group technology concept, Int. J. Prod. Res., 25, 4, pp. 561569, 1987b
Kusiak, A., Exgt-s : a knowledge based system for GT, Int. J. Prod. Res., 26, 5, pp. 887904, 1987c
Kusiak, A., Chow, W. S., Decomposition of manufacturing systems, IEEE J. Rob. and Aut.,
4, 5, pp. 457-471, 1988
Lashkari, R. S., Dutta, S. P., Nadoli, G., Part-family formation in FMS : an integer
programming approach, in : Modern Production Management Systems, A. Kusiak, pp.
627-635, 1987
Lee, J. L., Vogt, W. G., Mickle, M. H., Calculation of shortest paths by optimal
decomposition, IEEE Trans. Syst. Man. Cyb., 12, pp. 410-415, 1982
McCormick, W. T., Schweitzer, P. J., White, T. W., Problem decomposition and data
reorganization by cluster technique, Oper. Res., 20, 20, pp. 993-1009, 1972
Montevechi, J. A. B., Algoritmo de formação de células de manufatura adaptados à
incerteza, XV ENEGEP/ I ICIE, São Carlos, SP, pp. 1068-1072, 1995
Montevechi, J. A. B., Gorgulho Jr., J. H. C., Uma proposta computacional para inferência
reversa fuzzy, XV ENEGEP/ I ICIE, São Carlos, SP, pp. 1402-1409, 1995
Ronconi, D. P., Armentano, V. A., Um método heurístico baseado em grafos para a
formação de células de manufatura, Cadernos DEP-UFSCar, 21, pp. 24-28, 1993
Vanelli, A., Kumar, K. R., A method for finding minimal bottleneck cells for grouping partmachine families, Int. J. Prod. Res., 24, 2, pp. 387-400, 1986
Vila Fo, E. G., Introdução à TG : um novo enfoque em sistemas de produção, Tese de
Mestrado USP-EESC-SEM, São Carlos, SP, 1982
Witte, J., The use of similarity coefficients in production flow analysis, Int. J. Prod. Res.,
18, 4, pp. 503-514, 1980
(079)