An algorithmic study of the machine reassignment problem

Abstract

O trabalho realizado propõe uma abordagem para resolver o problema de Reatribuição de Máquinas (Machine Reassignment Problem). O problema consiste em otimizar o uso de recursos computacionais dado um conjunto de processos que devem ser executados. Portanto, deve-se encontrar uma atribuição de processos a máquinas. Além disso, existem diversas restrições para aumentar a segurança e confiabilidade do sistema. O problema tem uma relevância prática bastante grande atualmente. Com um uso cada vez maior de computação nas nuvens (Cloud Computing), é importante a otimização dos recursos dessas grandes infra-estruturas computacionais. Este é um problema de otimização combinatorial NO-Difícil muito complexo. Portanto, é natural a escolha de um método heurístico para resolvê-lo de forma aproximada. A solução proposta é uma heurística baseada em Simulated Annealing que utiliza duas vizinhanças. Os resultados são bem satisfatórios, visto que soluções quase-ótimas são encontradas em pouco tempo. Além do método de solução proposto, obteve-se outras constribuições no decorrer do trabalho. Uma formulação com programação inteira foi proposta e implementada, sendo capaz de encontrar soluções ótimas para instâncias pequenas. Para avaliar a solução encontrada pelo método para instâncias grandes, foram desenvolvidos limitantes inferiores para a solução ótima. Os limitantes inferiores encontrados parecem ser bons comparados com a solução ótima na maioria dos casos. O problema de Reatribuição de Máquinas foi proposto no contexto do desafio ROADEF, um desafio internacional proposto pela Sociedade Francesa de Pesquisa Operacional. O problema apresentado para ser resolvido é sempre um problema com relevância no meio industrial. Este ano, quem propôs o problema foi a empresa Google, interessada em métodos para otimização de sua infra-estrutura computacional. Dentre as 83 equipes participantes, 30 classificaram-se para a fase final e a nossa equipe (representando a UFRGS) ficou em quarto lugar com uma versão preliminar do método proposto. Os resultados finais ainda não haviam sido publicados na data de publicação deste trabalho.

In this work, an approach to solve the Machine Reassignment Problem is proposed. The problem consists in optimizing the usage of computational resources given a set of processes that must be executed. Therefore, an assignment of processes to machines must be find. Besides, there are plenty of constraints for increasing safety and reliability of the system. The problem has an important practical relevance nowadays. The increasing usage of cloud computing concepts forces the resource optimization of these huge computational infrastructures. This is a very complex NP-Hard combinatorial optimization problem. Thus, the choice of an heuristic method is natural for solving the problem approximately. The proposed solution is an heuristic based on Simulated Annealing that uses two neighborhoods. The results are satisfactory since near-optimal solutions are found in less than five minutes. Besides the proposed algorithm, this work presents some other contributions. An integer programming formulation is proposed and implemented, being capable of finding optimal solutions for small instances of the problem. To evaluate the solutions found by the proposed method for big instances, a lower bound was developed. The lower bounds seem to be good approximations of the optimal solutions in most cases. The Machine Reassignment Problem was proposed in the context of the ROADEF / EURO Challenge, an international challenge proposed by the French Society of Operations Research. The presented problems always are important in Industry. This year, Google proposed the problem, interested in methods for optimizing its computational infrastructure. Among 83 participating teams, 30 have been classified for the final phase, and our team (representing UFRGS) ranked fourth with a preliminary version of the proposed method. The final results are not yet published as of the publication date of this work.