====== Trabalhos ====== ===== Considerações gerais ===== * O trabalho é em grupos de três. * Cada grupo escolhe **um problema** e **uma meta-heurística**. * Tarefa de cada grupo: * Formular o problema como programa linear ou inteiro * Resolver as instâncias definidas (abaixo) com um solver genérico (p.ex. GLPK,SCIP) * Definir e implementar e meta-heurística escolhida para o problema * Resolver as instâncias definidas com a meta-heurística * Documentar e analisar os experimentos: **relatório** * Apresentar os resultados: **apresentação em aula** * [[http://www.ufrgs.br/propesq/seminarios/apresentacaooral.ppt|Como apresentar]] * :!: **Apresentar uma proposta ate 01/12/2010**. * Contéudo: Definição dos principais elementos da abordagem (vizinhanças, etc.) * **Prazos** Entrega do trabalho escrito: 06/12/2010. ===== Problemas ===== {{Ta.pdf|Definição dos problemas}} * [[http://www.assembly-line-balancing.de/index.php?content=classview&content2=classview&content3=classviewdlfree&content4=classview&classID=28&type=dl|Balanceamento de linhas de produção]] * Instâncias, melhores valores conhecidos e limite superior da solução ótima: ^ Nome ^ m ((Número de máquinas)) ^ c ((Melhor valor conhecido)) ^ | Arcus2 | 27 | 5689 | | Arcus2 | 9 | 16711 | | Barthol2 | 51 | 84 | | Barthol2 | 27 | 157 | | Warnecke | 10 | 155 | | Warnecke | 20 | 79 | | Scholl | 50 | 1394 | | Scholl | 38 | 1834 | | Scholl | 25 | 2787 | | Wee-Mag | 20 | 77 | | Wee-Mag | 30 | 56 | * [[http://people.brunel.ac.uk/~mastjjb/jeb/orlib/mknapinfo.html|Problema da mochila multidimensional]] * Instâncias e melhores valores conhecidos: ^ Instância ^ c ((Melhor valor conhecido)) ^ Arquivo ^ | 5.100-00 | 24381 | mknapcb1 | | 5.100-29 | 59965 | mknapcb1 | | 5.250-00 | 59312 | mknapcb2 | | 5.250-29 | 154662 | mknapcb2 | | 5.500-00 | 120130 | mknapcb3 | | 5.500-29 | 299904 | mknapcb3 | | 30.100-00 | 21946 | mknapcb7 | | 30.100-29 | 60603 | mknapcb7 | | 30.250-00 | 56693 | mknapcb8 | | 30.250-29 | 149572 | mknapcb8 | | 30.500-00 | 115868 | mknapcb9 | | 30.500-29 | 300460 | mknapcb9 | Obs: NN.MMM-XX é a instância número XX (contando a partir de 0) nos arquivos indicados com NN restrições, MMM variáveis. * [[http://people.brunel.ac.uk/~mastjjb/jeb/orlib/thpackinfo.html|Empacotamento de contâineres]] * Instâncias e melhores valores conhecidos: Usar a instância no. 50 de cada conjunto de instâncias. ^ Instância ^ c ((Melhor valor conhecido)) ^ | br1 | | | br2 | | | br3 | | | br4 | | | br5 | | | br6 | | | br7 | | | br8 | | | br9 | | | br10 | | ===== Meta-heurísticas ===== * Simulated annealing (SA) * Variable neighborhood search (VNS) * Busca Tabu (BT) * Algorítmo genético/memético (GA) * GRASP ===== Convenções ===== * 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 parâmtero da linha de comando é o nome de um arquivo para gravar a melhor solução encontrada. ===== Documentação e critérios de avaliação ===== 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 [[:relatorio|relatório]] com a documentação da solução com resultados e discussão (veja um {{sa-r.pdf|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. **[[trabalho-faq|Perguntas frequentes (FAQ)]]** ===== Grupos e trabalhos selecionados ===== ^ No. ^ Trabalho ^ Grupo ^ CP ^ A ^ R ^ C ^ | 1 | MM+AG | Christian, Marcio, Lucas Guerra | R | R | R | R | | 2 | MM+GRASP | Ana, Cassiano, Thais | R | R | R | R | | 3 | MM+SA | Matheus Jullien, Rodrigo, Luca | R | R | R | R | | 4 | BL+VNS | Humberto, Pedro Vieira | R | R | R | R | | 5 | BL+GA | Eduardo, Paulo, Damien | R | R | R | R | | 6 | BL+GRASP | Fabio, Cristiano, Lucas Zawacki | R | R | R | R | | 7 | MM+VNS | Ciro, Renato, Ananias | R | R | R | R | | 8 | BL+SA | Marcelo, Luis, Gabriel Hernandez | R | R | R | R | | 9 | EC+AG | Jean, Diego Marcon, Jeferson | R | R | R | R | | 10 | EC+BT | Pedro Dusso, Alexandre, Otávio | R | R | R | R | | 11 | MM+BT | Diego Bandeira, André, Tomaz | R | R | R | R | | 12 | EC+GRASP | Matheus Berlesi, Matheus Abegg, Gabriel Lamb Wink | | R | R | R | #Escolhas: 35/44. A=Apresentação, R=Relatório, C=Código. ==== Seleções ==== ^ ^ BL ^ MM ^ EC ^ | SA | X | X | | | VNS | X | X | | | BT | | X | X | | AG | X | X | X | | GRASP | X | X | X | ===== Agenda ===== ^ Data ^ Hora ^ Apresentação ^ | 06/12 | 10.30 | MM+AG | | 06/12 | 10.45 | MM+SA | | 06/12 | 11.00 | MM+BT | | 06/12 | 11.15 | MM+GRASP | | 06/12 | 11.30 | MM+VNS | | 06/12 | 11.45 | BL+SA | | 08/12 | 10.30 | BL+GRASP | | 08/12 | 10.45 | BL+GA | | 08/12 | 11.00 | BL+VNS | | 08/12 | 11.15 | EC+BT | | 08/12 | 11.30 | EC+GRASP | | 08/12 | 11.45 | EC+AG |