Um Algoritmo Híbrido GRASP-Simulated Annealing Aplicado à Programação de Máquinas Paralelas

Thaylo Xavier de Freitas

Um Algoritmo Híbrido GRASP-Simulated Annealing Aplicado à Programação de Máquinas Paralelas

Vitória - ES 2014

Thaylo Xavier de Freitas

Um Algoritmo Híbrido GRASP-Simulated Annealing Aplicado à Programação de Máquinas Paralelas

Monografia apresentada como Projeto de Graduação em Engenharia de Computação da Universidade Federal do Espírito Santo, como requisito parcial para obtenção do grau de Engenheiro de Computação.

Universidade Federal do Espírito Santo Departamento de Informática

Orientador: Profa. Dra. Maria Cristina Rangel

Vitória - ES 2014

Thaylo Xavier de Freitas Um Algoritmo Híbrido GRASP-Simulated Annealing Aplicado à Programação de Máquinas Paralelas/ Thaylo Xavier de Freitas. – Vitória - ES, 2014Orientador: Profa. Dra. Maria Cristina Rangel

Trabalho de Conclusão de Curso (Graduação) – Universidade Federal do Espírito Santo Departamento de Informática, 2014. 1. Meta-heurísticass. 2. Pesquisa Operacional. I. Maria Cristina Rangel. II. Universidade Federal do Espírito Santo. III. Departamenoto de Informática. IV. Meta-heurísticas em C++ Aplicadas à Programação de Máquinas Paralelas

Dedicado a todos que foram parte deste esforço, em especial a minha família, amigos, professores e colegas de faculdade.

Agradecimentos Agradeço aos meus pais, Edson e Ivanilda, pelo amor, cuidado e incentivo. À minha irmã Thayane pelo carinho e atenção. À minha orientadora Cristina pela ajuda e dedicação neste trabalho, e pelos ensinamentos passados. Aos demais professores que me capacitaram. Aos meus amigos do curso de Engenharia de Computação com os quais enfrentei situações desafiadoras e realizadoras. Aos meus amigos do PET Engenharia Elétrica (e agregados) pela camaradagem, momentos de descontração e troca de conhecimento. Também agradeço à Equipe de Robótica da UFES (ERUS) pelo apoio diário e pela oportunidade de trabalhar com pessoas incríveis. Aos alunos e tutores com os quais eu trabalhei no grupo PET da Engenharia de Computação, pelo aprendizado técnico e pela formação cidadã. Agradeço também aos petianos dos demais cursos da UFES pela oportunidade de compartilhar saberes e de construir uma universidade melhor. Aos meus colegas da APPI Tecnologia, pelos inúmeros ensinamentos e contribuições. À professora Maria Claudia Silva Boeres pela disponibilidade em participar da banca, de avaliar este trabalho e pelas oportunidades de aprender com ela durante várias etapas do curso. Ao professor Edmar Hell Kampke pela disponibilidade em participar da banca, pelo referencial teórico e pelas sugestões altamente construtivas. A todos os familiares e amigos que contribuíram durante a minha jornada na graduação e na vida pessoal.

Resumo A programação eficiente de tarefas em máquinas paralelas é um problema recorrente em sistemas com múltiplos servidores e em indústrias. Neste trabalho foi realizado um estudo do problema de programação de máquinas paralelas não relacionadas com tempos de preparação (setup times) dependentes de sequência e de recursos, ou seja, o tempo de preparação de cada máquina depende não somente da tarefa a ser executada mas também da tarefa anterior, juntamente com a quantidade de recursos escolhida para acelerar o setup time. As meta-heurísticas Simulated Annealing e GRASP foram aplicadas com o objetivo de alcançar um trade-off razoável entre tempo computacional e qualidade de soluções. Foi feita a comparação com as heurísticas e meta-heurísticas encontradas na literatura. Uma investigação da estrutura do problema foi realizada incluindo experimentações com métodos heurísticos adaptados. No método GRASP, os resultados obtidos utilizando Simulated Annealing na etapa de intensificação foram superiores em desempenho quando comparados ao hill climbing em instâncias grandes, sendo ainda melhores ao aplicar a técnica Path Relinking.

Abstract The efficient scheduling of tasks on parallel machines is a recurring problem in systems with multiple servers and industries. A study about the unrelated parallel machines scheduling problem with resources dependent setup times was performed. The preparation time of each machine depends not only on the task at hand but also the previous task, together with the chosen amount of resources to accelerate setup time. Two meta-heuristics, Simulated Annealing and GRASP, have been applied with the aim of achieve a reasonable trade-off between computational time and quality of solutions. An investigation of the structure of the problem was performed including trials with tailored heuristics. In the GRASP method, the results obtained using Simulated Annealing in the intensification phase were superior in performance when compared to hill climbing on large instances and even better when using Path Relinking.

Lista de ilustrações Figura 1 – Relação Linear entre Sijk e Rijk. . . . . . . . . . . . . . . . . . . . . Figura 2 – Níveis de utilização dos núcleos ao longo do tempo com quatro threads e com apenas uma. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figura 3 – Comparativo de qualidade de solução ao longo do tempo - Categoria Small com 2000 iterações . . . . . . . . . . . . . . . . . . . . . . . . Figura 4 – Comparativo de qualidade de solução ao longo do tempo - Categoria Small com 2000 iterações . . . . . . . . . . . . . . . . . . . . . . . . Figura 5 – Comparativo de qualidade de solução ao longo do tempo - Categoria Small com 2000 iterações . . . . . . . . . . . . . . . . . . . . . . . . Figura 6 – Comparativo de qualidade de solução ao longo do tempo - Categoria Small com 2000 iterações . . . . . . . . . . . . . . . . . . . . . . . . Figura 7 – Comparativo de qualidade de solução ao longo do tempo - Categoria Large com 2000 iterações . . . . . . . . . . . . . . . . . . . . . . . . . Figura 8 – Comparativo de qualidade de solução ao longo do tempo - Categoria Large com 2000 iterações . . . . . . . . . . . . . . . . . . . . . . . . . Figura 9 – Comparativo de qualidade de solução ao longo do tempo - Categoria Large com 2000 iterações . . . . . . . . . . . . . . . . . . . . . . . . . Figura 10 – Comparativo de qualidade de solução ao longo do tempo - Categoria Large com 2000 iterações . . . . . . . . . . . . . . . . . . . . . . . . .

. 17 . 34 . 36 . 37 . 38 . 39 . 42 . 43 . 44 . 45

Lista de tabelas Tabela 1 – Comparações iterações . . . Tabela 2 – Comparações iterações . . .

de Algumas Instâncias da Categoria Small . . . . . . . . . . . . . . . . . . . . . . . . . de Algumas Instâncias da Categoria Large . . . . . . . . . . . . . . . . . . . . . . . . .

com . . . com . . .

2000 . . . . 40 2000 . . . . 41

Sumário 1 1.1 1.2 1.3

INTRODUÇÃO . . . . . . . . Motivação . . . . . . . . . . . . Objetivos . . . . . . . . . . . . Organização deste documento

. . . .

. . . .

. . . .

. . . .

12 13 13 14

2 2.1 2.2 2.3 2.4 2.4.1 2.4.2 2.4.3 2.4.4 2.4.5 2.4.6 2.4.7 2.4.8 2.4.9 2.5 2.5.1 2.5.2 2.5.3

DEFINIÇÃO DO PROBLEMA . . . . . . . . . . . . . . . . . . Programação de tarefas em máquinas paralelas . . . . . . . . . Conceito de Setup Time . . . . . . . . . . . . . . . . . . . . . . Modelo matemático do problema . . . . . . . . . . . . . . . . . Exemplo Prático . . . . . . . . . . . . . . . . . . . . . . . . . . . Matriz de tempos de processamento Pij . . . . . . . . . . . . . . . . Conceito Geral das Matrizes de Tempos e de Recursos de Preparação Matriz de Tempos de Preparação mínimos Sij− . . . . . . . . . . . . . Matriz de Tempos de Preparação Máximos Sij+ . . . . . . . . . . . . − Matriz de Recursos de Preparação Mínimos Rij . . . . . . . . . . . . + Matriz de Recursos de Preparação Máximos Rij . . . . . . . . . . . . Representando uma Solução . . . . . . . . . . . . . . . . . . . . . . Avaliando uma Solução . . . . . . . . . . . . . . . . . . . . . . . . . Vizinhança de uma Solução . . . . . . . . . . . . . . . . . . . . . . Avaliando a Função Objetivo . . . . . . . . . . . . . . . . . . . . Processamentos na Primeira Máquina . . . . . . . . . . . . . . . . . Processamentos na Segunda e na Terceira Máquina . . . . . . . . . . Avaliação Total . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

15 15 16 17 18 19 20 20 21 22 22 23 24 24 24 24 25 25

3 3.1 3.2 3.2.1 3.2.2 3.2.3

. . . . . . .

. . . . . . .

. . . . . . .

26 26 27 27 29 29

3.2.3.1

MÉTODOS HEURÍSTICOS Métodos Construtivos . . . . Métodos Propostos . . . . . GRASP . . . . . . . . . . . . . Hill Climbing . . . . . . . . . . Simulated Annealing . . . . . . Path Relinking . . . . . . . . . .

4 4.1 4.2

DETALHES DE IMPLEMENTAÇÃO . . . . . . . . . . . . . . . . . 33 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Algoritmos e Desempenho . . . . . . . . . . . . . . . . . . . . . . . . 33

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

31

5 5.1 5.2

TESTES E RESULTADOS . . . . . . . . . . . . . . . . . . . . . . . 35 Condições de Teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Qualidade das Soluções e Tempos de conclusão . . . . . . . . . . . . 35

6

CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

"Com ordem e com tempo encontra-se o segredo de fazer tudo e tudo fazer bem." (Pitágoras)

12

1 Introdução A Pesquisa Operacional (PO) é uma área de conhecimento multidisciplinar altamente aplicável à gestão e à tomada de decisões, pode-se dizer que ela consiste em um conjunto de métodos científicos aplicados para melhorar o aproveitamento de recursos escassos. A PO se comporta como uma ferramenta auxiliar nos processos de tomada de decisões, de planejamento, e em quaisquer setores e níveis da economia, visando à maior satisfação dos usuários, definidos num determinado contexto. Dessa forma, a PO é uma área da Ciência da Computação que possui grande interseção com outras áreas do conhecimento humano. Com isso, nas últimas décadas observamos um grande impulso da PO na área de administração, com o apoio a tomada de decisões e também visando aumento da qualidade dos processos de produção e atendimento (KAMPKE, 2010).

Dentre as ferramentas da PO, pode-se citar a Otimização Combinatória, uma disciplina que trata de tomadas de decisões com o objetivo de maximizar (ou minimizar) uma função objetivo utilizando recursos e respeitando suas restrições quantitativas quando aplicadas a problemas discretos. A Otimização Combinatória pode ser aplicada à programação de máquinas paralelas, que merece destaque dada a sua relevância e grande aplicabilidade. Em um problema de programação de tarefas em máquinas paralelas (PTMP), existe um conjunto N = 1, 2, ... , n de tarefas onde cada tarefa deve ser processada necessariamente em uma das máquinas do conjunto M = 1, 2, ... , m. As tarefas são distribuídas entre as máquinas e, em cada máquina, uma sequência de execução de tarefas deve ser determinada. No caso mais geral do problema de programação de máquinas paralelas, elas são ditas “não relacionadas” (RUIZ; ANDRÉS, 2007). Neste cenário, o tempo de processamento de cada tarefa em cada máquina é determinístico e previamente conhecido, sendo denotado por pij , i ∈ M, j ∈ N. Neste estudo foi considerada uma variante deste problema na qual existe um tempo de preparação, ou setup time, durante a transição entre tarefas, denotado por Sijk , que representa o tempo de preparação necessário para que a máquina i alterne entre a tarefa j e a tarefa k caso a transição ocorra. Este tempo é determinístico e é conhecido de antemão. Ao PTMP que considera o tempo de preparação entre tarefas sensível aos recursos alocados, dá-se o nome de problema de programação de tarefas em máquinas paralelas com setup times dependentes de sequência e de recursos ou abreviadamente PPTMPSR (KAMPKE, 2010).

Capítulo 1. Introdução

13

1.1 Motivação Sistemas de atendimento com múltiplos pontos de serviço estão presentes em quase todos lugares com várias modalidades. Podemos encontrar analogias em sistemas operacionais, filas de supermercados, atendimento de pacientes em hospitais e fábricas com múltiplas máquinas e em quaisquer situações onde múltiplas instâncias de um recurso limitado atendem a várias requisições. Infelizmente, alguns destes exemplos são, também, exemplos práticos de sistemas ineficientes, com grande tempo de espera, baixa qualidade de serviço e altos custos de manutenção. Embora as requisições de serviço possam atingir picos esporádicos, a infraestrutura de atendimento precisa ser planejada, expandida e mantida de alguma forma. Neste contexto, o escalonamento adequado da ordem de atendimentos em cada ponto de atendimento (ou máquina) pode aumentar o desempenho de uma planta já construída sem que seja obrigatória a sua expansão. O aumento do desempenho é vantajoso e desejado em inúmeras situações, sendo possível cogitar repercussões na qualidade de serviços públicos, no desempenho de sistemas computacionais e no retorno financeiro de empresas. Assim, a programação de tarefas em máquinas paralelas é assunto altamente relevante justificando estudos aprofundados do problema e de técnicas que permitam atingir melhores resultados. Entre as técnicas usadas na abordagem deste problema, as heurísticas se mostram apropriadas dada a sua capacidade de encontrar boas soluções em problemas altamente combinatoriais, como será detalhado adiante.

1.2 Objetivos Este trabalho tem como objetivos estudar o problema de programação de tarefas em máquinas paralelas com setup times dependentes de sequência e de recursos (PPTMPSR), a implementação de métodos heurísticos baseados no GRASP, Greedy Randomized Adaptive Search Procedure (FEO; RESENDE, 1989), e no Simulated Annealing (OSMAN; POTTS, 1989) juntamente com a técnica de reconexão de caminhos, também denominada path relinking, (GLOVER; LAGUNA; MARTÍ, 2000) e a análise de desempenho dos algoritmos tendo como métrica a soma ponderada dos tempos de conclusão com o total de recursos utilizados. O objetivos específicos são: • Estudo das instâncias com o objetivo de melhor direcionar o projeto dos algoritmos; • Implementar uma heurística construtiva que obtenha uma boa solução inicial; • Aplicar as meta-heurísticas GRASP e Simulated Annealing em um algoritmo híbrido; • Verificar mudanças de desempenho dos algoritmos com a inserção da técnica path relinking. • Verificar a aplicabilidade de métodos heurísticos na solução de problemas reais.

Capítulo 1. Introdução

14

1.3 Organização deste documento No capítulo 2, após a definição do problema, é feita uma revisão da literatura, onde apresenta-se o conceito de setup time, o modelo matemático e um exemplo prático.

No capítulo 3 são apresentados os métodos construtivos e em seguida, são apresentados os métodos propostos que visam aprimorar soluções de forma iterativa partindo de uma solução inicialmente construída.

No capítulo 4 são mostrados os detalhes de implementação das rotinas na linguagem C++, bem como as estruturas de dados e algoritmos utilizados.

No capítulo 5 são apresentados os resultados dos testes computacionais detalhadamente por meta-heurística, bem como as comparações entre os resultados.

No capítulo 6, as conclusões são apresentadas, além de algumas propostas para trabalhos futuros.

15

2 Definição do Problema O problema de programação de tarefas em máquinas paralelas (PTMP) pode ser definido, sucintamente, como o problema de determinar a melhor ordem de atendimento (ou execução) de um conjunto de tarefas em um conjunto de máquinas considerando os tempos de execução de cada tarefa em cada máquina de forma a minimizar algum critério de avaliação: soma dos tempos de espera, throughput, tempo total de execução, etc. A programação ou sequenciamento de tarefas em máquinas paralelas tem sido objeto de análise em muitos estudos. Sua relevância na eficiência da produção tem chamado a atenção de empresas já que o ambiente de negócios é um setor altamente competitivo. ALLAHVERDI et al. (2008) realizaram um levantamento constatando que nas últimas décadas, o estudo do problema PTMP tem aumentado consideravelmente. Sua recorrência foi comprovada em modalidades diversificadas, de audiências judiciais à fabricação de chips. No trabalho de RUIZ e ANDRÉS (2007) foi aplicada programação inteira mista (MIP ou Mixed Integer Programming) na resolução de instâncias pequenas. As instâncias foram classificadas em duas categorias. Instâncias com até 10 tarefas são consideradas como pertencentes ao grupo small e as demais são classificadas como large. Não se conhece um algoritmo de complexidade polinomial que obtenha a melhor programação possível, já que o PTMP é NP-difícil como demonstrado por RUIZ e ANDRÉS (2007), o que torna difícil obter a solução ótima, embora seja possível obter boas soluções. Neste trabalho foram aplicados métodos heurísticos nas instâncias classificadas como grandes. KAMPKE (2010) apresenta resultados aplicando as meta-heurísticas GRASP e ILS, confirmando a viabilidade do uso de métodos heurísticos nesta classe de problema.

2.1 Programação de tarefas em máquinas paralelas Em um problema de programação de tarefas em máquinas paralelas (PTMP), existe um conjunto N = 1, 2, ... , n de tarefas onde cada tarefa deve ser processada necessariamente em uma das máquinas do conjunto M = 1, 2, ... , m. As tarefas são distribuídas entre as máquinas e, em cada máquina, uma sequência de execução de tarefas deve ser determinada. O tempo de processamento da tarefa j na máquina i é determinístico e previamente conhecido, sendo denotado por pij , i ∈ M, j ∈ N. Existe um tempo de preparação, ou setup time, durante a transição entre tarefas, denotado por Sijk , que representa o tempo de preparação necessário para que a máquina i alterne entre a tarefa j e a tarefa k caso a transição ocorra. A quantidade de recursos consumidos na fase

Capítulo 2. Definição do Problema

16

de preparação da máquina i entre a tarefa j e a tarefa k, caso esta transição ocorra, é denotada por Rijk . A métrica utilizada para comparar diferentes soluções neste trabalho, entre outras propostas por CHENG e SIN (1990), é uma combinação linear da soma dos tempos de finalização das tarefas com a soma dos recursos gastos durante os setup times. A formulação do problema é apresentada na seção 2.3.

2.2 Conceito de Setup Time Quando uma máquina termina a execução de uma tarefa, são necessários procedimentos de preparação antes que a próxima tarefa seja assumida. Os procedimentos podem incluir, por exemplo, a verificação de danos, reabastecimento, resfriamento, troca de componentes, troca de pessoal, etc. O tempo de duração desta preparação é denominado setup time. É possível aumentar ou diminuir o tempo de preparação comprometendo menos ou mais recursos no processo. Os recursos gastos nesta fase de preparação da máquina podem ser medidos em valores monetários ou em força de trabalho (homem-hora) e independente da modalidade, existem limites superiores e inferiores para esse valores em cada transição de cada máquina. Por exemplo, na troca de pneus e reabastecimento de carros de corrida da Fórmula 1, existe um número máximo de técnicos que podem trabalhar ao mesmo tempo dada a limitação de espaço físico em volta do carro, por outro lado, não é usual fazer troca de pneus com menos de dois mecânicos. Os valores máximos e mínimos para tempo de preparação e recursos são denotados, − − + + respectivamente, por Sijk , Sijk ,Rijk e Rijk . RUIZ e ANDRÉS (2007) fizeram uma extensa revisão da literatura relacionada aos problemas onde o setup time está relacionado aos recursos. Encontraram trabalhos onde os tempos de processamento pij podem ser controlados com o uso de recursos. Esta possibilidade foi explorada por ZHANG, TANG e CHEN (2001), com o objetivo de minimizar, em máquinas paralelas não relacionadas, a soma ponderada dos tempos de conclusão somada aos custos de aceleração associados a cada tarefa. A relação entre Sijk e Rijk depende de cada situação, sendo frequentemente inversamente proporcional. Neste trabalho foi adotada a mesma relação apresentada em KAMPKE (2010) que é a interpolação interpolação linear onde um tempo de preparação − + de Sijk unidades corresponde à alocação de Rijk unidades de recurso, enquanto o tempo de − + preparação de Sijk unidades corresponde à alocação de Rijk unidades de recurso. Assim:

Sijk =

+ Sijk

− + Sijk − Sijk − − + − (Rijk − Rijk ) Rijk − Rijk

(2.1)

Como em cada transição, os valores máximos e mínimos de tempos e de recursos

Capítulo 2. Definição do Problema

17

Figura 1 – Relação Linear entre Sijk e Rijk. − + + são conhecidos, pode-se estabelecer coeficientes K1 e K2 em função de Sijk , Sijk ,Rijk e − Rijk de tal forma que:

Sijk = K1 − K2 Rijk

(2.2)

2.3 Modelo matemático do problema A soma dos tempos de conclusão de todas as tarefas é denominado flow time. Seja Cj o tempo transcorrido até a conclusão da tarefa j, então o flow time pode ser calculado como:

C=

n X

(2.3)

Cj

j=1

Para minimizar a expressão 2.3, o gasto de recursos nas fases de preparação foi maximizado, contudo, não basta minimizar o flow time. Como a minimização do total de recursos consumidos também é importante, eles devem ser considerados no modelo matemático. Desta forma, a equação 2.4 descreve a contribuição dos recursos.

Trec =

m X n X

n X

Rijk

(2.4)

i=1 j=1 k=1,k6=j

Por fim, para compor a função objetivo, similarmente a KAMPKE (2010), foi considerada uma combinação linear (dados α e β números reais estritamente positivos) do

Capítulo 2. Definição do Problema

18

flow time C com o total de recursos alocados nas etapas de preparação Trec . De acordo a expressão:

Z = αTrec + βC

(2.5)

Podemos detalhar a equação 2.5 da seguinte forma: Z=α

m X n X

n X

i=1 j=1 k=1,k6=j

Rijk + β

m X n X

Cij

(2.6)

i=1 j=1

Onde m e n são, respectivamente, o número de máquinas e o número de tarefas. Um conjunto completo de restrições foi apresentado por RUIZ e ANDRÉS (2007) ao aplicarem programação inteira mista na resolução de algumas instâncias. Tais restrições estabelecem que o tempo de execução de cada tarefa é positivo, o recurso atribuído a cada − + etapa e preparação é um valor inteiro limitado por Rijk e Rijk , cada tarefa tem exatamente uma antecessora (através da criação de uma tarefa fictícia no início de cada lista), cada tarefa tem no máximo uma sucessora e, por fim, antecessoras e sucessoras de uma tarefa são, por definição, alocadas na mesma máquina desta tarefa. A partir destas definições, os dados de entrada do problema são: o número de tarefas n, o número de máquinas m, a matriz dos tempos de processamento Pm× n , a matriz dos tempos de preparação máximos + − + − Sm e mínimos Sm , recursos máximos Rm e mínimos Rm . Estas quatro × n× n × n× n × n× n × n× n matrizes possuem diagonal nula, ou seja, não existe transição entre uma tarefa i e ela mesma, pois as tarefas não se repetem na mesma máquina.

2.4 Exemplo Prático KAMPKE (2010) exemplifica o PPTMPSR associado a problemas de algumas indústrias em atividades como o polimento de cerâmicas e a produção em gráficas. No caso das gráficas, um conjunto de impressoras atende a uma determinada demanda de impressões, sendo cada máquina mais eficiente utilizando um determinado tipo de papel, tendo também diferentes tempos de limpeza entre as impressões. Tal situação ocorre devido as diferenças de desempenho entre cada modelo (para cada modalidade de papel) e dada a necessidade de limpar e de adaptar as configurações de cada equipamento para cada nova tarefa. Nas etapas de preparação é possível fazer a alocação de recursos (funcionários, matérias-primas, energia, etc.) com o objetivo de reduzir o setup time. Para ilustrar um exemplo do problema, abaixo são apresentados os dados de entrada de um problema com n = 6 tarefas e m = 3 máquinas de uma instância gerada por RUIZ e ANDRÉS (2007).

Capítulo 2. Definição do Problema

19

2.4.1 Matriz de tempos de processamento Pij No início do arquivo da instância são informados quatro valores: o número de tarefas, o número de máquinas e dois valores numéricos que neste trabalho serão desconsiderados. Tais valores são sucedidos por n linhas contendo cada uma m pares de valores, onde o primeiro representa a máquina (um índice i variando de 0 a m − 1) e o segundo representa o tempo P ij da tarefa i na máquina j. Cada tarefa tem seus tempos de processamento completamente armazenados em exatamente uma linha:

Capítulo 2. Definição do Problema

6 3 0 0 0 0 0 0

3

20

1

1 1 4 2 87 21 1 28 2 68 32 1 17 2 38 43 1 9 2 48 8 1 85 2 6 30 1 92 2 37

Ao interpretar estes dados, será armazenada uma matriz P6× 3 contendo os seguintes valores: 

P6,3

1   21   32 =  43   8  30

4 28 17 9 85 92



87  68   38   48   6  37

2.4.2 Conceito Geral das Matrizes de Tempos e de Recursos de Preparação Todas as transições entre tarefas (para cada máquina) irão consumir tempo e recursos. Tais quantidades são descritas por matrizes que indicam de forma determinística custo e tempo de preparação para realizar uma tarefa, sendo conhecida a tarefa anterior e o índice da máquina onde ocorrerá a transição. Vale ressaltar que a diagonal principal das matrizes contém valores nulos já que para o PPTMPSR abordado, cada tarefa é executada apenas uma vez, não existindo transição dela para ela mesma.

2.4.3 Matriz de Tempos de Preparação mínimos Sij− Esta seção do arquivo de instância é iniciada com a expressão “RSSDMIN”, seguida de m subseções, cada uma contendo a matriz de setup times mínimos da máquina j variando de M0 até Mm−1 . Para esta instância, todas as matrizes tem dimensão M6x6 já que existem 6 tarefas: RSSDMIN M0 0 3 1 3 1 0 1 1 3 1 0 2 1 3 3 0 3 1 1 1

3 2 1 2 0

3 1 3 3 2

Capítulo 2. Definição do Problema

1 2 M1 0 3 2 0 3 1 3 2 2 1 3 1 M2 0 2 2 0 2 3 1 2 2 3 1 1

21

1 3 2 0 3 3 0 2 3 1

2 2 1 0 3 3

1 3 3 3 0 3

3 1 2 3 3 0

3 1 0 2 3 3

3 3 1 0 1 3

1 1 1 1 0 2

1 1 1 1 1 0

2.4.4 Matriz de Tempos de Preparação Máximos Sij+ Após os tempos mínimos, o arquivo de instância descreve os tempos de preparação máximos utilizando mesma lógica de endereçamento dos tempos de preparação mínimos. Porém, a expressão utilizada para demarcar este novo contexto é “RSSDMAX”, como segue: RSSDMAX M0 0 4 4 5 5 0 5 3 3 3 0 5 3 4 5 0 4 5 5 3 3 5 5 4 M1 0 4 4 4 3 0 4 4 4 5 0 3 5 5 3 0 4 4 3 3 4 3 5 3 M2 0 3 5 4

4 3 3 3 0 5

4 3 4 3 4 0

5 3 5 5 0 3

5 3 5 5 5 0

5 3

Capítulo 2. Definição do Problema

5 3 4 5 3

0 4 3 4 5

3 0 5 3 4

3 5 0 5 3

5 4 5 0 4

22

4 4 3 4 0

− 2.4.5 Matriz de Recursos de Preparação Mínimos Rij

O marcador desta seção é “SSDMIN”, a lógica de endereçamento é análoga às matrizes anteriores. Como segue: SSDMIN M0 0 47 28 17 23 12 10 0 35 50 32 35 28 5 0 38 8 12 45 36 22 0 50 8 2 10 1 19 0 20 19 5 23 26 24 0 M1 0 34 41 29 13 19 30 0 44 31 13 35 28 44 0 19 19 32 40 23 11 0 35 42 38 46 10 39 0 14 15 36 23 49 10 0 M2 0 1 12 45 17 44 39 0 49 14 20 42 2 13 0 3 26 22 1 8 36 0 16 20 28 14 8 15 0 4 36 17 40 33 29 0 + 2.4.6 Matriz de Recursos de Preparação Máximos Rij

O marcador desta seção é “SSDMAX”, a lógica de endereçamento é análoga às matrizes anteriores. Como segue: SSDMAX

Capítulo 2. Definição do Problema

23

M0 0 95 51 63 95 84 51 0 58 57 71 71 28 57 0 50 77 88 79 61 93 0 53 8 74 53 68 83 0 60 90 76 71 52 100 0 M1 0 58 52 53 55 90 98 0 55 60 13 88 99 75 0 51 80 90 97 76 83 0 100 89 86 95 10 39 0 100 87 89 50 49 10 0 M2 0 68 66 53 89 63 93 0 96 14 52 95 97 74 0 85 69 71 88 85 67 0 82 76 99 55 8 100 0 51 81 68 76 33 82 0

2.4.7 Representando uma Solução Uma solução é representada por uma tupla de elementos separados por um valor especial que neste trabalho é -1. A tupla SolucaoExemplo = {1, 0, −1, 2, 3, −1, 4, 5} é uma representação válida para uma solução, significando a execução das tarefas 1 e 0 (nesta ordem) na primeira máquina, paralelamente à execução das tarefas 2 e 3 na segunda máquina restando as tarefas 4 e 5 para a terceira máquina. Porém, é necessário descrever a quantidade de recursos consumidos em cada etapa de transição de tarefas de cada máquina. A representação completa da solução é SolucaoExemplo = {1/0, 0/1, −1, 2/0, 3/1, −1, 4/0, 5/1}, onde cada índice de tarefa é acompanhado pela quantidade de recursos investidos na preparação da mesma (valores separados por barras). Neste contexto, o símbolo “/” cumpre apenas o papel de separação entre índice de tarefa e recurso atribuído na fase de preparação que acontece antes da mesma. A notação de índices das soluções segue o padrão da linguagem de programação C e por isso, índices 0 devem ser interpretados como o índice da primeira tarefa. Para os custos de preparação prevalece o valor literal.

Capítulo 2. Definição do Problema

24

2.4.8 Avaliando uma Solução Vários algoritmos podem ser propostos para encontrar escalonamentos em máquinas paralelas. Devido à elevada complexidade combinatorial, soluções ótimas são conhecidas apenas para instâncias pequenas do problema. Ao calcular uma solução será importante fazer avaliações via função de custo Como a data de término de cada tarefa é considerada para avaliar a função de custo, o procedimento de avaliar a solução apresentada anteriormente, por exemplo, consiste em computar o tempo de execução da tarefa 1 na máquina 0. Armazenar este resultado e então calcular o tempo de preparação entre as tarefas 1 e 0 na máquina 0. Este tempo é sensível à quantidade de recursos gasta, no caso 1, e por fim, soma-se a este tempo o processamento da tarefa 0 propriamente dita. O tempo final, ou data de término, de cada tarefa será contabilizado para compor a parcela de tempo da função objetivo. Juntamente com este, o total de recursos gastos será contabilizado, multiplicado por uma constante e então somado aos tempos, conforme apresentado anteriormente na equação 2.5.

2.4.9 Vizinhança de uma Solução A estrutura de vizinhança adotada neste trabalho foi do tipo Nr , em uma notação proposta por KAMPKE (2010). Uma reinserção de uma tarefa em uma nova posição (ou em qualquer posição de outra máquina) irá gerar uma solução vizinha à original.

2.5 Avaliando a Função Objetivo Para exemplificar, será computada a avaliação a solução exemplo: S = {1/0, 0/1, −1, 2/0, 3/1, −1, 4/0, 5/1} Por meio da expressão:

Z = αTrec + βC

(2.5)

2.5.1 Processamentos na Primeira Máquina Esta máquina tem índice 0. O primeiro elemento da solução é 1/0. Isto significa que a tarefa de índice 1 será executada com custo de preparação e setup time iguais a 0. O custo e o tempo de preparação da máquina é zero pois ainda não foi executada tarefa alguma e este custo só está definido em transições de tarefas. A coluna da matriz pm×n que contém os tempos de execução da primeira máquina é a coluna 1. A linha da matriz pm×n que contém os tempos de execução da tarefa de índice 1 nas diferentes máquinas é a

Capítulo 2. Definição do Problema

25

linha 2. Consultando os valores fornecidos na subseção 2.4.1 temos p1,2 = 21. A tarefa de índice 1 estará concluída após 21 unidades de tempo contando a partir do início de todos processamentos, logo: C1 = 21 é seu tempo de conclusão. Em seguida, a máquina deve ser preparada antes de executar a próxima tarefa. O próximo elemento da solução é 0/1. Isto significa que a tarefa de índice 0 é a próxima a ser executada com custo de preparação igual a 1. O setup time pode ser obtido acessando os valores das matrizes de tempos e recursos e aplicando-os à equação 2.2, assim: S0,1,0 = 51. A partir deste momento, a máquina inicia o processamento da tarefa sua segunda tarefa, cujo índice é 0. A coluna da matriz pm×n que contém os tempos de execução da primeira máquina é a coluna 1. A linha da matriz pm×n que contém os tempos de execução da tarefa de índice 0 nas diferentes máquinas é a linha 1. Consultando os valores fornecidos na subseção 2.4.1 temos p1,1 = 1. A tarefa de índice 0 estará concluída após C0 unidades de tempo onde C0 = C1 + S1,1,0 + p1,1 = 21 + 51 + 1 = 73 unidades de tempo contando a partir do início de todos processamentos, logo: C0 = 73 é seu tempo de conclusão. O próximo elemento da solução é −1, indicando que a primeira máquina não processará mais tarefas. O total de recursos consumidos em preparação na máquina de índice 0 foi T0 = 1 unidade.

2.5.2 Processamentos na Segunda e na Terceira Máquina Seguindo o mesmo raciocínio, C2 = 17 e C3 = 17 + 51 + 9 = 77. O total de recursos consumidos em preparação na máquina de índice 0 foi T1 = 1 unidade. Prosseguindo, C4 = 6 e C5 = 6 + 51 + 37 = 94. O total de recursos consumidos em preparação na máquina de índice 0 foi T2 = 1 unidade.

2.5.3 Avaliação Total Aplicando-se a equação:

Z = αTrec + βC

(2.5)

Z = α(1 + 1 + 1) + β(21 + 73 + 17 + 77 + 6 + 94)

(2.7)

Obtém-se:

Adotando os valores 50.0 e 1.0 para α e β respectivamente, pode-se concluir:

Z = 50.0 × (1 + 1 + 1) + 1 × (21 + 73 + 17 + 77 + 6 + 94) = 438

(2.8)

26

3 Métodos Heurísticos A abordagem de problemas combinatoriais requer métodos capazes de explorar o espaço de busca de forma direcionada e eficiente. Como não existe algoritmo de complexidade polinomial capaz de encontrar a solução ótima para o problema PPTMPSR (RUIZ; ANDRÉS, 2007), as heurísticas representam um vasto campo de alternativas altamente relevantes do ponto de vista prático, já que encontrar a solução ótima para um problema combinatorial de forma exata é inviável para instâncias grandes. A alternativa de métodos heurísticos é capaz de encontrar soluções viáveis de boa qualidade (ou mesmo a solução ótima) com esforço computacional aceitável. Uma situação interessante pode ser observada no crescimento rápido da função fatorial onde a representação de valores inteiros em 32 bits não acomoda o valor do fatorial de 13. Similarmente, o crescimento do espaço de buscas em problemas combinatoriais torna métodos de força bruta inviáveis.

3.1 Métodos Construtivos Os métodos heurísticos construtivos abordam os problemas de forma incremental (frequentemente gulosa), ou seja, a partir de uma solução inicial vazia, novos elementos podem ser adicionados criteriosamente de forma a convergir para uma solução final válida e de boa qualidade. Em RUIZ e ANDRÉS (2007) e KAMPKE (2010) destacou-se uma heurística de alocação dinâmica e incremental de tarefas, desta forma, a heurística Dynamic Job Assignment with Setups resource Assignment, doravante DJASA, foi implementada para servir como referência ao analisar os resultados dos métodos propostos. Para construir a solução via Djasa, uma lista de tarefas pendentes é criada, contendo todas as tarefas da instância. Para cada tarefa da lista, calcula-se o incremento da função objetivo ao escalonar esta tarefa na máquina que causará o menor incremento. Esta tarefa sai da lista e o processo continua até o fim da lista. 1 2 3 4 5 6 7 8

Procedimento DJASA Parametros : Jobs Solucao = { vazio } JobsPendentes = {1 , 2 , 3 , ... , n } Enquanto JobsPendentes != { vazio } Para cada Job j em JobsPendentes Para cada maquina i Atribua temporariamente recursos de setup para escalonar j em i

Capítulo 3. Métodos Heurísticos

9 10 11 12 13

14 15 16

27

Escalone j em i de Solucao Reavalie a Solucao e armazene o valor da funcao objetivo Fim - Para Fim - Para Escalone em Solucao a tarefa k que acarreta o menor aumento na funcao objetivo JobsPendentes = JobsPendentes - { k } Fim - Enquanto Retorne Solucao

Pseudocódigo 3.1 – Pseudocódigo Djasa Existem diferentes abordagens para determinar a quantidade de recursos alocados em cada fase de setup. De fato, a escolha dos recursos impacta os resultados de tarefas pendentes. Por outro lado, até que todas as tarefas tenham sido alocadas, não é possível escolher a melhor quantidade de recursos que cada máquina deve usar a fim de acelerar (ou não) a transição entre duas tarefas. Desta forma, uma decisão deve ser tomada no sentido de definir os recursos para que o algoritmo siga até o fim construindo uma solução válida. Em RUIZ e ANDRÉS (2007) foram propostas três opções: setup times utilizando recursos mínimos, máximos e médios. Apenas ao final é feita a alocação otimizada de recursos, cujo método é exposto no pseudocódigo 3.4. Uma das desvantagens deste procedimento, é que uma inserção de incremento mínimo não garante que a tarefa foi inserida na melhor posição possível, já que o setup time entre ela e as próximas tarefas candidatas pode impactar severamente a função objetivo na próxima iteração.

3.2 Métodos Propostos 3.2.1 GRASP O método GRASP ou Greedy Randomized Adaptive Search Procedure, é um algoritmo aplicável a problemas de otimização combinatória. Proposto por FEO e RESENDE (1989) para abordar problemas de set covering, consiste em um procedimento de duas fases que acontecem ao longo de n repetições, onde n é um parâmetro da meta-heurística. Na primeira fase é gerada uma solução de forma probabilística, gulosa e adaptativa para que na segunda fase, seja feita uma intensificação por meio de uma busca local. Na fase construtiva, similarmente à meta-heurística DJASA, uma lista de tarefas pendentes é criada, e a partir dela são selecionadas tarefas para compor a nova solução. Para explorar melhor o espaço de buscas evitando mínimos locais, o GRASP não escalona a tarefa de menor incremento da função objetivo. Na primeira fase da meta-heurística GRASP, a partir de uma solução vazia, são derivadas n outras soluções (onde n é a quantidade de possíveis

Capítulo 3. Métodos Heurísticos

28

inserções de tarefas pendentes na solução atual). Estas possíveis inserções são ordenadas e então são feitos sorteios sucessivos sempre entre as α% mais promissoras para decidir qual inserção será executada. Note que α = 100% permite construir uma solução completamente aleatória, enquanto α −→ 0% é uma proposta gulosa porém torna a fase de construção pouco exploratória apesar da soluções geradas serem de boa qualidade. No contexto da meta-heurística GRASP, α é denominado parâmetro de aleatoriedade. Na segunda fase do GRASP, é feita uma busca local a fim de intensificar a solução. Neste trabalho foram feitas duas modalidades de intensificação: Hill Climbing e Simulated Annealing. A seguir o pseudocódigo da meta-heurística GRASP: 1 2 3 4 5 6 7 8 9 10 11 12

Procedimento GRASP Argumentos : Instancia , alfa_aleatoriedade , max_iter Zmin = inf Para contador i variando de 1 a max_iter S = co ns tr uc ao _s ol uc ao ( instancia , a lf a_ al ea to rie da de ) ; S = busca_local ( S ) ; Se ( avaliacao ( S ) < Zmin ) Melhor = S Zmin = avaliacao ( S ) Fim - Se Fim - Para Retorne Melhor

Pseudocódigo 3.2 – Pseudocódigo GRASP

1 2 3 4 5 6 7 8 9 10

11 12 13 14

Procedimento CONSTRUCAO SOLUCAO Argumentos : Instancia , A lf a_ al ea to ri eda de Sequencia = { vazio } Vetor Lista DeCand idatos = {1 , 2 , 3 , ... , n } Enquanto # t ar ef as Es ca lon ad as < # totalDeTarefas Para cada Job j em Li staDeC andid atos Avalie e marque em j o seu custo de escalonamento minimo Fim - Para Ordene Li staDeC andid atos segundo os custos de escalonamento Sorteie um Job J entre os al fa _a le at or ie da de % Jobs mais promissores Otimize os recursos de setup no Job J Escalone J em Sequencia Retire J de Li staDe Candid atos Fim - Enquanto

Pseudocódigo 3.3 – Pseudocódigo Construcao Solucao GRASP Cada unidade de recurso adicionalmente consumida na etapa de preparação entre duas tarefas vai reduzir a data de conclusão de todas as tarefas seguintes da mesma

Capítulo 3. Métodos Heurísticos

29

máquina, consequentemente reduzindo a parcela de tempo da função objetivo. Por outro lado, isso vai aumentar a parcela dos recursos gastos. Existe um critério que permite definir em que situações é vantajoso investir recursos para reduzir o setup time. No contexto de otimização de recursos, α e β denotam valores reais (positivos) de ponderação no cálculo da função objetivo expressa pela equação 2.5. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Procedimento OTIMIZAR RECURSOS Argumentos : Instancia , Solucao Para cada maquina Para cada tarefa na maquina Se RijkMax == RijkMin Recursos atribuidos = RijkMin Senao h = quantidade de tarefas subsequentes K2 = ( SijkMax - SijkMin ) /( RijkMax - RijkMin ) Se K2 * h * beta < alfa Recursos atribuidos = RijkMax Senao Recursos atribuidos = RijkMin Fim - Se Fim - Se Fim - Para Fim - Para

Pseudocódigo 3.4 – Pseudocódigo Otimização de Recursos A busca local do GRASP pode ser realizada de várias formas. Quando ela é feita via Simulated Annealing, neste trabalho, o GRASP será denominado como GRASP SA. Quando, além do Simulated Annealing, for utilizada a técnica de reconexão de caminhos, a terminologia será GRASP PRSA. Para o GRASP com Hill Climbing será usado o termo GRASP HC.

3.2.2 Hill Climbing O método de busca local Hill Climbing implementado neste trabalho baseia-se na noção de que pequenas modificações podem ser feitas em uma solução a fim de compor e explorar uma vizinhança de soluções. Destas, apenas a mais promissora é selecionada para novamente realizar a busca local até que não seja encontrada melhoria de qualidade na solução.

3.2.3 Simulated Annealing A meta-heurística simulated annealing (SA) é uma técnica de busca local aplicável a problemas de otimização. Uma das principais características do SA é o seu caráter

Capítulo 3. Métodos Heurísticos

30

probabilístico condicionado a um fator de temperatura. A partir de uma solução inicial qualquer, buscas sucessivas na vizinhança da solução atual são feitas, aceitando soluções de melhor avaliação e aceitando (probabilisticamente) soluções de pior avaliação. Existem dois fatores que regem a probabilidade, a magnitude da piora de avaliação e a temperatura atual do sistema. A temperatura é uma abstração que simboliza o grau de agitação, e portanto, de instabilidade do sistema. Desta forma, o sistema inicia com uma temperatura T0 elevada e esta é atenuada a cada iteração do algoritmo por um fator de arrefecimento α tal que 0 < α < 1. Soluções melhores sempre são aceitas, mas soluções piores tem uma probabilidade de aceitação p = exp(−(f (Si) − f (S))/T ), onde Si é a solução candidata da iteração i, S é a solução corrente, f é a função de avaliação. Nota-se que a expressão adotada para a probabilidade implica em uma menor chance de aceitação para soluções muito ruins sendo tal chance reduzida também com o passar do tempo, tornando o algoritmo menos exploratório. A seguir o pseudocódigo: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

Procedimento SIMULATED ANNEALING Parametros : max_success_per_iter , T0 , Tf , max_per_per_iter e alfa_arref Cria e inicializa solucao S Cria solucao de iteracao Si T = T0 ; Tf = 1e -9; // Dada uma temperatura final conhecida , o // numero maximo de iteracoes fica determinado . max_iter = log ( Tf / T0 ) / log ( alfa_arref ) ; Inicializa nSuccess = 1; Criar contadores i e j nulos Loop Externo Resetar iterador i = 0; Resetar contador nSuccess = 0; Loop Interno Si = perturba ( S ) DeltaFi = avaliacao ( Si ) - avaliacao ( S ) p = exp ( - DeltaFi / T ) ; Se ( DeltaFi < 0.0 || aux >= random_t () ) Aceita - se S = Si ; Incrementar nSuccess ++; Fim - Se i ++; Se ( nSuccess >= m a x _ s u c c e s s _ p e r _ i t e r || i > max_per_per_iter ) Parar Loop interno Fim - Se Fim - Loop Arrefecer T = alfa_arref * T ; Incrementar j ++; Se ( nSuccess == 0 || j >= max_iter ) Parar Loop Externo

Capítulo 3. Métodos Heurísticos

32 33 34

31

Fim - Se Fim - Loop Externo Retorne s ;

Pseudocódigo 3.5 – Pseudocódigo Simulated Annealing

3.2.3.1 Path Relinking Uma proposta para enriquecer a busca por soluções de qualidade, é a reconexão de caminhos (GLOVER; LAGUNA; MARTÍ, 2000). Esta técnica consiste em percorrer (por meio de permutações) o “caminho” que liga soluções encontradas na fase de intensificação às soluções de elite. Este algoritmo foi acoplado ao GRASP implementado neste trabalho. A cada nova melhoria de solução obtida pelo GRASP (em cada uma de suas iterações), um pool de soluções de elite é atualizado. Caso o pool ultrapasse um determinado tamanho, são mantidas as k melhores soluções, onde k é um parâmetro ajustável. A etapa que decide quais caminhos percorrer está descrita no pseudocódigo a seguir: 1 2 3 4 5 6 7 8 9 10 11 12 13

Procedimento PATH RELINKING Parametros : Pool de Solucoes Elite e Solucao S qualquer MelhorSolucao = S Senao Para cada elemento i em E Solucao atual = pe rc or re rA va lia nd o (i , S ) Se ( avaliacao ( atual ) < avaliacao ( MelhorSolucao ) ) MelhorSolucao = atual Fim - Para Retorne MelhorSolucao Fim - Se retorne MelhorSolucao }

Pseudocódigo 3.6 – Pseudocódigo Geral Path Relinking

1 2 3 4 5 6 7 8 9 10 11

Procedimento PERCORRER AVALIANDO Parametros : Solucao Origem e Solucao Destino . Step = Origem Melhor = Step Enquanto Step != Destino Solucao Step = MAIS_PROMISSORA ( Step , Destino ) Se avaliacao ( Step ) < avaliacao ( Melhor ) Melhor = Step Fim - Se Fim - Enquanto Retorne Melhor

Capítulo 3. Métodos Heurísticos

Pseudocódigo 3.7 – Pseudocódigo Específico Path Relinking

1 2 3 4 5 6 7 8 9 10 11 12

Procedimento MAIS_PROMISSORA Parametros : Solucao Origem e Solucao Destino . Vetor trocas = { vazio } Para cada tarefa i escalonada na Origem Se o id da tarefa i correspondente no Destino diferir j = p o s i c a o C o r r e s p o n d e n t e da tarefa i no Destino Empilhar a tupla {i , j } no vetor de trocas Fim - Se Fim - Para Se ( trocas == { vazio }) Retorne Origem Fim - Se

13 14 15 16 17 18 19

Vetor so lu co es Ca nd id at as = { vazio } Para cada troca T em trocas S = geraSolucao ( Origem , T ) ; empilhar S no vetor de s ol uc oe sC an di da tas Fim - Para retorne melhorAvaliada ( so lu co es Ca nd ida ta s ) // Simples de obter .

Pseudocódigo 3.8 – Pseudocódigo Step Relinking

32

33

4 Detalhes de Implementação A linguagem C++ foi utilizada para implementar os algoritmos. Foi utilizado o compilador g++ versão 4.8.2 tendo como ambiente Linux a distribuição Ubuntu 14.04 LTS. O código se distribui em 10 arquivos fonte, 11 arquivos de headers e 6 arquivos shellscript totalizando 3619 linhas de código. Para o controle de versão, foi utilizada a ferramenta Git. A função objetivo é calculada por um algoritmo que neste trabalho manipula objetos das classes Solucao (cuja estrutura foi descrita na subseção 2.4.7) e Instancia. A fim de acomodar o escalonamento das tarefas nas m máquinas, o objeto Solucao é definido como um vetor de m listas de tarefas. Instancia é definida como um conjunto de matrizes alocadas estaticamente com tamanho igual ao tamanho adequado à maior instância testada. Este trabalho priorizou a realização de uma prova de conceito da aplicação da linguagem C++ e dos recursos da STL, Standard Template Library.

4.1 Classes Para armazenar as informações e métodos relacionados às instâncias, foi criada uma classe Instancia. Ela permite que todas as matrizes com dados lidos a partir de arquivos de texto ficam armazenados na memória de forma consistente, além de prover métodos (em alguns casos implícitos) de alocação, desalocação, leitura, modificação e exibição. A mesma analogia vale para a classe Solucao, que possui métodos de alocação, comparação, inicialização, desalocação, modificação, leitura e exibição.

4.2 Algoritmos e Desempenho A classe BateriaDeT estes possui um método run cuja arquitetura assíncrona permitiu um melhor aproveitamento dos núcleos de processamento. Cada instância, seja ela da categoria small ou large, é tratada como uma tarefa. Assim a thread principal transforma o índice de tarefas em uma pilha de tarefas pendentes. Após a construção desta pilha, várias threads são iniciadas para dar vazão à fila de tarefas pendentes. Assim, não é necessário nenhum tipo de espera na execução dos testes já que todos os núcleos atingem valores elevados de utilização. O tempo de execução de quatro instâncias da categoria small foi reduzido de 5 minutos e 24.457 segundos para 2 minutos e 32.788 segundos utilizando quatro threads, uma redução de 53%. Acima da proporção de uma thread por núcleo de processamento, nenhum ganho considerável foi detectado.

Capítulo 4. Detalhes de Implementação

34

Figura 2 – Níveis de utilização dos núcleos ao longo do tempo com quatro threads e com apenas uma.

35

5 Testes e Resultados Juntamente com o método DJASA, três modalidades de GRASP foram testadas sendo elas: busca local via Hill Climbing e busca local com Simulated Annealing, tendo este uma versão com Path Relinking e uma versão sem tal recurso.

5.1 Condições de Teste O computador utilizado para realizar a comparação da versão multithread com thread única em um equipamento de baixo poder computacional é um notebook com processador core i3, 6 GB RAM e 500 GB HD. Para rodar as 360 instâncias da categoria small foi utilizada uma máquina virtual rodando em um hardware com processadores Intel Xeon E5-2670 v2 (Ivy Bridge), com 32 vCPUs, 60 GiB de RAM e 2 x 320 GB de armazenamento.

5.2 Qualidade das Soluções e Tempos de conclusão Todas as três variantes do GRASP implementadas apresentaram soluções de qualidade, em vários casos superando o melhor valor até então encontrado em testes reportados na literatura com limitações de tempo e 2000 iterações. Embora os a qualidade das soluções tenha sido similar, o tempo médio de execução do GRASP HC foi consideravelmente menor nas instâncias da categoria small. Para as primeiras 30 instâncias da categoria small, tempo médio do GRASP HC foi de 61 segundos, contra 48 segundos do GRASP PRSA e 62 segundos do GRASP SA.

Capítulo 5. Testes e resultados

36

Figura 3 – Comparativo de qualidade de solução ao longo do tempo - Categoria Small com 2000 iterações

Capítulo 5. Testes e resultados

37

Figura 4 – Comparativo de qualidade de solução ao longo do tempo - Categoria Small com 2000 iterações

Capítulo 5. Testes e resultados

38

Figura 5 – Comparativo de qualidade de solução ao longo do tempo - Categoria Small com 2000 iterações

Capítulo 5. Testes e resultados

39

Figura 6 – Comparativo de qualidade de solução ao longo do tempo - Categoria Small com 2000 iterações

Capítulo 5. Testes e resultados

40

Tabela 1 – Comparações de Algumas Instâncias da Categoria Small com 2000 iterações Instance Name

Method

Final mean evaluation 1594.0

Latest Time

Best Literature Evaluation

Best Evaluation Achieved

Reduction %

I 10 3 S(1-50;50-100) R(1-3;3-5) 2 I 10 3 S(1-50;50-100) R(1-3;3-5) 2 I 10 3 S(1-50;50-100) R(1-3;3-5) 2 I 10 3 S(1-50;50-100) R(1-3;3-5) 4 I 10 3 S(1-50;50-100) R(1-3;3-5) 4 I 10 3 S(1-50;50-100) R(1-3;3-5) 4 I 10 3 S(1-50;50-100) R(1-3;3-5) 1 I 10 3 S(1-50;50-100) R(1-3;3-5) 1 I 10 3 S(1-50;50-100) R(1-3;3-5) 1 I 10 3 S(1-50;50-100) R(1-3;3-5) 3 I 10 3 S(1-50;50-100) R(1-3;3-5) 3 I 10 3 S(1-50;50-100) R(1-3;3-5) 3

Hill Climbing PRSA

18.098392

1621

1594

1.665638

1594.0

586.213239 1621

1594

1.665638

SA

1594.0

637.458534 1621

1594

1.665638

Hill Climbing PRSA

1632.0

19.279270

1632

1632

0.0

1632.0

613.906070 1632

1632

0.0

SA

1632.0

592.611388 1632

1632

0.0

Hill Climbing PRSA

1541.0

17.431278

1560

1541

1.217949

1541.0

629.823086 1560

1541

1.217949

SA

1541.0

560.593852 1560

1541

1.217949

Hill Climbing PRSA

1686.0

18.252857

1654

1686

-1.934704

1686.0

604.107573 1654

1686

-1.934704

SA

1686.0

626.612972 1654

1686

-1.934704

Capítulo 5. Testes e resultados

41

Tabela 2 – Comparações de Algumas Instâncias da Categoria Large com 2000 iterações Instance Name

Method

I 100 10 S(1-50’50100) R(1-3’3-5) 4 I 100 10 S(1-50’50100) R(1-3’3-5) 4 I 100 10 S(1-50’50100) R(1-3’3-5) 4 I 100 10 S(1-50’50100) R(1-3’3-5) 2 I 100 10 S(1-50’50100) R(1-3’3-5) 2 I 100 10 S(1-50’50100) R(1-3’3-5) 2 I 100 10 S(1-50’50100) R(1-3’3-5) 3 I 100 10 S(1-50’50100) R(1-3’3-5) 3 I 100 10 S(1-50’50100) R(1-3’3-5) 3 I 100 10 S(1-50’50100) R(1-3’3-5) 5 I 100 10 S(1-50’50100) R(1-3’3-5) 5 I 100 10 S(1-50’50100) R(1-3’3-5) 5

Hill Climbing PRSA

Final mean evaluation 38840.25

Latest Time

Best Literature Evaluation

Best Evaluation Achieved

Reduction

9621.638945 24782

28157

-13.61

29640.5

43748.47

24782

29174

-17.72

SA

36568.5

15088.65

24782

36447

-47.07

Hill Climbing PRSA

39046.75

8954.98

23558

29532

-25.35

29508.5

44364.36

23558

29194

-23.92

SA

35815.0

14970.38

23558

35611

-51.16

Hill Climbing PRSA

39497.41

9036.61

24646

30176

-22.437718

30554.0

44235.31

24646

29790

-20.871541

SA

36105.0

14995.35

24646

35964

-45.922259

Hill Climbing PRSA

29152.5

9063.25

25935

28462

-9.743590

30406.0

44246.92

25935

30296

-16.815115

SA

36234.5

14522.95

25935

36050

-39.001350

Capítulo 5. Testes e resultados

42

Figura 7 – Comparativo de qualidade de solução ao longo do tempo - Categoria Large com 2000 iterações

Capítulo 5. Testes e resultados

43

Figura 8 – Comparativo de qualidade de solução ao longo do tempo - Categoria Large com 2000 iterações

Capítulo 5. Testes e resultados

44

Figura 9 – Comparativo de qualidade de solução ao longo do tempo - Categoria Large com 2000 iterações

Capítulo 5. Testes e resultados

45

Figura 10 – Comparativo de qualidade de solução ao longo do tempo - Categoria Large com 2000 iterações

46

6 Conclusão Os métodos heurísticos implementados permitiram atingir soluções de boa qualidade, frequentemente ótimas, para várias instâncias da categoria small. O método GRASP PRSA atingiu, em geral, soluções de melhor qualidade para instâncias large. De fato, a reconexão de caminhos permitiu um ganho de qualidade nas soluções apesar do aumento do custo computacional. Soluções de boa qualidade foram obtidas mesmo com 100 iterações. O ganho expressivo de qualidade obtido pela busca local via Simulated Annealing e Path Relinking serve como validação para os procedimentos já que os métodos heurísticos testados atingiram as soluções ótimas em vários casos, e para as situações onde as soluções conhecidas não eram ótimas foi possível obter boas soluções. Versões multithread foram testadas comprovando ganhos de tempo de execução. Como trabalhos futuros, pode-se citar a variação automática de parâmetros de meta-heurísticas a fim de melhorar o desempenho.

47

Referências ALLAHVERDI, A. et al. A survey of scheduling problems with setup times or costs. European Journal of Operational Research, n. 187, p. 985–1032, 2008. CHENG, T.; SIN, C. A state-of-the-art review of parallel-machine scheduling research. European Journal of Operational Researc, n. 47, p. 271–292, 1990. FEO, T. A.; RESENDE, M. G. C. A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, p. 67–71, 1989. GLOVER, F.; LAGUNA, M.; MARTÍ, R. Fundamentals of scatter search and path relinking. Control and Cybernetics, n. 29, p. 653–684, 2000. KAMPKE, E. H. Metaheheurísticas para o Problema de Programação de Tarefas em Máquinas Paralelas com Tempos de Preparação Dependentes da Sequência e de Recursos. Dissertação (Mestrado) — Universidade Federal de Viçosa, 2010. OSMAN, I.; POTTS, C. Simulated annealing for permutation flow-shop scheduling. OMEGA - The International Journal of Management Science, v. 17, n. 6, p. 551–557, 1989. RUIZ, R.; ANDRÉS, C. Unrelated parallel machines scheduling with resource assignable sequence dependent setup times. Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), p. 439–446, 2007. ZHANG, F.; TANG, G.; CHEN, Z.-L. A 3/2-approximation algorithm for parallel machine scheduling with controllable processing times. Operations Research Letters, n. 29, p. 41–47, 2001.