APLICAÇÃO DO SCATTER SEARCH AO PROBLEMA DE ESCALONAMENTO DE PROJETOS COM RESTRIÇÃO DE RECURSOS E MÚLTIPLOS MODOS DE PROCESSAMENTO

APLICAÇÃO DO SCATTER SEARCH AO PROBLEMA DE ESCALONAMENTO DE PROJETOS COM...

(Parte 1 de 8)

Trabalho de Conclusão de Curso de Graduação em Ciência da Computação apresentado à FAESA - Faculdades Integradas Espírito-Santense, como requisito parcial para obtenção do título de Bacharel em Ciência da Computação, sob orientação do Professor Dr. Luciano Lessa Lorenzoni.

Relatório final do Trabalho de Graduação, apresentado à FAESA - Faculdades Integradas Espírito-Santense, como requisito parcial para obtenção do título de Bacharel em Ciência da Computação.

Aprovado em 01 de dezembro de 2009.

Prof. Dr. Luciano Lessa Lorenzoni – Orientador FAESA

Profª. Ma. Chíntia Cristina Lúcio Caliari FAESA

Profª. Ma. Elvira Pádua Lovatte FAESA

À minha esposa, Bruna Pimentel da Hora Hoehene, pela paciência, apoio, dedicação e cumplicidade na finalização de mais uma etapa de minha vida.

Leandro Geraldo Hoehene

Ao meu amigo Luciano Martins Basseto, pela sinceridade, apoio e incentivo, na conclusão de mais um degrau de minha vida.

Luiz Carlos Chaves Küster

Leandro

Primeiramente, quero agradecer a Deus pela sua presença constante em minha vida me dando força para superar as dificuldades encontradas.

Aos meus pais, Elmo e Cleuza, minha esposa, minha irmã e meus irmãos, pelo incontestável apoio que me ofereceram, incentivando-me a seguir em frente no intuito de atingir meus objetivos.

Ao meu orientador, Prof. Dr. Luciano Lessa Lorenzoni, não só pela orientação deste trabalho, mas também por todo ensinamento compartilhado.

A todos os meus amigos e colegas, em especial Luiz Carlos (Robinho), aos demais familiares e todos os professores que de uma forma ou de outra estiveram presentes durante toda a minha caminhada acadêmica.

Luiz Carlos

Ao nosso Deus, por seu infinito amor, motivo de nossa existência e que renova a cada dia as nossas esperanças e a nossa força, sem nunca levar em conta a dignidade ou merecimento de cada um de nós.

Aos meus amigos, em especial ao Leandro, aos meus pais e familiares, pela compreensão, apoio, incentivo e paciência demonstrada ao longo de todo o tempo que empreguei no desenvolvimento deste trabalho.

Também aos meus professores, em especial ao meu orientador Prof. Dr. Luciano Lessa Lorenzoni, pelo carinho, apoio e ensinamentos que levarei para toda a vida.

“O futuro tem vários nomes. Para os fracos é inatingível.

Para os medrosos, o desconhecido. Para os corajosos, a oportunidade.”

Vitor Hugo

2.1 Relações de precedência17
2.2 Alocação de recursos e makespan18
recursos2
3.1 Fluxo principal do Scatter Search27
3.2 Exemplo do crossover 1 – combinação de um único ponto31
3.3 Exemplo do crossover 2 – combinação em multipontos32
3.4 Exemplo do crossover 3 – combinação uniforme3
3.5 Exemplo da mutação 134
3.6 Exemplo da mutação 235
2.1 Projeto com 10 atividades reais e 2 recursos16
4.1 Notação utilizada na classificação do algoritmo Scatter Search39
4.2 Modos de processamento40
4.3 Parametrização – NP e RS42
4.4 Impacto dos métodos geradores de soluções43
4.5. Impacto de escalonamentos não repetidos4
4.6 Impacto dos subconjuntos45
4.7 Impacto dos métodos de combinação45
4.8 Impacto das mutações46
4.9 Conjunto de parâmetros para intervenção47
4.10 Impacto das intervenções no conjunto referência47
4.1 Conjunto de parâmetros para aninhamento de 2 níveis49
4.12 Impacto do aninhamento em 2 níveis49
4.13 Conjunto de parâmetros para aninhamento de 3 níveis49
4.14 Impacto do aninhamento em 3 níveis50
algoritmo51

4.15 Impacto do método de melhoria LSAD, na versão SSP,GS3,LS, SB1,CR7,RP,MU4 do

4.16 Impacto do método de melhoria LSAD, na versão SSP,GS3,LS, SB1,CR7,RP,MU4,AN1 do

algoritmo51
4.17 Impacto do aumento da população inicial (NP)51
4.18 Evolução da meta-heurística e seus métodos52
4.19 Comparação da meta-heurística na classe de problemas J2053

4.20 Comparação da meta-heurística em todas as classes de problemas .......... 54

SSP,GS3,LS,SB1,CR7,RP,MU4,LSAD2 do algoritmo60

8.1 Resultados em todas as classes de problemas com a versão 8.2 Resultados em todas as classes de problemas com a versão

9 RESUMO

Este trabalho apresenta o problema de escalonamento de projetos com restrição de recursos e múltiplos modos de processamento. Esse problema consiste na identificação do tempo de início de processamento de cada atividade e na escolha do modo de processamento, tendo como objetivo minimizar o maior tempo dentre todas as atividades, respeitando as relações de precedência entre as atividades. Devido à grande complexidade em se determinar a melhor solução para esse problema, pois se trata de um problema da classe NP - difícil, aplicou-se a metaheurística Scatter Search com o intuito de se encontrar uma solução satisfatória. Essa meta-heurística opera sobre um conjunto de soluções chamado conjunto referência, combinando-as e gerando novas soluções, de modo a melhorar a solução original. Os experimentos computacionais foram feitos através do uso de um conjunto de problemas-padrão disponível na literatura. Nos experimentos, percebeuse a necessidade de se modificar o algoritmo, adicionando alguns métodos não contidos na lógica original do Scatter Search, alcançando melhorias em relação à proposta inicial da metodologia.

1 INTRODUÇÃO12
RECURSOS14
2.1 CARACTERIZAÇÃO DO PROBLEMA15
DE PROJETO18
2.3 ÚNICO MODO (Single-Mode Case) – PS|prec|Cmax19
2.4 MULTIPLOS MODOS (Multi-Mode Case) – MPS|prec|Cmax20

SUMÁRIO 2 PROBLEMAS DE ESCALONAMENTO DE PROJETOS COM RESTRIÇÃO DE 2.2 NOTAÇÃO E CLASSIFICAÇÃO DOS PROBLEMAS DE ESCALONAMENTO 2.5 ABORDAGENS UTILIZADAS NA RESOLUÇÃO DO PROBLEMA DE

ESCALONAMENTO DE PROJETOS COM RESTRIÇÃO DE RECURSOS21
2.5.1 Métodos Exatos23
2.5.2 Métodos Heurísticos23
3 SCATTER SEARCH APLICADO AO PROBLEMA DE ESCALONAMENTO25
3.1 INTRODUÇÃO25
ESCALONAMENTO28
3.2.1 Método Gerador de Soluções28
3.2.2 Método de Melhoramento29
3.2.3 Método de Atualização do Conjunto Referência30
3.2.4 Método de Geração de Subconjuntos30
3.2.5 Método de Combinação de Soluções31
3.2.6 Mutação34
4 EXPERIMENTOS COMPUTACIONAIS36
4.2 CALIBRAGEM DOS PARÂMETROS41
4.3 ANÁLISE DO SCATTER SEARCH43
4.3.1 Método Gerador de Soluções43
4.3.2 Conjunto Referência4
4.3.3 Método de Geração de Subconjuntos4
4.3.4 Métodos de Combinação45
4.3.5 Inserção da Mutação46
4.3.6 Intervenções no Conjunto Referência46
4.3.7 Aninhamentos de Conjunto Referência48
4.3.8 Método de Melhoramento50
4.4 CONSIDERAÇÕES FINAIS52
5 CONCLUSÕES56
6 PERSPECTIVAS FUTURAS57
7 REFERÊNCIAS58

1 INTRODUÇÃO

Segundo Blazewicz et al. (1996), citado por Lorenzoni (2003, p.18) os problemas de escalonamento estão associados a alocação de recursos para um conjunto de tarefas em um determinado tempo. Escalonar significa alocar recursos para a execução das tarefas com o objetivo de minimizar o tempo de processamento das tarefas.

Dada a necessidade de aperfeiçoar diversas situações no mundo real, como por exemplo, planejamentos de produção, gerenciamento de projetos e sequenciamento de tarefas por um microprocessador, têm-se um enfoque no desenvolvimento de soluções viáveis desses processos dentro de um prazo de entrega aceitável, que são desenvolvidas pelos algoritmos meta-heurísticos, usando-se variadas técnicas e metodologias. Nesse conjunto há uma classe especial de problemas que é o de escalonamento com restrição de recursos e múltiplos modos de processamento, adaptados a diversas aplicações no dia a dia.

De acordo com Artigues, Demassey e Néron (2008, p. 21) um problema de escalonamento de processos com restrição de recursos considera recursos de disponibilidade limitada, atividades de durações conhecidas e solicitações de recursos. O problema consiste em encontrar um escalonamento da duração mínima pela alocação do tempo de início de cada atividade, respeitando as relações de precedências e as disponibilidades de recursos.

Conforme Brucker et al. (1999) citado por Lorenzoni (2003, p.19) em meados da década de 90, os problemas de escalonamento com restrição de recursos tem sido alvo de interesse de pesquisadores. As generalizações deste problema, como os que possuem restrições de precedências generalizadas e as com múltiplos modos de processamento, são tipos de escalonamento mais gerais que contêm quase todos os problemas complexos de escalonamento de máquinas como casos especiais.

Para Artigues, Demassey e Néron (2008, p. 21) segundo a teoria de complexidade computacional, o problema de escalonamento de processos com restrição de recursos é um dos mais complexos problemas de otimização combinatorial. De fato, o problema de escalonamento de processos com restrição de recursos pertence à classe de problemas NP - difícil.

O uso prático desse problema pode ser encontrado facilmente em diversas situações do mundo real, por exemplo, no contexto portuário. Nesse contexto os recursos são os berços de atracação e as tarefas são as solicitações do navio para o embarque e/ou desembarque de carga.

Conforme Lorenzoni (2003, p.19) apesar de serem práticos, poucos têm sido os desenvolvimentos de trabalhos que demonstram sua aplicação em situações do mundo real.

Otimizar essas situações do mundo real, permite aumentar os lucros e diminuir os custos operacionais das mais diversas organizações.

O objetivo deste trabalho é desenvolver uma meta-heurística baseada no Scatter Search (S) almejando alcançar soluções viáveis com um alto percentual de soluções ótimas ou com baixas taxas de desvios, para o problema de escalonamento com restrição de recursos e múltiplos modos de processamento.

O presente trabalho, além desta introdução, está estruturado da seguinte forma:

No capítulo 2 – problemas de escalonamento de projetos com restrição de recursos – será abordado o estado da arte na área de problemas de escalonamento, descrevendo o problema, assim como suas variações e apresentaremos um estudo mais específico, abrangendo o conceito e a complexidade do problema.

No capítulo 3 – Scatter Search – é feita uma descrição geral da abordagem e de rotinas de intensificação e diversificação, que combinadas geram diferentes versões do algoritmo.

No capítulo 4 – experimentos computacionais – apresenta as abordagens algorítmicas utilizadas para a sua resolução, a biblioteca PSPLIB (Project Scheduling Problem Library) e os resultados obtidos pelo algoritmo proposto e a comparação dos resultados obtidos com os melhores resultados encontrados na literatura. Por fim, no capitulo 5 são apresentadas as conclusões do trabalho e no capítulo 6 as perspectivas de estudos futuros.

2 PROBLEMAS DE ESCALONAMENTO DE PROJETOS COM RESTRIÇÃO DE RECURSOS

Em um problema de escalonamento, temos um número limitado de recursos para serem usados no processamento de um conjunto de tarefas (Lawler et al. 1993, Pinedo, 1995). As tarefas individualmente disputam esses recursos que podem ser de naturezas distintas, tais como, mão de obra, capital, máquina, energia e ferramenta. Escalonar significa determinar o tempo de início do processamento de cada tarefa e os recursos utilizados na sua execução, tendo como principal meta a otimização de um ou mais objetivos (WEGLARZ, 1998, p. 2).

Segundo Lorenzoni (2003, p.23) os tipos de escalonamento podem ser dois. O determinístico, o qual os dados que definem uma instância do problema são conhecidos antes, e o estocástico, o qual um ou mais dados são definidos aleatoriamente durante a execução das tarefas.

O estudo sobre esse tipo de problema iniciou-se nos anos 50 com Kelly & Walter, que desenvolveram o Método do Caminho Crítico (Critical Path Method – COM). Esse método determinava o comprimento mínimo do projeto, os intervalos de tempo que indicavam o primeiro e o último instante em que se pode iniciar o processamento de uma tarefa (janela de tempo) e o conjunto de tarefas críticas, sempre respeitando as relações de precedência. Inicialmente, as restrições de recursos não eram levadas em conta explicitamente. Considerava-se que os recursos envolvidos tinham disponibilidades ilimitadas. Com o passar do tempo foise considerando aspectos mais realísticos, como por exemplo, a limitação de recursos (LORENZONI, 2003, p. 24).

Para Lorenzoni (2003, p. 24) resolver um problema de escalonamento de projetos quando vários tipos de recursos são considerados é uma tarefa difícil. Vários procedimentos têm sido desenvolvidos para resolver este problema otimamente ou aproximadamente.

15 2.1 CARACTERIZAÇÃO DO PROBLEMA

De acordo com Artigues, Demassey e Néron (2008, p. 21) informalmente, um problema de escalonamento de processos com restrição de recursos considera recursos de disponibilidade limitada, atividades de durações conhecidas e solicitações de recursos. O problema consiste em encontrar um escalonamento da duração mínima pela alocação do tempo de início de cada atividade, respeitando as relações de precedências e as disponibilidades de recursos.

(Parte 1 de 8)

Comentários