O menor caminho temporal exato é um algoritmo extremamente custoso compu- tacionalmente, o que inviabiliza sua aplicação para problemas de médio e grande porte, bem como para grandes lotes de produção. Uma maneira simples de simpliĄcar o pro- blema é aplicar uma heurística no estilo branch and bound, evitando a espera por eventos
4.2. Menor Tempo Heurístico 59 não controláveis.
Partindo do princípio de que, usualmente, eventos controláveis iniciam uma tarefa e eventos não controláveis indicam o Ąm de uma tarefa, não seria interessante deixar de executar um evento controlável para executar um evento não controlável. Dessa maneira, a heurística aqui desenvolvida se resume em, dado um estado, explorar apenas as transições relativas a eventos controláveis, a menos que um evento não controlável tenha que ser obrigatoriamente executado ou não haja eventos controláveis possíveis no estado. Um evento controlável deve ser obrigatoriamente executado pelo algoritmo apenas quando possui tempo zero, ou algum evento controlável gera um acréscimo de tempo superior ao tempo para a ocorrência do evento não controlável
As informações necessárias para a execução do algoritmo são as mesmas do algo- ritmo de menor tempo. O conjunto de estados do supervisor (𝑄), o conjunto de eventos do supervisor (Σ = Σ𝑐∪Σ𝑛𝑐), a função de transição de estados (Ó), a função de eventos ativos
(Γ), o estado inicial (𝑞0) e a profundidade de busca 𝑛, e a agenda de eventos inicial (𝑎0).
Como resultado, o algoritmo devolve a estrutura 𝑝𝑎𝑡ℎ que armazena o maior caminho en- tre o estado inicial (𝑞0, 𝑎0,0) e qualquer outro estado alcançado na busca, e o tempo total
𝑡𝑖𝑚𝑒. Além disso, neste algoritmo faz-se necessário que o agendador de eventos restrinja o número de ocorrências dos eventos controláveis, sendo que após o número máximo de ocorrências de um evento controlável à, temos 𝑎[à] = ∞.
Algoritmo 4: Calcula o caminho que minimiza o makespan no grafo acíclico de um
supervisor, utilizando uma heurística 1 𝑝𝑎𝑡ℎ[(𝑞, 𝑎, 0)] ⊂ 𝜖
2 𝑡𝑖𝑚𝑒[(𝑞, 𝑎, 0)] ⊂ 0
3
4 𝐹⊂ (𝑞0, 𝑎,0)
5
6 while𝐹 is not empty do
7 (𝑞, 𝑎, 𝑖) ⊂ 𝐹 8 if Γ(𝑞) ∩ Σc̸= ∅ AND ∀à ∈ Γ(𝑞) ∩ Σc, 𝑎[à] = 0 then 9 𝐸⊂ Γ(𝑞) ∩ Σc 10 else 11 𝑡min⊂ min σ∈Γ(q)∩Σu 𝑎[à] 12 𝐸⊂ Γ(𝑞) ∩ ¶àt: àt∈ Σ ∧ 𝑎[àt] ⊘ 𝑡min♢ 13 end 14 foreachevent à in 𝐸 do 15 𝑣⊂ Ó(𝑞, à) 16 𝑡⊂ 𝑎[à] 17 𝑎n⊂ 𝑢𝑝𝑑𝑎𝑡𝑒(𝑎, à) 18 if 𝑡= ∞ then continue 19
20 if 𝐹 does not contain (𝑣, 𝑎n, 𝑖+ 1) then
21 𝐹⊂ (𝑣, 𝑎n, 𝑖+ 1) 22 end 23 𝑡tot⊂ 𝑡𝑖𝑚𝑒[(𝑞, 𝑎, 𝑖)] + 𝑡 24 if (∄ 𝑡𝑖𝑚𝑒[(𝑣, 𝑎n, 𝑖+ 1)]) OR (𝑡tot< 𝑡𝑖𝑚𝑒[(𝑣, 𝑎n, 𝑖+ 1)]) then 25 𝑝𝑎𝑡ℎ[(𝑣, 𝑎n, 𝑖+ 1)] ⊂ 𝑝𝑎𝑡ℎ[(𝑞, 𝑎, 𝑖)]à 26 𝑡𝑖𝑚𝑒[(𝑣, 𝑎n, 𝑖+ 1)] ⊂ 𝑡tot 27 end 28 end 29 end
60 Capítulo 4. Busca pelo Menor Tempo
O algoritmo é inicializado com o caminho até o estado inicial como a sequência vazia (𝑝𝑎𝑡ℎ[(𝑞0, 𝑎0,0)] ⊂ 𝜖) e o tempo inicial como zero (𝑡𝑖𝑚𝑒[(𝑞0, 𝑎0,0)] ⊂ 0).
O estado inicial é inserido na Ąla 𝐹 (linha 4) e, enquanto a Ąla possui elementos, o primeiro estado é retirado da Ąla. A parte heurística do algoritmo está em considerar que eventos controláveis iniciam tarefas e que, no contexto de minimização do tempo, retardar o início de uma tarefa aguardando a ocorrência de um evento não controlável, em geral, não traz benefícios. Dessa forma, o algoritmo veriĄca se existem transições por eventos controláveis disponíveis e se todas elas não geram acréscimo de tempo (linha 8), ou seja, de o tempo total após a ocorrência do evento é igual ao tempo anterior à ocorrência do evento. Caso essas transições existam, o conjunto de eventos que serão avaliados (𝐸) é formado apenas pelos eventos relacionados a essas transições. Caso não existam transições por eventos controláveis, ou transições controláveis que afetam a contagem de tempo, o procedimento do algoritmo exato é utilizado. Determina-se qual o menor tempo para a ocorrência de um evento não controlável, armazenado em 𝑡𝑚𝑖𝑛 (linha 11) e, após isso, cada
transição que produza um acréscimo de tempo menor ou igual a 𝑡𝑚𝑖𝑛 é avaliada.
Para cada transição por um evento no conjunto 𝐸, calcula-se o acréscimo de tempo gerado pela transição, atualiza-se a agenda de eventos e veriĄca-se se a sequência resultante é temporalmente factível (linhas 15, 16 e 17). Caso o estado de destino ainda não tenha sido avaliado, ele é colocado na Ąla. O tempo total é avaliado como o tempo até o estado de origem, acrescido do intervalo de tempo da transição. Caso o estado de destino não esteja deĄnido em time, ou gere uma diminuição no tempo total, essa transição é usada para atualizar o caminho e o tempo total.
Assim como no algoritmo de menor tempo exato, o estado é representado como um estado do supervisor, uma agenda de eventos e um índice, porém a heurística reduz de maneira signiĄcativa o branching factor, de forma que o algoritmo seja rápido, mesmo com um algoritmo não polinomial.
Uma restrição quanto à ocorrência de eventos controláveis, apesar de poder ser uti- lizada em todos os algoritmos descritos anteriormente, se faz necessária neste caso para garantir que os eventos não controláveis sejam executados em algum momento, desabili- tando forçadamente certos eventos controláveis, garantindo assim que a heurística leve ao encontro de um estado marcado.
Exemplo 4.2.1. No exemplo da Pequena Fábrica, a aplicação da heurística utilizada no
algoritmo de Menor Caminho Heurístico pode ser visto na Figura13. Neste caso, além da transição entre o estado 𝑇 𝑇 𝑉 4 e 𝑃 𝑇 𝐶5 não precisar ser analisada, tabém não se analisa a transição entre o estado 𝑃 𝑇 𝑉 3 e 𝑃 𝑃 𝑉 4, resultando em uma diminuição signiĄcativa no espaço de busca, tornando a solução, neste caso, trivial, visto que resta apenas um caminho que leva ao estado marcado 𝑃 𝑃 𝑉 8. Essa heurística se justiĄca porque partimos do pressuposto que esperar 5 𝑢.𝑡. para que o evento 4 aconteça não é uma boa estratégia,
4.2. Menor Tempo Heurístico 61 visto que seria possível ligar 𝑀1 e manter ambas funcionando em paralelo.
Figura 13 Ű Grafo acíclico do supervisor da Pequena Fábrica com agendas de eventos asso- ciadas aos estados e duplicidade de estados e heuristica de poda, para uma profundidade de 8 eventos.
Neste caso, a única sequência resultante da execução do algoritmo de Menor Tempo Heurístico foi a seguinte:
𝑠1 = (1, 2, 3, 1, 4, 2, 3, 4)
A sequência 𝑠1 é a mesma sequência encontrada no Exemplo 3.2.2 e no Exem-
plo 4.1.1.
4.2.1 Vantagens e Desvantagens
O algoritmo de Menor Tempo Heurístico apresenta como vantagem uma redução signiĄcativa do tempo de execução do algoritmo de Menor Tempo Exato, gerando boas soluções. É importante notar, porém, que o algoritmo continua não polinomial, de forma que, dependendo da estrutura do supervisor e dos intervalos de tempo utilizados, a heurís- tica pode não ser muito signiĄcativa quanto à redução do tempo de execução. Além disso, o algoritmo necessita de restrições quanto ao número de vezes que cada evento controlável pode ocorrer, a Ąm de alcançar um estado marcado.
63
5 Testes e Análise de Resultados
Foram executados testes para três plantas utilizando os quatro algoritmos descritos no trabalho. Na análise serão considerados o tempo de execução do algoritmos, o tempo de execução da sequência e o paralelismo da sequência.