====== Trabalhos ======

===== Considerações gerais =====

  * O trabalho pode ser feito em grupos até três.
  * Cada grupo escolhe **um problema** e ** uma meta-heurística**.
  * Cada grupo implementa o problema, conduz testes com instâncias pre-definidos, documenta os resultados e apresenta-los.
  * [[http://www.ufrgs.br/propesq/seminarios/apresentacaooral.ppt|Como apresentar]]






===== Problemas =====
{{t.pdf|Definição dos problemas}}

  * [[http://www.wiwi.uni-jena.de/Entscheidung/binpp|Empacotamento (bin packing)]]
    * Instâncias: N1C1W1_A,N2C2W2_F,N2C2W1_A,N3C2W4_O,N4C3W4_R,N1W1B1R0,N2W2B2R2,N2W3B2R6,N3W3B3R4,N4W4B1R6,HARD2,HARD7
  * [[http://www.seas.upenn.edu/qaplib|Problema de Designação Quadrático (Quadratic Assignment Problem)]]
    * Instâncias: Bur26c,Bur26f,Chr15b,Chr22a,Els19,Esc16h,Esc32a,Had12,Had14,Kra30b,Kra32,Sk090
  * [[http://neo.lcc.uma.es/radi-aeb/WebVRP|Roteamento de Veículos com restrição de capacidade (capacitated vehicle routing problem)]]
    * Instâncias: A-n32-k5,A-n39-k6,A-n61-k9,A-n65-k9,E-n30-k3,E-n33-k4,E-n51-k5,E-n76-k10,F-n45-k4,F-n72-k4.

===== Meta-heurísticas =====

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





===== 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, por exemplo representação do problema e a seleção das operações.
  * Avaliação experimental\\
    Reprodutibilidade: Documentação das instâncias, tempo de execução, parametros, número de experimentos, semente do gerador randômico, etc. 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.
  * Uma implementação.
  * Uma apresentação em aula.


**[[trabalho-faq|Perguntas frequentes (FAQ)]]**






===== Grupos e trabalhos selecionados =====

^ No. ^ Trabalho ^ Grupo ^
| 1   | BP+GA     | Claudinei Constantin, Samir Nerado, Niarchos Pombo |
| 2   | BP+SA     | Dionatan Moura, Lucas Seadi, Tobias Petry |
| 3   | BP+VNS    | Eduardo Postal, Oscar paesi, Rodrigo Lumertz |
| 4   | DQ+VNS    | Márcio Rocha Zacarias |
| 5   | BP+GRASP  | Danilo Fukuda, Ismael Stangherlini, Laércio Pilla |
| 6   | BP+BT     | Eduardo Gastal, Rafael Henkin, Thiago Alves |
| 7   | DQ+GA     | Crístofer Kremer, Guilherme M. Macedo, Marcelo B. Anton |
| 8   | CVRP+BT   | José Antônio Salini Ferreira, Filipe Paz Rodrigues. André Machado |
| 9   | CVRP+VNS  | Rafael Trein |
| 10  | CVRP+GA   | Thiago Addevico Presa |
| 11  | DQ+BT     | Ana Paula Locatelli,Caesar Ralf Franz Hoppen |
| 12  | DQ+SA     | Fábio Arreguy Camargo Corrêa |
| 13  | CVRP+SA   | Rodrigo de Abreu Batista, César Malerba |
| 14  | DQ+GRASP  | Maurício Machado |
| 15  | DQ+BT     | Augusto Klinger, Felipe Miralha, Fernando Varella |
| 16  | CRVP+GRASP| Fernando Acker |
#Escolhas: 34/38.


==== Seleções ====

^       ^ BP  ^ DQ  ^ CVRP ^
| SA    |  X  |  X  |  X  |
| VNS   |  X  |  X  |  X  |
| BT    |  X  |  X  |  X  |
| GA    |  X  |  X  |  X  |
| GRASP |  X  |  X  |  X  |








===== Agenda =====
^ Data ^ Hora ^ Apresentação ^
| 26/11 | 10.30 | {{BP+SA.ppt|BP+SA}} |
| 26/11 | 10.50 | {{BP+VNS.pdf|BP+VNS}} |
| 26/11 | 11.10 | {{BP+BT.pdf|BP+BT}} |
| 26/11 | 11.30 | {{BP+GA.ppt|BP+GA}} |
| 26/11 | 11.50 | BP+GRASP |
| 28/11 | 10.30 | {{DQ+SA.pdf|DQ+SA}} |
| 28/11 | 10.50 | {{DQ+VNS.pdf|DQ+VNS}} |
| 28/11 | 11.10 | {{DQ+BT1.pdf|DQ+BT 1}} |
| 28/11 | 11.30 | DQ+BT 2 |
| 28/11 | 11.50 | {{DQ+GA.pdf|DQ+GA}} |
| 28/11 | 12.10 | {{DQ+GRASP.ppt|DQ+GRASP}} |
| 03/12 | 10.30 | {{CVRP+SA1.pdf|CVRP+SA}} |
| 03/12 | 10.50 | {{CVRP+VNS.pdf|CVRP+VNS}} |
| 03/12 | 11.10 | {{CVRP+BT.pdf|CVRP+BT}} |
| 03/12 | 11.30 | CVRP+GA |
| 03/12 | 11.50 | CVRP+GRASP |