From the Magic Square to the Optimization of Networks of AGVs and from MIP to an Hybrid High Performance Optimization Algorithm

摘要

In a previous work we presented an algorithm inspired in the Artificial Intelligence and in the minimax optimization that imitates the human being in the solution of the magic square and we showed that in most cases its performance was better than the human's performance and even better than the performance of the best genetic algorithms to solve the magic square, in terms of number of changes. In this paper we adapt and transform this algorithm to solve the optimization of an AGVs network problem, using as a test case 9 workstations in fixed positions and 9 operations to be executed, and the optimization problem is translated in the search of which of the 9! possible manners to distribute 9 operations by the 9 workstations that minimizes the total production time for a given plan of production. This gradual process of adaptation and transformation resulted in an evolutionary hybrid algorithm with high performances, with a little bit of Tabu Search and a little bit of genetic algorithm. In 1000 successive runs, with the two tabu flags On, it never failed in the search of one of the 4 optimal solutions and never took more than 3000 iterations and 9!= 362880. As a final validation test, using random search, in 1000 runs it never reached the optimal solution at the end of 100000 iterations. Finally we considered the more general case where the number of workstations is greater than the number of operations, and so there are some workstations that make the same operation, and we will have a layout with repetitions. This turns the problem more complex since when a product has operations that are executed by various workstations we must search all the possible combinations and find the average distance over all possible trajectories associated to a product. Furthermore the generation of all 'permutations with repetitions' is more complex and in the literature there are no published algorithm to generate this type of combinatorial entities. The Mixed Integer Programming approach proves to be impractical even for a simple test case of two products defined as sequences of four operations since the implementation of the division of the total distance over all trajectories that implement a product by their number turns the MIP model very big and combinatorial explosive. Again our algorithm adapted to layouts with repetitions presented very good results for this simple test case of 9 machines, 4 operations and 2 products.