Solving the production leveling problem with memetic algorithms

Abstract

In dieser Diplomarbeit präsentieren wir sowohl einen Memetischen als auch Genetischen Algorithmus, um das kürzlich präsentierte Production Leveling Problem erstmals evolutionär zu lösen. Das Production Leveling Problem ist ein NP-schweres kombinatorisches Optimierungsproblem, das sich mit der Zuordnung von Aufträgen zu Produktionsperioden beschäftigt. Das Ziel ist die Aufträge gleichmäßig über die Perioden und bestimmte Ressourcen zu verteilen, während Perioden- und Ressourcen-Limits und Prioritäten eingehalten werden. Das Problem liegt im Bereich der mittelfristigen Planung, ein Gebiet, in dem die Bestellungen erst gruppiert werden, um dann während der kurzfristigen Planung konkret für die Periode geplant zu werden. Wir präsentieren eine Lösungsdarstellung basierend auf der bisherigen Definition und verwenden die entsprechende Fitness-Funktion mit problemspezifischen Optimierungen. Sieben Konstruktionsheuristiken werden implementiert, diskutiert und bezüglich Qualität und Diversität der erzeugten Lösungen analysiert. Während der Diversitätsanalyse wurde neben den bereits etablierten Metriken der ”allele coverage” und ”solution equality”, der Begriff des ”Extended Jaccard Index” eingeführt, um die Diversität der Mengen beschreiben zu können, die durch die Heuristiken erzeugt werden. Weiters werden drei ”Selection” Operatoren, fünf ”Crossover” Operatoren und vier ”Mutation” Operatoren implementiert und besprochen. Vier ”Local Search” Operatoren werden für die Verwendung im Memetischen Algorithmus vorgestellt. Schließlich werden noch drei ”Replacement” Ansätze diskutiert. Nachdem die Operatoren und deren Potential besprochen wurden, werden die vielversprechendsten für das Parameter-Tuning übernommen. Um während des Tunings gute Lösungen zu finden, ohne die Algorithmen auf die Testdaten anwenden zu müssen, werden 2000 Trainingsdaten unter Verwendung einer Heuristik aus vorherigen Arbeiten erzeugt. Für einen faireren Vergleich, der aufgrund von Systemunterschieden erschwert ist, wird ein ”Simulated Annealing” Ansatz implementiert und getuned. Der Hauptfokus der Arbeit liegt auf dem Vergleich und der Bewertung des Memetischen und des Genetischen Algorithmus. Dafür vergleichen wir zuerst die Algorithmen, die im Zuge dieser Arbeit entstanden sind und dann die Ergebnisse mit denen aus der Literatur. Die Ergebnisse zeigen, dass der Genetische Algorithmus am besten abschneidet, dicht gefolgt vom Memetischen Algorithmus. Die beiden evolutionären Algorithmen liefern für das Set der realistischen Instanzen Ergebnisse innerhalb einer 5% ”optimality gap”. Zusätzlich lösen sie alle der optimal lösbaren Instanzen ohne ”hard constraint”-Verstoß und sogar 4 der 50 optimal, beides Leistungen die, soweit uns bewusst ist, bisher nicht mit Metaheuristiken erreicht wurden.

In this thesis we develop and present a memetic and genetic algorithm for solving the Production Leveling Problem introduced recently, providing the first evolutionary approach to this problem. The Production Leveling Problem is an NP-hard combinatorial optimisation problem about assigning orders to production periods in such a way that their demand across those periods and certain resources is balanced while also taking into account demand limits per period and per resource. It is a problem situated in the realm of medium-term planning, an area where orders are first grouped to then be scheduled more concretely during short-term planning. We propose a solution representation based on the previous problem definition and implement the fitness function accordingly, introducing problem specific optimisations. Seven construction heuristics are implemented and discussed and further analysed in terms of quality and diversity of the solutions they create. When discussing diversity, in addition to the already established measures of allele coverage and solution equality, the notion of the Extended Jaccard Index is introduced to gain insight into how diverse the sets are that the heuristics create. Furthermore, three selection operators, five crossover operators and four mutation operators are implemented, reviewed and discussed. Four local search strategies are presented for the use in the memetic algorithm. Lastly, we look at three different approaches for replacement. After reviewing the operators and their potential they are reduced to a more compact set from which the best configurations are then chosen during hyperparameter tuning. In order to find good solutions without applying the algorithm to the test data provided in existing literature, a set of 2000 training instances is generated based on a random instance generator discussed in earlier work. For the sake of comparison and due to system differences, we also implement and tune a simulated annealing approach. The main focus of the thesis is the comparison and review of the memetic and the genetic algorithm developed. For that we first compare the algorithms introduced and tuned during this thesis amongst themselves and then compare their results with the findings presented in the literature. We find that the genetic algorithm performs best amongst the algorithms developed during this thesis, with the memetic algorithm trailing only slightly behind. On the set of realistic instances both evolutionary approaches manage to mostly find solutions within a 5% optimality gap. Additionally, they manage to solve the entire set of perfectly solvable test instances without hard constraint violations, and even solve four of the 50 instances to optimality, both feats that, to the best of our knowledge, have not been achieved thus far using metaheuristic approaches.