Aula 1 (08/08/2012): Introdução ao conteúdo do curso; critérios de avaliação; visão geral do que é um problema de escalonamento. (Slides usados nesta aula)
Aula 2 (10/08/2012): Definição de escalonamento; diagrama de Gantt; exemplo da Fábrica de Tintas (makespan, limitante inferior, escalonamento com interrupções). (Slides usados nesta aula)
Aula 3 (15/08/2012): Notação α | β | γ para problemas de escalonamento; problemas com máquinas paralelas e máquinas shop; características e restrições de tarefas; critérios clássicos de otimização para problemas de escalonamento. (Slides usados nesta aula)
Aula 4 (17/08/2012): Escalonamentos sem atrasos, ativos e semi-ativos; breve resumo sobre complexidade computacional: notação assintótica (ordem Ο), problemas de decisão, algoritmo verificador, classes P e NP de problemas e redução polinomial de problemas. (Slides usados nesta aula)
Aula 5 (22/08/2012): Redução polinomial de problemas; problemas NP-completos; redução polinomial de PARTIÇÃO a P2 | | Cmax. (Slides usados nesta aula)
Aula 6 (24/08/2012): Redução polinomial de PARTIÇÃO a F3 | | Cmax; optimalidade do algoritmo SPT para o problema 1 | | ΣCi; optimalidade da Regra de Smith para o problema 1 | | ΣwiCi. (Slides usados nesta aula)
Aula 7 (29/08/2012): Algoritmo de Lawler para o problema 1 | prec | fmax; algoritmo Earliest Due Date first (EDD) para os problemas 1 | | Lmax e 1 | prec | Lmax e redução polinomial de 3-PARTIÇÃO a 1| ri | Lmax. (Slides usados nesta aula)
Aula 8 (12/09/2012): Estudo de artigo científico. Ronald L. Graham. Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics, Vol. 17, No. 2. (March 1969), pp. 416-429. (Slides usados nesta aula, cedidos pelo Milson Monteiro)
Aula 9 (14/09/2012): Introdução ao escalonamento em máquinas paralelas; optimalidade do problema P | pmtn | Cmax; garantias de Algoritmos de Lista e do algoritmo LPT para o problema P | | Cmax. (Slides usados nesta aula)
Aula 10 (19/09/2012): Garantias de aproximação "justas" para os Algoritmos de Lista e LPT; existência de PTAS para o problema P | | Cmax; cálculo do caminho crítico em grafos de precedência para o problema Pm | prec | Cmax.
Aula 11 (21/09/2012): Formulação como problema de programação linear, algoritmo polinomial ótimo e algoritmo LRPT para o problema P | prmp | Cmax; optimalidade do algoritmo SPT para o problema P | | ΣCi; optimalidade do problema Pm | prmp | Lmax.
Aula 12 (26/09/2012): Estudo de artigo científico: Cohen et al. Multi-organization scheduling approximation algorithms. Concurrency and Computation: Practice & Experience, 23: 2220–2234, 2011. Motivações, contexto e notações.
Aula 13 (28/09/2012): Continuação do estudo de artigo científico: limitantes inferiores e impacto das restrições locais e de egoísmo na qualidade do Cmax ótimo.
Aula 14 (03/10/2012): Aula do prof. Alfredo sobre heurísticas e meta-heurísticas.
Aula 15 (05/10/2012): Continuação do estudo de artigo científico: provas de NP-completude para o caso degenerado (organizações só contribuem com recursos) e para o caso completo (organizações contribuem com recursos e tarefas).
Aula 16 (17/10/2012): Estudo de artigo científico. Christos Papadimitriou and Mihalis Yannakakis. Towards an architecture-independent analysis of parallel algorithms. In Proceedings of the ACM Symposium on Theory of Computing (STOC '88). ACM, New York, NY, USA, 510-513, 1998. (Slides usados nesta aula, cedidos pelo Mijail Gamarra Holguin)
Aula 17 (19/10/2012): Análise e desempenho dos algoritmos ILBA, LPT-LPT, SPT-LPT e Less Helped First para o problema MOSP.
Aula 18 (24/10/2012): Estudo do Problema do Portfólio, seminário (convidado) apresentado pelo Dr. Yanik Ngoko. (Slides usados nesta aula)
Aula 19 (26/10/2012): Continuação do Problema do Portfólio, seminário (convidado) apresentado pelo Dr. Yanik Ngoko. (Slides usados nesta aula)
Aula 20 (31/10/2012): Estudo do problema de Escalonamento de Campanhas, seminário (convidado) apresentado por Vinicius Gama Pinheiro. (Slides usados nesta aula)
Aula 21 (07/11/2012): Estudo de artigo científico. Uwe Schwiegelshohn, Andrei Tchernykh, and Ramin Yahyapour. Online scheduling in grids. In Proceedings of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS 2008). (Slides usados nesta aula, cedidos pelo Milson Monteiro)
Aula 22 (09/11/2012): Estudo de artigo científico. Johanne Cohen, Christoph Dürr, and Thang Nguyen Kim. Non-clairvoyant Scheduling Games. Journal of Theory of Computing Systems 49, 1 (Julho 2011), 3-23. (Slides usados nesta aula, cedidos pelo Mijail Gamarra Holguin)
Aula 23 (21/11/2012): Revisão para a prova.
Aula 24 (23/11/2012): Perspectivas de pesquisa científica na área de Teoria do Escalonamento. Exemplos de tópicos de pesquisas atuais apresentados no workshop New Challenges in Scheduling Theory (Fréjus, França, 2012).
Aula 25 (28/11/2012): Prova.
Última modificação: 23 de novembro de 2012