Análise do Desempenho de Técnicas de Otimização no Problema de Escalonamento

A optimização nas aplicações modernas assume um carácter fortemente interdisciplinar, relacionando-se com a necessidade de integração de diferentes técnicas e paradigmas na resolução de problemas reais complexos. O problema do escalonamento é recorrente no planeamento da produção. Sempre que uma ordem de fabrico é lançada, é necessário determinar que recursos serão utilizados e em que sequência as atividades serão executadas, para otimizar uma dada medida de desempenho. Embora ainda existam empresas a abordar o problema do escalonamento através de simples heurísticas, a proposta de sistemas de escalonamento tem-se evidenciado na literatura. Pretende-se nesta dissertação, a realização da análise de desempenho de Técnicas de Optimização, nomeadamente as meta-heurísticas, na resolução de problemas de optimização complexos – escalonamento de tarefas, particularmente no problema de minimização dos atrasos ponderados, 1||ΣwjTj. Assim sendo, foi desenvolvido um protótipo que serviu de suporte ao estudo computacional, com vista à avaliação do desempenho do Simulated Annealing (SA) e o Discrete Artificial Bee Colony (DABC). A resolução eficiente de um problema requer, em geral, a aplicação de diferentes métodos, e a afinação dos respetivos parâmetros. A afinação dos parâmetros pode permitir uma maior flexibilidade e robustez mas requer uma inicialização cuidadosa. Os parâmetros podem ter uma grande influência na eficiência e eficácia da pesquisa. A sua definição deve resultar de um cuidadoso esforço experimental no sentido da respectiva especificação. Foi usado, no âmbito deste trabalho de mestrado, para suportar a fase de parametrização das meta-heurísticas em análise, o planeamento de experiências de Taguchi. Da análise dos resultados, foi possível concluir que existem vantagem estatisticamente significativa no desempenho do DABC, mas quando analisada a eficiência é possível concluir que há vantagem do SA, que necessita de menos tempo computacional.

Optimization in its modern applications has strong interdisciplinary character, which is related to the necessity of integrating diverse techniques to approach complex problems. Scheduling is an important part of the production planning. Each time a production order is released, it is necessary to determine the resources that will be employed and in what sequence the tasks will be executed, to enhance a certain performance measure. While some enterprises still approach the scheduling problem with simple heuristic rules, advanced, automatized scheduling problems are becoming more popular. In this dissertation, the performance of the Simulated Annealing (SA) and the Discrete Artificial Bee Colony (DABC), in the resolution of the minimization of the weighted tardiness scheduling problem (ΣwjTj), were studied. In order to compare the performance of the two meta-heuristics, both were implemented in a software prototype. Even with the development of several meta-heuristics, including the Simulated Annealing (SA) and the Discrete Artificial Bee Colony (DABC), there is still uncertainty on what makes some meta-heuristics more efficient than others, without a comparative analyses. Moreover, meta-heuristics parameters impact on how the techniques will perform, on how effective and efficient is the exploration of solution space, while also requiring a careful revision. In this dissertation, the meta-heuristics were tuned with Taguchi experiments, which allow a comprehensive and efficient revision of the parameters. Through the analysis of the results, it was possible to conclude about a relevant statistical performance advantage of the DABC in the resolution of the minimization of the weighted tardiness problem (ΣwjTj), however, SA appeared more efficient, since it required less computational time than DABC in most instances of the problem