XXIII Encontro Nac. de Eng. de Produção - Ouro Preto, MG, Brasil, 21 a 24 de out de 2003

Algoritmo genético para o balanceamento de linhas de produção Sérgio Fernando Mayerle (EPS / UFSC – [email protected]) Rodrigo Nereu dos Santos (EPS / UFSC – [email protected])

Resumo Neste artigo é discutido o problema de balanceamento de linhas de produção simples (produto único), o qual consiste na obtenção de uma alocação de um conjunto de tarefas aos postos (ou estações) de trabalho, respeitando a relação de precedência na execução destas tarefas. Duas situações distintas são consideradas: reduzir o número de postos de trabalho, considerando o tempo de ciclo que satisfaça a demanda e/ou reduzir o tempo de ciclo, dado o número de postos de trabalho. Para cada um destes problemas é apresentado um modelo de Programação Linear Binária, os quais caracterizam a solução ótima do problema. Um algoritmo genético é proposto para a solução destes problemas, e aplicado na solução de um problema de 70 tarefas proposto por Tonge (1961), considerando distintos postos de trabalho. Os resultados obtidos são comparados com um limite inferior, demonstrando a eficiência do método proposto. Palavras Chave: assembly line balancing; genetic algorithmic; combinatorial optimization. 1. Introdução O problema de balanceamento de linhas de produção (LBP) refere-se à alocação das atividades de transformação em postos de trabalho, de modo que se obtenha o menor número de postos capaz de satisfazer a demanda e, ainda, que o tempo de ciclo seja o menor possível, de modo a aumentar a produtividade. Este problema é formulado a partir de um conjunto de tarefas a serem alocadas, para as quais são conhecidos os tempos padrões de execução. O balanceamento de linhas também propicia, dentre outras vantagens, a recuperação mais rápida do investimento inicial e o aumento da capacidade de atendimento à demanda. Considerando n tarefas a serem executadas, existem n ! possíveis permutações entre as mesmas, de modo que a busca da solução por métodos de enumeração explícita torna-se impossível para a maioria dos casos práticos, remetendo a solução deste problema ao uso de meta-heurísticas tais como: tabu search, simulated annealing e genetic algorithm (GA). Diversos trabalhos já foram desenvolvidos na otimização de problemas combinatoriais com a utilização destas meta-heurísticas, incluindo variações dos problemas clássicos de job shop e flow shop, bem como outros problemas de igual complexidade. Mais especificamente, o problema de balanceamento de linhas de produção foi discutido por Tonge (1961 e 1965), Moodie e Young (1965), Nevins (1972), Talbot et ali (1986), que comparam diversas técnicas heurísticas, e Baybars (1986), que apresenta uma revisão dos principais algoritmos exatos disponíveis. Mais recentemente Anderson & Ferris (1994) apresentam um GA para este mesmo problema. 2. Caracterização do problema e formulação matemática Considere uma linha de produção simples (produto único) contendo um conjunto de postos de trabalho, denotado por I = {1,2,...,m } , aos quais devem ser alocadas tarefas de um conjunto J = {1,2,...,n } . Para o produto em questão, considere que para cada tarefa k ∈ J existe um ENEGEP 2003

ABEPRO

1

XXIII Encontro Nac. de Eng. de Produção - Ouro Preto, MG, Brasil, 21 a 24 de out de 2003

subconjunto de tarefas predecessoras, J k ⊂ J e um tempo de execução tk . Considere, ainda, que seja conhecido o maior tempo de ciclo T o com o qual é possível atender a demanda existente. Então, o menor número de postos de trabalho que contenha todas as tarefas do conjunto J , pode ser determinado pela solução do seguinte modelo de programação linear binária: LBP-1

Min z1 = ∑ ∑ Pi ⋅ x ij

(2.1)

i ∈I j ∈J

s.a:

∑x

ij

=1

∀j ∈ J

(2.2)

i ∈I

∑t

j

⋅ x ij ≤ T o

∀i ∈ I

(2.3)

j ∈J

∑i ⋅ x

ij

≤

i ∈I

∑i ⋅ x

ik

∀k ∈ J ; j ∈ J k

(2.4)

i ∈I

x ij ∈ { 0,1}

∀i ∈ I ; j ∈ J

(2.5)

onde: x ij = 1 caso a tarefa j seja alocada ao posto i , e x ij = 0 em caso contrário; e Pi = n i é uma penalidade associada à ativação do i -ésimo posto de trabalho.

No modelo acima, a equação (2.2) garante que cada tarefa seja atribuída a exatamente um posto de trabalho, e as inequações (2.3) e (2.4) garantem, respectivamente, que nenhum posto de trabalho receba um subconjunto de tarefas cujo tempo de execução exceda o tempo de ciclo T o e que as relações de precedência entre tarefas sejam obedecidas. Neste modelo, como se pode observar, a função objetivo (2.1) é construída de modo a penalizar o incremento do número de postos de trabalho. Para a formulação do modelo acima, o número mínimo de postos de trabalho, m , poderá ser estimado a partir da construção de uma solução inicial usando um método heurístico qualquer. No pior caso poderá ser adotado m = n , ou seja, que em cada posto seja alocado exatamente uma tarefa e, ainda, que o tempo de ciclo total seja estabelecido pela tarefa de maior duração. Para o problema (2.1)-(2.5), tem-se como resultado uma solução viável, isto é, que obedece a relação de precedência entre as atividades e o tempo de ciclo que garante o atendimento da demanda, com o menor número de postos de trabalho. Este número mínimo de postos de trabalho poderá ser determinado por:

(

m = max i , j i ⋅ x ij

)

(2.6)

e a partir desta solução, um segundo problema de programação linear binária poderá ser formulado para a obtenção do menor tempo de ciclo T , considerando que as tarefas serão alocadas em m postos:

ENEGEP 2003

ABEPRO

2

XXIII Encontro Nac. de Eng. de Produção - Ouro Preto, MG, Brasil, 21 a 24 de out de 2003

LBP-2

Min z 2 = T s.a:

m

∑x

ij

(2.7) =1

∀j ∈ J

(2.8)

i =1

∑t

j

⋅ x ij ≤ T

∀i = 1,...,m

(2.9)

j ∈J m

∑i ⋅ x

ij

≤

i =1

x ij ∈ { 0,1}

m

∑i ⋅ x

ik

∀k ∈ J ; j ∈ J k

(2.10)

i =1

∀i ∈ I ; j ∈ J

(2.11)

Pode-se observar que os modelos apresentados acima se diferenciam, basicamente, quanto à função objetivo. Enquanto o primeiro trata de obter o menor número de postos de trabalho para um tempo máximo de ciclo definido pelo problema, o segundo busca determinar o menor tempo de ciclo, dado o número de postos obtidos através da solução do primeiro modelo. Apesar da relativa simplicidade dos modelos acima apresentados, as soluções destes são de difícil obtenção através da utilização de algoritmos clássicos de programação linear inteira, especialmente para o caso de problemas que apresentam grande número de tarefas. 3. Algoritmo proposto Para solução dos problemas LBP-1 e LBP-2, foram desenvolvidos dois GA’s, diferenciados quanto à avaliação do fitness, cujos aspectos serão tratados posteriormente. Os GA’s são procedimentos heurísticos baseados no princípio da evolução das espécies enunciado por Darwin em 1879. A idéia de utilizar tal princípio na solução de problemas matemáticos, notadamente os de otimização, foi desenvolvida inicialmente por John Holland, no início da década de 70. Apesar deste processo de evolução não ser totalmente conhecido pelos biólogos, alguns aspectos referentes ao mesmo são bem aceitos. Em primeiro lugar, sabe-se que a evolução se processa por meio de dispositivos biológicos denominados de cromossomos, os quais armazenam as características dos indivíduos. Através de um processo de seleção natural, indivíduos mais bem adaptados ao meio (maior fitness) conseguem se reproduzir com maior freqüência, transmitindo suas características genéticas aos descendentes. A reprodução é a chave pela qual a evolução se processa. Através da combinação dos materiais genéticos dos ancestrais, novos cromossomos são produzidos, os quais, eventualmente passam por um processo denominado de mutação. Através deste processo, os descendentes poderão vir a apresentar características distintas de seus ancestrais. Eventualmente, tais características permitem que o indivíduo gerado venha a ter uma maior capacidade de adaptação ao meio. Os GA’s apresentam uma estrutura similar ao que se observa na natureza, conforme descrito, e seus passos principais podem ser assim delineados: Gerar uma população inicial Avaliar o fitness dos indivíduos da população Repetir Selecionar ancestrais da população Gerar descendentes através do cruzamento genético entre os ancestrais selecionados Realizar uma eventual mutação nos descendentes gerados Avaliar o fitness dos descendentes gerados Substituir alguns indivíduos da população (ou todos) pelos descendentes gerados Até que uma solução satisfatória tenha sido encontrada

Dentro desta perspectiva, os aspectos relevantes, que passarão a ser discutidos, são: a estrutura do cromossomo, a avaliação do fitness e os processos de seleção natural, de cruzamento e de mutação. ENEGEP 2003

ABEPRO

3

XXIII Encontro Nac. de Eng. de Produção - Ouro Preto, MG, Brasil, 21 a 24 de out de 2003

3.1. Estrutura do cromossomo e geração da população inicial Uma solução viável para o problema de balanceamento de linhas de produção simples corresponde a uma permutação das tarefas a serem alocadas, de modo a satisfazer as relações de precedência e o tempo de ciclo estabelecido. Neste contexto, a caracterização de uma solução em particular pode ser realizada por meio de um vetor de inteiros, onde cada elemento corresponde ao índice de uma tarefa. Neste vetor não pode haver repetição de índices de tarefa, já que cada tarefa deve ser alocada a um e somente um posto. Na figura 1, pode-se observar a representação gráfica desta estrutura para um problema com 10 tarefas, na qual a primeira tarefa a ser realizada é a de índice 3, a segunda de índice 4, e assim sucessivamente, até a última tarefa (índice 10). 3

4

2

6

1

7

9

8

5

10

Figura 1 - Esquema de representação do cromossomo, para o problema de balanceamento de linhas de produção.

Para formação de uma população inicial contendo K soluções aleatórias, denotada por π = {S1,...,Sr ,...,S K } , pode-se tomar inicialmente, para cada uma destas soluções, a seqüência de tarefas S = (1,2,...,n ) , e realizar sucessivas trocas de posições (aleatória) entre pares de elementos. Seja Sr = (sr 1, sr 2 ,..., srn ) o vetor resultante deste procedimento de trocas. Note-se que a aplicação deste procedimento não garante que as relações de precedência entre tarefas sejam satisfeitas. Contudo este aspecto poderá ser devidamente considerado através de funções de penalidade apropriadas, quando da avaliação do fitness de cada indivíduo, como será visto mais à frente. Para caracterização completa da solução, é necessário identificar em qual posto encontra-se cada tarefa, como poderá ser visto em mais detalhes no algoritmo que será apresentado posteriormente. 3.2. Avaliação do fitness O fitness de um cromossomo representa a capacidade do indivíduo adaptar-se ao meio. No caso dos algoritmos genéticos, quando aplicados sobre problemas de otimização combinatorial, a medida de fitness costuma relacionar-se com o valor da função objetivo. Para um indivíduo Sr = (sr 1, sr 2 ,..., srn ) , o número de inviabilidades NI r na relação de precedência entre tarefas e o valor da função objetivo zr , poderão ser calculados, considerando o tempo de ciclo T o e as notações tα ≡ t (α ) e J α ≡ J (α ) , através do procedimento CalculaParametrosFitness apresentado no Quadro I. Após a aplicação deste procedimento, o valor de fitness poderá ser calculado usando qualquer função f (Sr ) que satisfaça as seguintes condições: i) Se NI r < NI q , então f (Sr ) > f (S q ) ; ii) Se NI r = NI q e z r < z q , então f (Sr ) > f (S q ) . Assim, com base nos valores f (Sr ) , calculados para todo Sr pode-se ordenar os indivíduos de π , de modo que f (S1 ) ≥ f (S 2 ) ≥ ... ≥ f (S K ) .

ENEGEP 2003

ABEPRO

4

XXIII Encontro Nac. de Eng. de Produção - Ouro Preto, MG, Brasil, 21 a 24 de out de 2003

procedimento CalculaParametrosFitness ( Sr ); início i ← 1; NI r ← 0 ; Tac ← 0 ;

// inicializar número do posto // inicializar número de inviabilidades // inicializar tempo acumulado

zr ← 0 ; v ← 0; repetir v ← v + 1; k ←1; enquanto k < v faça início se srv ∈ J (srk ) então NI r ← NI r + 1 ; k ← k + 1; fim; se t (srv ) + Tac ≤ T 0 então Tac ← Tac + t (srv ) senão início i ← i + 1; Tac ← t (srv ) ; fim; zr ← zr + Pi

// inicializar a função objetivo // inicializar índice da tarefa

// inicializar índice tarefas predecessoras

// incrementar número de inviabilidades // tomar a próxima tarefa // incrementar tempo acumulado // incrementar número do posto // redefinir o tempo acumulado // incrementar a função objetivo

// alocar tarefa srv ao posto i Posto (srv ) = i ; até que v = n ; Retornar NI r , z r e a lista de tarefas com os respectivos postos; fim.

Quadro I – Procedimento utilizado para cálculo dos parâmetros da função de fitness

3.3. Seleção natural e cruzamento (crossover) No GA proposto para a solução do problema de balanceamento de linhas de produção simples, a operação de cruzamento realiza-se entre dois indivíduos, denotados por Sr = (sr 1, sr 2 ,..., srn ) e S q = (sq1, sq 2 ,..., sqn ) , escolhidos aleatoriamente e com igual probabilidade na população π , a fim de gerar um novo descendente Sd = (sd1, sd 2 ,...,sdn ) , a ser incluído na população, em substituição a S K , caso f (Sd ) > f (S K ) . O procedimento de cruzamento proposto ocorre de modo que as restrições de precedência, denotadas por α a β (leia-se α precede β ), sejam privilegiadas, conforme apresentado no Quadro II. Note-se que na seleção realizada, apesar de ser utilizada uma distribuição uniforme, os indivíduos mais promissores acabam permanecendo por mais tempo na população e, consequentemente, sendo escolhidos com maior freqüência para a realização da operação de cruzamento. 3.4. Mutação A mutação nos seres vivos é um fenômeno raro no processo de reprodução, e consiste em modificar de forma aleatória algum gene no cromossomo do indivíduo descendente gerado. Entretanto, no algoritmo proposto ela está presente na concepção de qualquer novo indivíduo. Assim, ocorre que neste algoritmo a mutação é projetada a dar preferência ao preenchimento dos postos de trabalho, mantida a ordem de precedência entre tarefas, e observadas as disponibilidades de tempo para execução da tarefa no posto, conforme apresentado no Quadro III. Em outras palavras, na geração de cada indivíduo é considerada a possibilidade de trocar a ordem das tarefas, desde que isto possibilite a melhor utilização de ociosidades existentes em postos de trabalho de menor índice, desde que esta troca não viole alguma restrição adicional de precedêcia já satisfeita. ENEGEP 2003

ABEPRO

5

XXIII Encontro Nac. de Eng. de Produção - Ouro Preto, MG, Brasil, 21 a 24 de out de 2003 procedimento Cruzamento ( Sr , Sq ); início para k = 1 até n faça se srk = sqk então sdk = srk ;

// para todos os genes do cromossomo // se forem iguais, manter descendente

se srk a sqk então início

// se srk precede sqk

sdk = srk ; Trocar ( Sq , srk , sqk ); fim; se sqk a srk então início

sdk

// se sqk precede srk

= sqk ;

// executar antes sqk

Trocar ( Sr , srk , sqk ); fim; se Not (srk a sqk ) e Not (sqk a srk )

fim; Retornar S d ; fim.

// permutar posição dos genes em Sr // se srk e sqk não se precedem

então início p = Random ( q,r ); sdk = s pk ; se p = q

// executar antes srk // permutar posição dos genes em Sq

// escolha aleatória entre q e r // executar antes s pk (aleatório)

então Trocar ( Sr , srk , sqk )

// permutar posição dos genes em Sr

senão Trocar ( S q , srk , sqk );

// permutar posição dos genes em Sq

fim;

Quadro II – Procedimento utilizado para realização da operação de cruzamento entre dois indivíduos. procedimento Mutação ( Sr ); Início m =0; para i = 1 até n faça Slack (i ) = T o ; para k = 1 até n faça First (k ) = 1 ; para k = 1 até n faça Posto (k ) = 0 ;

// inicializar o número de postos // inicializar folga do posto // inicializar primeiro posto para tarefa // inicializar primeiro posto para tarefa

para k = 1 até n faça início i = First (k ) ; enquanto Slack (i ) < t (srk ) faça i = i + 1;

Posto (srk ) = i ; se i > m então m = i ; Slack (i ) = Slack (i ) − t (srk ) ; para j = 1 até n faça se Posto (srj ) = 0 e srk a srj e First (srj ) < i então First (srj ) = i ;

// para todos genes do cromossomo // começando pela 1a. possibilidade // incrementar posto até encontrar folga // alocar tarefa srk ao posto i // corrigir número de postos, se necessário // descontar o tempo de srk na folga de i // revisar a 1a. possibilidade de alocação // das atividades sucessoras de srk

fim; Reordenar os elementos de Sr = (sr 1, sr 2 ,..., srn ) por ordem crescente de Posto (srk ) ; Retornar Sr ; fim.

Quadro III – Procedimento utilizado para realização da mutação em um indivíduo.

4. Resultados numéricos Dos diversos problemas de balanceamento de linhas de produção já consagrados na literatura tomou-se como exemplo numérico, para fins de comparação, o clássico problema de balanceamento de linhas elaborado por Tonge (1961), apresentado no anexo. Este exemplo foi escolhido devido a dois motivos: é um problema real proveniente da industria eletrônica; e numerosos autores o solucionaram por diferentes métodos e heurísticas (Tonge em 1965, ENEGEP 2003

ABEPRO

6

XXIII Encontro Nac. de Eng. de Produção - Ouro Preto, MG, Brasil, 21 a 24 de out de 2003

Moodie e Young também em 1965, Nevins em 1972 e Baybars em 1981). Neste contexto, para avaliar o algoritmo proposto, comparou-se o valor do tempo de ciclo obtido pela aplicação do GA, com o limite inferior calculado como se o balanceamento da carga de trabalho fosse ideal, isto é: LI =

∑t

j

(2.12)

m

Assim, para distintos postos de trabalho, obteve-se os seguintes resultados: m

11 10 9 8 7 6

Tempos de Ciclo (seg.)

T 341 373 414 464 532 617

LI 334,82 368,30 409,22 460,38 526,14 613,83

Desvio médio em relação ao limite inferior (%)

%

1,85 1,28 1,17 0,79 1,11 0,52 1,12

Tabela 1 – Resultados obtidos com a aplicação do algoritmo proposto ao problema de Tonge (1961).

Ressalta-se, todavia, que o limite inferior calculado pela expressão 2.12 é um valor teórico, dificilmente alcançável, tendo em vista as restrições de precedência entre tarefas, e as dificuldades de se realizar o empacotamento perfeito das tarefas alocadas aos postos de trabalho, dentro do tempo de ciclo estabelecido por este limite. 5. Conclusões e recomendações Embora, não se tenha realizado testes exaustivos com o algoritmo proposto, seu desempenho ficou muito próximo da otimalidade, quando aplicado ao problema de Tonge, inclusive com performance razoável de tempo de processamento. Portanto, uma vez que o algoritmo não se restringe à busca do menor número de postos de trabalho, mas, também, introduz a procura pelo menor tempo de ciclo para um dado número de postos de trabalho, verifica-se que o algoritmo apresenta grande potencial de aplicabilidade nas linhas de produção reais. Por outro lado, quanto às recomendações, sugere-se, em primeiro lugar, que seja ampliado o número de testes realizados com o algoritmo, incluindo outros problemas que tenham soluções por outros métodos heurísticos encontrados na literatura. Sugere-se, também, contemplar, no algoritmo proposto, o problema de balanceamento de linhas de produção para multi-produtos, nos quais considera-se que a linha sirva diversos modelos do mesmo tipo de produto ou, até mesmo, diferentes produtos. Por fim, poder-se-ia também desenvolver uma interface gráfica ao algoritmo, que de forma didática seria utilizada como ferramenta de ensino de engenharia. 6. Bibliografia ANDERSON, E. J. & FERRIS, M. C. (1994). Genetic Algorithms for Combinatorial Optimization: The Assembly Line Balancing Problem. ORSA Journal of Computing. Vol. 6, No. 2, p.161-173. ENEGEP 2003

ABEPRO

7

XXIII Encontro Nac. de Eng. de Produção - Ouro Preto, MG, Brasil, 21 a 24 de out de 2003

BAYBARS, I. (1986). A Survey of Exact Algorithms for the Simple Assembly Line Balancing Problem. Management Science. No. 32, p.909-932. McMULLEN, P.R. & FRAZIER, G. V. (1998). Using Simulated Annealing to Solve a Multiobjective Assembly Line Balancing Problem With Parallel Work Stations. International Journal of Productions Research 31 (10), 2717-2741. MOODIE, C. L. & YOUNG, H. H. (1965). A Heuristic Method of Assembly Line Balancing for Assumptions of Constant of or Variable Work Element Times. Journal of Industrial Engineering 16, 23-29. NEVINS, A. J. (1972). Assembly Line Balancing Using Best Bud Search. Management Science 18, 9, p.530. TALBOT, F. B.; PATTERSON, J. H. & GEHRLEIN, W. V. (1986). A Comparison of Heuristic Line Balancing Techniques. Management Science 32, 430-454. TONGE, F. M. (1961). A Heuristic Program of Assembly Line Balancing. Management Science 7, 21-42. TONGE, F. M. (1965). Assembly Line Balancing Using Probabilistic Combinations of Heuristics. Management Science 11, 727-735. 7. Anexo 41 16

56 68 30 11

31 31

24 12

33 102

53 44

32 50 51 11

05 6

68 72

01 17

02 66

06 88

03 54

04 52

08 128

70 27

12 21

23 73

69 23

09 68

10 70

11 85 18 319

tarefa tempo

15 94

16 90

17 59

44 43

25 152

35 35

36 40

37 2

38 1

27 45

14 135

07 21

48 56

26 42

21 50 22 40 20 54

62 27

29 26

19 19

49 59

45 30

39 3

46 83

47 89

40 13

42 25

61 25

28 74

55 38

52 26

34 46

13 134

54 121

63 156

43 21

50 43

65 15 64 28

66 26 67 18

57 22

58 7

59 16

60 32

Figura 2 – Diagrama de precedência do problema proposto por Tonge (1961).

ENEGEP 2003

ABEPRO

8