Algoritmos e Estruturas de Dados III
2^o semestre de 2008
Problema:
O problema de escalonamento de elevadores é interessante pelas várias métricas de sucesso que podem ser consideradas ao resolver o problema. Assim, o primeiro desafio está em contemplar essas várias métricas simultaneamente. Uma primeira métrica que já foi avaliada em trabalhos anteriores é o tempo médio de atendimento a um passageiro, ou seja, a soma dos tempos que o passageiro fica na fila e dentro do elevador. Uma segunda métrica relacionada é o tempo máximo de atendimento de um passageiro, que funcionaria como um acordo de qualidade de serviço. Uma terceira métrica é o quanto de energia o elevador consome, que pode ser expressa pelo quanto ele se movimenta. Note que minimizar o tempo de atendimento normalmente significa um aumento de consumo de energia.
Um segundo desafio é que a variabilidade da carga de trabalho pode fazer que estratégias que sejam muito efetivas para situações de pico não sejam boas para períodos onde o sistema de elevadores não está sobrecarregado.
O terceiro desafio é que a variação nos tempos de movimentação do elevador (quanto tempo para ir de um andar para outro) e nos tempos de entrada e saída de passageiros do elevador podem ser determinantes para a eficiência das estratégias.
O que fazer:
(a) Apresente duas estratégias para escalonamento do elevador: (i) minimiza tempo médio de atendimento e (ii) minimiza consumo de energia. Justifique, com exemplos didáticos, o princípio de funcionamento das estratégias.
(b) Qual a ordem de complexidade de cada estratégia proposta?
(c) As suas estratégias são ótimas? Por que?
(d) Implemente cada uma de suas estratégias.
(e) Compare o desempenho das estratégias para ambas as métricas de desempenho e variadas configurações de prédios (andares e número de elevadores), cargas de trabalho (número de passageiros, taxa de chegada e distribuição de origens e destinos) e custos de movimentação e entrada/saída de passageiros. Avalie também o custo computacional das suas estratégias e as relações custo-benefício em termos da qualidade da solução gerada. Não é permitido dividir estaticamente os andares entre os elevadores e o número de elevadores é sempre maior que um.
(f) Apresente a documentação das implementações realizadas (veja aqui maiores detalhes sobre a
entrega
de trabalhos práticos).
(g) Pontos Extras: Paralelize as suas implementações utilizando Pthreads. Cada paralelização funcionando e apresentando ganhos de desempenho será premiada com pontuação extra.