Genetische Algorithmusplanung - Genetic algorithm scheduling

Der genetische Algorithmus ist eine operative Forschungsmethode , mit der Planungsprobleme in der Produktionsplanung gelöst werden können .

Bedeutung der Produktionsplanung

Um wettbewerbsfähig zu sein, müssen Unternehmen Ineffizienzen minimieren und die Produktivität maximieren. In der Fertigung hängt die Produktivität inhärent davon ab, wie gut das Unternehmen die verfügbaren Ressourcen optimieren, Abfall reduzieren und die Effizienz steigern kann. Es kann äußerst komplex sein, den besten Weg zu finden, um die Effizienz in einem Herstellungsprozess zu maximieren. Selbst bei einfachen Projekten gibt es mehrere Eingaben, mehrere Schritte, viele Einschränkungen und begrenzte Ressourcen. Im Allgemeinen besteht ein ressourcenbeschränktes Planungsproblem aus:

  • Eine Reihe von Jobs, die ausgeführt werden müssen
  • Eine begrenzte Anzahl von Ressourcen, mit denen jeder Auftrag ausgeführt werden kann
  • Eine Reihe von Einschränkungen, die erfüllt sein müssen
    • Zeitliche Einschränkungen - das Zeitfenster zum Abschließen der Aufgabe
    • Verfahrensbeschränkungen - Die Reihenfolge, in der jede Aufgabe ausgeführt werden muss
    • Ressourcenbeschränkungen - ist die verfügbare Ressource
  • Eine Reihe von Zielen zur Bewertung der Planungsleistung

Eine typische Werkseinstellung ist ein gutes Beispiel dafür, wo geplant werden muss, welche Aufträge auf welchen Maschinen, von welchen Mitarbeitern, in welcher Reihenfolge und zu welcher Zeit ausgeführt werden müssen.

Verwendung von Algorithmen bei der Planung

Bei sehr komplexen Problemen wie der Planung ist kein Weg bekannt, um zu einer endgültigen Antwort zu gelangen. Daher suchen wir danach, um eine "gute" Antwort zu finden. Planungsprobleme verwenden meistens heuristische Algorithmen, um nach der optimalen Lösung zu suchen. Heuristische Suchmethoden leiden darunter, dass die Eingaben komplexer und vielfältiger werden. Diese Art von Problem ist in der Informatik als NP-Hard- Problem bekannt. Dies bedeutet, dass keine Algorithmen bekannt sind, um eine optimale Lösung in der Polynomzeit zu finden.

Abb. 1. Vorrang bei der Planung

Genetische Algorithmen eignen sich gut zur Lösung von Produktionsplanungsproblemen , da genetische Algorithmen im Gegensatz zu heuristischen Methoden eher mit einer Population von Lösungen als mit einer einzelnen Lösung arbeiten. In der Produktionsplanung besteht diese Population von Lösungen aus vielen Antworten, die unterschiedliche, manchmal widersprüchliche Ziele haben können. In einer Lösung können wir beispielsweise einen Produktionsprozess optimieren, der in kürzester Zeit abgeschlossen werden soll. In einer anderen Lösung optimieren wir möglicherweise für eine minimale Anzahl von Fehlern. Wenn wir die Geschwindigkeit, mit der wir produzieren, erhöhen, können die Fehler in unserem Endprodukt zunehmen.

Wenn wir die Anzahl der Ziele erhöhen, die wir erreichen möchten, erhöhen wir auch die Anzahl der Einschränkungen für das Problem und erhöhen in ähnlicher Weise die Komplexität. Genetische Algorithmen sind ideal für diese Art von Problemen, bei denen der Suchraum groß und die Anzahl der möglichen Lösungen klein ist.

Anwendung eines genetischen Algorithmus

Abb. 2 A. Beispiel Zeitplangenom

Um einen genetischen Algorithmus auf ein Planungsproblem anzuwenden, müssen wir ihn zuerst als Genom darstellen. Eine Möglichkeit, ein Planungsgenom darzustellen, besteht darin, eine Folge von Aufgaben und die Startzeiten dieser Aufgaben relativ zueinander zu definieren. Jede Aufgabe und ihre entsprechende Startzeit repräsentiert ein Gen.

Eine bestimmte Abfolge von Aufgaben und Startzeiten (Gene) repräsentiert ein Genom in unserer Population. Um sicherzustellen, dass unser Genom eine praktikable Lösung ist , müssen wir darauf achten, dass es unseren Prioritätsbeschränkungen entspricht. Wir generieren eine anfängliche Grundgesamtheit unter Verwendung zufälliger Startzeiten innerhalb der Prioritätsbeschränkungen. Mit genetischen Algorithmen nehmen wir dann diese anfängliche Population und kreuzen sie, indem wir Genome mit einer geringen Zufälligkeit (Mutation) kombinieren. Die Nachkommen dieser Kombination werden anhand einer Fitnessfunktion ausgewählt , die eine oder mehrere unserer Einschränkungen umfasst, z. B. die Minimierung der Zeit und die Minimierung von Fehlern. Wir lassen diesen Prozess entweder für eine vorab festgelegte Zeit oder bis wir eine Lösung finden, die unseren Mindestkriterien entspricht. Insgesamt hat jede nachfolgende Generation eine höhere durchschnittliche Fitness, dh sie benötigt weniger Zeit mit höherer Qualität als die vorhergehenden Generationen. Bei Planungsproblemen müssen wir wie bei anderen genetischen Algorithmuslösungen sicherstellen, dass wir keine Nachkommen auswählen, die nicht realisierbar sind, wie z. B. Nachkommen, die gegen unsere Prioritätsbeschränkung verstoßen. Möglicherweise müssen wir natürlich weitere Fitnesswerte hinzufügen, z. B. die Minimierung der Kosten. Jede hinzugefügte Einschränkung vergrößert jedoch den Suchraum erheblich und verringert die Anzahl der Lösungen, die gut übereinstimmen.

Siehe auch

Literaturverzeichnis

  • Wall, M., Ein genetischer Algorithmus für die ressourcenbeschränkte Planung (PDF)
  • Lim, C.; Sim, E., Produktionsplanung in einer Produktions- / Wiederaufarbeitungsumgebung unter Verwendung eines genetischen Algorithmus


Externe Links