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




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

  * 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.
  * [[http://www.ufrgs.br/propesq/seminarios/apresentacaooral.ppt|Como apresentar]]
  * :!: **Apresentar uma proposta ate 18/05/2009**.
  * **Prazos** Entrega do trabalho escrito: 12/06.








===== Problemas =====
{{T.pdf|Definição dos problemas}} {{t3.pdf|Definição detalhada}}

  * [[http://people.brunel.ac.uk/~mastjjb/jeb/orlib/scpinfo.html|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)

^ Inst ^ Valor ^ Inst ^ Valor ^ Inst ^ Valor ^ Inst ^ Valor ^ Inst ^ Valor ^ Inst ^ Valor ^
| scpclr10 |  23 | scpclr11 |  25 | scpclr12 |  26 | scpclr13 |  26 | scpcyc6 |  60 | scpcyc7 |  144 |
| scpcyc8 |  344 | scpcyc9 |  780 | scpcyc10 |  1792 | scpcyc11 |  4103 | scp410 |  514 | scp510 |  265 |
| scpa1 |  253 | scpc1 |  227 | scpe1 |  5 | scpnrf1 |  14 | scpnrg1 |  176 | scpnrh1 |  63 |

  * [[http://people.brunel.ac.uk/~mastjjb/jeb/orlib/jobshopinfo.html|Job shop scheduling]]
    * Instâncias: orb01, ft10, abz6, la01, la16, la26, la31, la36, swv01, swv06, swv11, yn1 (todas dentro do arquivo jobshop1.txt)


===== 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 parametero 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 ^ A ^ R ^ C ^
| 1    |  CC+GRASP  |  Francis,Guilherme  | OK | OK | OK |
| 2    |  CC+AG  |  Marcelo,Matheus  | OK | OK | OK |
| 3    |  CC+SA  |  Roger, Fernando  | OK | OK | OK |
| 4    |  CC+VNS  |  Eduardo, Vanius  | OK | OK | OK |
| 5    |  JSS+VNS  |  Pedro  | OK | OK | OK |
| 6    |  JSS+SA  |  Marcus,André  | OK | OK | OK |
| 7    |  CC+BT  |  Alisson,Soraya  | OK | OK | OK |
| 8    |  JSS+BT  |  Rafael, Vinicius  | OK | OK | OK |
#Escolhas: 15/16. A=Apresentação, R=Relatório, C=Código.











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

^       ^ CC  ^ JSS  ^
| SA    |  X  |  X  |
| VNS   |  X  |  X  |
| BT    |  X  |  X  |
| GA    |  X  |     |
| GRASP |  X  |     |






===== Agenda =====
^ Data ^ Hora ^ Apresentação ^
| 15/06 |  8.30 |  VNS  |
| 15/06 |  8.50 |  GRASP  |
| 15/06 |  9.10 |  BT  |
| 15/06 |  9.30 |  SA  |
| 15/06 |  9.50 |  GA  |
| 17/06 |  8.30 |  SA  |
| 17/06 |  8.50 |  BT  |
| 17/06 |  9.10 |  VNS  |
| 17/06 |  9.30 |    |
| 17/06 |  9.50 |    |