Trabalhos

• O trabalho pode ser feito em grupos de até dois.
• Cada grupo escolhe um problema e uma meta-heurística.
• A tarefa da cada grupo é implementar o problema, testar com instâncias definidas (listadas abaixo), documentar os resultados e apresentar-los.
• Como apresentar
• Apresentar uma proposta ate 18/05/2009.
• Prazos Entrega do trabalho escrito: 12/06.

Definição dos problemas Definição detalhada

• Cobertura por conjuntos
  • Instâncias: scpclr10, scpclr11, scpclr12, scpclr13, scpcyc6, scpcyc7, scpcyc8, scpcyc9, scpcyc10, scpcyc11, scp410, scp510, scpa1, scpc1, scpe1, scpnrf1, scpnrg1, scpnrh1
  • Valores das melhores soluções conhecidas (para comparação, Lan et al. 2007)

• Job shop scheduling
  • Instâncias: orb01, ft10, abz6, la01, la16, la26, la31, la36, swv01, swv06, swv11, yn1 (todas dentro do arquivo jobshop1.txt)

• Simulated annealing (SA)
• Variable neighborhood search (VNS)
• Busca Tabu (BT)
• Algorítmo genético/memético (GA)
• GRASP

• Todas implementações devem aceitar uma instância no formato do problema na entrada padrão (stdin) e imprimir a melhor solução encontrada na saida padrão (stdout).
• Os principais parametros do método devem ser definíveis pela linha de comando.
• O primeiro parametero da linha de comando é o nome de um arquivo para gravar a melhor solução encontrada.

O objetivo do trabalho é conhecer uma meta-heurística profundamente e ganhar experiência prática para aplicar-la em novos problemas. A avaliação reflete esse objetivo.

• Entendimento do método
  

Definição e justificativa da abordagem ao problema. Todas escolhas feitas para aplicar a meta-heuristica para o problema em questão devem ser claramente relatadas. Isso inclui a representação do problema, a função objetivo, a geração da solução inicial, a vizinhança e a estratégia de escolha em caso de buscas locais, os operadores (crossover,mutação) em caso de algoritmos genéticos, outros parameteros do métodos (temperature,lista tabu e tenure,…), critério de terminação. (Essa lista não é exhaustiva.)

• Avaliação experimental
  

Reprodutibilidade: Documentação das instâncias, tempo de execução, parametros, número de experimentos, semente do gerador randômico, etc. Método de escolha de parâmetros. Discussão e conclusões.

• Implementação
  

Critérios básicas da eng. de SW: documentação, legibilidade, etc.

O trabalho consiste em:

• Um relatório com a documentação da solução com resultados e discussão (veja um exemplo).
• Uma implementação (linguagem arbitrário desde seja padrão sem uso de bibliotécas proprietárias e pode ser compilado e executado usando somente software livre).
• Uma apresentação em aula.

Perguntas frequentes (FAQ)

#Escolhas: 15/16. A=Apresentação, R=Relatório, C=Código.