Integration of genetic algorithms for knowledge-based multi-objective scheduling problems in the DéjàVu class library

Abstract

Real-world scheduling problems are confronted with conflicting constraints and objective functions. Scheduling problems are known as NP-Hard problems, i.e. there is no algorithm that solves them in polynomial time. In the artificial intelligence community many approaches are used to solve these problems. In the last three decades modern approaches from artificial intelligence were used. These approaches are known as meta-heuristic search methods, such as simulated annealing, tabu search, evolutionary algorithms, random search, and neural networks. In this thesis we use evolutionary algorithms to try to solve multi-objective production scheduling problems in high-grade steel making. We focus on the use of genetic algorithms, which are inspired from the Darwinian theory of the evolution in nature and are some of the most used algorithms in the evolutionary computation community. Genetic algorithms are integrated in a framework called DejaVu class library, which is specially designed for the production scheduling problems in high-grade steel making. DejaVu class library is based on object oriented paradigm, where other improvement methods like tabu search are implemented. In this thesis genetic algorithms try to improve the multi-objective scheduling problem and compare the result with tabu search method. As application a steel demo from the steel industry is used, which was inspired by real-world steel making scheduling problems. The Unified Modeling Language (UML), a modeling language for software design, is used to design the integration of genetic algorithms in the DejaVu Class library. Numerous representations of a schedule in a chromosome and the corresponding operators are discussed. Several genetic algorithms parameters like population size, crossover operators, mutation operators, crossover and mutation probability are changed to see the influence of these operators on the performance of genetic algorithms. In this thesis we extended the DejaVu Class library to integrate genetic algorithms and to do experiments to see how effective genetic algorithms are in solving production scheduling problems in high-grade steel making. In the experiments we used two kinds of genetic algorithms, the simple genetic algorithm and the steady state genetic algorithm. We compared the results with the tabu search method and we proved that if we use the appropriate parameters for genetic algorithms we get better results then when using the tabu search method.

Praktische Anwendungen des Schedulingproblems sind oft mit widerspruechlichen Bedingungen und Zielfunktionen konfrontiert.Fragestellungen werden auch als NP-schweren Probleme bezeichnet, dh. es gibt keinen Algorithmus der dieses Problem in polynomialer Zeit loest. Im Bereich der kuenstlichen Intelligenz gibt es viele Ansaetze dieses Problem zu loesen. In den letzten drei Jahrzehnten wurden viele Ansaetze der kuenstlichen Intelligenz verwendet. Diese Ansaetze werden unter dem Begriff metaheuristischen suche zusammengefasst, dazu gehoeren Simulated annealing, tabu search, evolutionaere Algorithmen, Zufallsuche und Neurale Netze. In dieser Dissertation verwenden wir evolutionaere Algorithmen um multikriterielle scheduling Probleme im Stahlerzeugungsprozess zu loesen. Wir verwenden genetische Algorithmen, die aus der Darwinschen Evolutionstheorie entstanden sind und weit verbreitet im Bereich der evolutionaeren Algorithmen sind. Die genetische Algorithmen werden in einer Klassenbibliothek mit dem Namen DejaVu class library" integriert, welche fuer Schedulingprobleme in der Stahlerzeugung konzipiert wurde. Die DejaVu class library ist objekt-orientiert ausgerichtet und beinhaltet Methoden wie tabu-search. In dieser Dissertation versuchen genetische Algorithmen multikriterielle scheduling Probleme zu loesen und die Ergebnisse mit tabu-search zu vergleichen. Als Anwendung wird eine "steel-demo" der Stahlindustrie verwendet, die den realen Bedingungen der Stahlerzeugung entspricht. Zur Integration der genetischen Algorithmen in die "DejaVu class library" wird die "Unified Modeling Language" (UML) verwendet. Mehrere Repraesentationen eines "schedules" in einem Chromosome und dessen Operatoren werden diskutiert. Einige Parameter der genetischen Algorithmen wie zum Beispiel Groesse der Population, "crossover"-, Mutations- Operatoren, Crossover- und Mutationswahrscheinlichkeit wurden modifiziert, um den Einfluss dieser Operatoren auf die Qualitaet der genetischen Operatoren zu untersuchen. In dieser Arbeit wurde die DejaVu class library" erweitert, um genetische Algorithmen zu integrieren und zu untersuchen, wie effektiv genetische Algorithmen verwendet werden koennen, um "scheduling Probleme" im Stahlerzeugungsprozess zu loesen. In den Experimenten verwendeten wir zwei Arten von genetischen Algorithmen: "simple genetic algorithm" und "steady state genetic algorithm". Wir verglichen die Ergebnisse mit der "tabu search " Methode und bewiesen, dass unter Zuhilfenahme der passenden Parameter fuer die genetischen Algorithmen bessere Resultate, als mit "tabu search" zu erreichen sind.