Dissertação
{pt=Problema de Escalonamento de Técnicos e Intervenções numa Empresa de Telecomunicações} {} EVALUATED
{pt=O concurso organizado pela Sociedade Francesa de Investigação Operacional e Análise de Decisão, designado por Roadef?2007 Challenge, consistiu na resolução de um problema de optimização proposto pela France Telecom. O objectivo deste problema é planear um escalonamento de técnicos e intervenções (tarefas) de tal forma que intervenções terminem no menor tempo possível, tendo em conta um conjunto de restrições de precedência, disponibilidade dos técnicos e outras. Por outro lado, para cada Instância é dado um valor monetário que representa o custo limite das intervenções a enviar para outsourcing. Nesta tese, este problema foi inicialmente formulado como um problema de programação linear inteira. Contudo, os resultados experimentais obtidos em instâncias de grandes dimensões indicam que métodos exactos têm grandes limitações de ordem computacional na resolução deste problema. Deste modo, esta tese apresenta igualmente uma análise experimental do desempenho de vários métodos heurísticos, tais como heurísticas simples de pesquisa local e arrefecimento simulado, que retornam uma aproximação do óptimo num tempo razoável. Estas heurísticas apresentaram resultados bastante aceitáveis uma vez que se encontram dentro da gama dos resultados obtidos pelas equipas concorrentes apuradas para a fase final do concurso., en=The challenge organized by French Society of Operational Research and Decision Analysis, known as ROADEF 2007 Challenge, consisted on solving an optimization problem proposed by France Telecom. The main goal of this problem is to schedule technicians and interventions in such way that the interventions finish in the lowest possible time, by taking into account a set of precedence constraints, availability of technicians, and other constraints. On the other hand, for each instance a budget is given that represents the amount of money available to outsource interventions. In this thesis, we propose several algorithms for tackling this problem. We started by formalizing it as an integer programming problem. However, the experimental results obtained in large size instances indicate that such approach may have serious computational limitations. Therefore, we also present an experimental analysis on the performance of some heuristics, such as local search and simulated annealing, which return an approximation of the optimum in a reasonable amount of time. Some of these heuristics were able to reach similar results to those obtained by more complex and high performing algorithms for the final phase of the ROADEF challenge.}
março 2, 2009, 10:30
Publicação
Obra sujeita a Direitos de Autor
Orientação
