Fútbol strategies applied to optimize combinatortial problems to create efficent results – the soccer heuristic

Abstract

Heuristics are often implemented to find better solutions to computationally challenging problems. Heuristics use varying techniques to search for quality solutions. Several optimization heuristics have drawn inspiration from real world practices. Ant colony optimization mimics ants in search of food. Genetic algorithms emulate traits being passed from a parent to a child. Simulated annealing imitates annealing metal. This thesis presents a new variable neighborhood search optimization heuristic, fútbol Strategies applied to Optimize Combinatorial problems to Create Efficient Results, which is called the SOCCER heuristic. This heuristic mimics fútbol and the closest player to the ball performs his neighborhood search and players are assigned different neighborhoods. The SOCCER heuristic is the first application of variable neighborhood search heuristic that uses a complex structure to select neighborhoods. The SOCCER heuristic can be applied to a variety of optimization problems. This research implemented the SOCCER heuristic for job shop scheduling problems. This implementation focused on creating a quality schedule for a local limestone company. A small computational study shows that the SOCCER heuristic can quickly solve complex job shop scheduling problems with most instances finishing in under an half an hour. The optimized schedules reduced the average production time by 7.27%. This is roughly a 2 day decrease in the number of days required to produce a month’s worth of orders. Thus, the SOCCER heuristic is a new optimization tool that can aid companies and researchers find better solutions to complex problems.