Metodologias de Planeamento e Escalonamento

Código:

EIC0063

Sigla:

MPES

Áreas Científicas
Classificação	Área Científica
OFICIAL	Inteligência Artificial

Ocorrência: 2013/2014 - 2S (de 10-02-2014 a 06-06-2014)

Ativa?	Sim
Página Web:	http://paginas.fe.up.pt/~eol/PRODEI/mpe1314_eng.htm
Unidade Responsável:	Departamento de Engenharia Informática
Curso/CE Responsável:	Mestrado Integrado em Engenharia Informática e Computação

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
MIEIC	10	Plano de estudos a partir de 2009/10	4	-	6	56	162

Língua de trabalho

Português - Suitable for English-speaking students

Objetivos

Abordar de uma forma integrada as problemáticas de planeamento e escalonamento.

Estudar abordagens tradicionais a problemas de planeamento e escalonamento.

Explorar metodologias de planeamento e escalonamento recentes, baseadas em algoritmos heurísticos do domínio da Inteligência Artificial.

Aplicar técnicas heurísticas de planeamento e escalonamento a problemas de complexidade média.

Resultados de aprendizagem e competências

Conhecer as principais abordagens à resolução de problemas de planeamento e escalonamento.

Saber aplicar métodos tradicionais de planeamento e escalonamento.

Saber identificar problemas de planeamento e escalonamento que requerem métodos heurísticos (do domínio da Inteligência Artificial) para a sua resolução.

Saber aplicar métodos heurísticos a problemas de planeamento e escalonamento de complexidade média.

Modo de trabalho

Presencial

Programa

Definições de Planeamento e Escalonamento. Planeamento vs. Escalonamento. Introdução às Metodologias Tradicionais de Planeamento e Escalonamento: CPM e PERT. Problemas e Aplicações.

Planeamento e IA: Geração Automática de Planos: Análise Meios-Fins, Planeamento Linear, Não-Linear, Hierárquico e Parcialmente Ordenado. Planeamento e Aprendizagem: Generalização de Planos.

Os problemas de escalonamento. Máquinas e trabalhos. Medidas de desempenho. Classificação de problemas de escalonamento. A notação alfa|beta|gama. Máquinas: número, tipo. "Job shop", "flow shop" e "open shop". Restrições de escalonamento: "preemption", "no-wait", precedências. Função objectivo: "makespan", "lateness", "tardiness". Modelos determinístico e estocástico de escalonamento.

Complexidade dos problemas de escalonamento. Decisão vs. optimização. A classe de problemas NP-Completos. Algoritmos de aproximação.

Algoritmos de escalonamento. "Branch and bound". "Dispatching rules". Algoritmos de pesquisa local. "Hill-climbing". Arrefecimento simulado. Pesquisa tabu. Algoritmos genéticos. "Ant colony optimization". Programação com restrições.

Modelização e resolução de problemas reais de planeamento e escalonamento.

Bibliografia Obrigatória

Pinedo, Michael; Scheduling. ISBN: 0-13-706757-7
Peter Brucker; Scheduling algorithms. ISBN: 3-540-20524-1
ed. by Joseph Y-T. Leung; Handbook of scheduling. ISBN: 1-584-88-397-9 (http://www.crcnetbase.com/doi/book/10.1201/9780203489802)
Michel Gendreau, Jean-Yves Potvin (eds); Handbook of Metaheuristics, Springer, 2010. ISBN: 978-1-4419-1663-1

Bibliografia Complementar

Barry McCollum et al.; International Timetabling Competition, 2007 ([online] avaliable at: http://www.cs.qub.ac.uk/itc2007/ (accessed on 24/01/2011))
ICAPS - International Conference on Automated Planning and Scheduling, 2011 ([online] avaliable at: http://ipc.icaps-conference.org/ (accessed on 24/01/2011))

Métodos de ensino e atividades de aprendizagem

Apresentação dos assuntos de forma interativa. Aprendizagem orientada ao projeto. Acompanhamento da execução dos trabalhos práticos.

Palavras Chave

Ciências Físicas > Matemática > Matemática aplicada > Investigação operacional
Ciências Físicas > Ciência de computadores > Cibernética > Inteligência artificial

Tipo de avaliação

Avaliação distribuída sem exame final

Componentes de Avaliação

Designação	Peso (%)
Participação presencial	0,00
Trabalho escrito	40,00
Trabalho laboratorial	60,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Elaboração de relatório/dissertação/tese	10,00
Frequência das aulas	42,00
Trabalho de investigação	30,00
Trabalho laboratorial	80,00
Total:	162,00

Fórmula de cálculo da classificação final

Avaliação distribuída sem exame final.

Trabalho/Projeto (100%), dividido da seguinte forma:

• Apresentação intercalar sobre o tema e abordagem (30%)
• Escrita de um relatório sob a forma de Artigo Científico (40%)
• Apresentação final do Trabalho (oral/demo) (30%)

 

Provas e trabalhos especiais

Trabalho/Projeto (incluindo todas as componentes: apresentação, demonstração e artigo) a apresentar em data a combinar com os docentes.

Avaliação especial (TE, DA, ...)

Trabalho/Projeto (incluindo todas as componentes: apresentação, demonstração e artigo) a apresentar em data a combinar com os docentes.

Melhoria de classificação

Trabalho/Projeto (incluindo todas as componentes: apresentação, demonstração e artigo) a apresentar em data a combinar com os docentes.