Projekt Scheduling GA: effiziente Datenstruktur für das Chromosom

Question

Dies ist eine Fortsetzung meiner vorherigen Frage, die war, wie man ein einzelnes Chromosom darstellt, ich fand einen Weg, wie, aber ich habe ein Problem mit, wie man dies im Gedächtnis darstellt.

Ich schreibe eine Projektplanung Optimierung Bibliothek, eine besondere Art eines Job Shop Problem. Um es einfach zu halten, funktioniert mein Algorithmus nur mit Worker ist die einzige Ressource für das Projekt (später sollte ich in der Lage sein, mehr Ressourcen hinzuzufügen), und es gibt nur 2 Arten von Einschränkungen (später wird es mehr Einschränkungen geben auch) bis jetzt:

1) Jeder Arbeiter hat eine Beschränkung auf welche Projekte er arbeiten kann. Nur einige Arbeiter sind qualifiziert, an demselben Projekt zu arbeiten (zum Beispiel: W1, W3, W7-Arbeiter können an Projekt P2 arbeiten; W2, W3, W5 können an Projekt P3 arbeiten; usw.), aber derselbe Arbeiter kann geschickt arbeiten in mehreren Projekten und darf zu verschiedenen Zeiten an mehreren Projekten arbeiten (zum Beispiel: W1 arbeitet an P1 5 Tage [oder sogar Stunden] hintereinander, wechselt dann für 4 Tage zu P2, dann kommt er zurück zu P1, etc)

2) Jeder Arbeitnehmer eine Einschränkung auf hat, wie viele Stunden er jeden Tag arbeiten kann - dies ein Arbeitnehmer Effizienz

zu beginnen, habe ich einen einfachen Zeitplan bestehend aus nur vier Projekten darstellen sollte und 4 Arbeiter.

PROJEKTE:

• P1; beginnend: Mai, der 1.; Frist: 30 Tage; Arbeitsstunden benötigt: 300
• P2; beginnend: 1. Juli; Frist: 60 Tage; Arbeitsstunden benötigt: 150
• P3; beginnend: Mai, der 15.; Frist: 45 Tage; Arbeitsstunden benötigt: 50
• P4; ab: 20. April; Frist: 20 Tage; Arbeitsstunden benötigt: 150

ARBEITNEHMER:

• W1; Effizienz: 10h/Tag; verfügbar für Projekte: P1, P2, P3, P4
• W2; Effizienz: 5h/Tag; verfügbar für Projekte: P1, P3
• W3; Effizienz: 8h/Tag; verfügbar für Projekte: P1, P4
• W4; Effizienz: 6h/Tag; verfügbar für Projekte: P2, P4

Mit einem Problem wie dieses sein Setup, fand ich ein einziges Chromosom (Einzel Zeitplan) sollte darstellen, die Arbeiter für jede einzelne Stunde auf welchem ​​Projekt arbeitet, bis das letzte Projekt ist fertig.

In diesem Beispiel sollte der Zeitplan vom 20. April bis zum 1. Juli + 60 Tage gehen. Das sind also insgesamt 130 Tage x 12 Stunden = 1560 Stunden Slots. In jeder Steckplatz sollte ein Arbeiter mit dem zugewiesenen Projekt für diesen Stundensteckplatz sein.

Was wäre die richtige Datenstruktur für den Slot (es scheint ineffizient, neue Worker-Objekt für jeden Slot zuzuordnen?), Und das ist in der Lage für Crossover und Mutation?

Answer 1

Sie müssen sicherlich nichts zuweisen, sondern ein Array. Mit Ihren 4 Projekten und 4 Arbeitern können Sie alle 4 * 4 Kombinationen vorbelegen und Referenzen auf sie in Ihrem Chromosom speichern.

Dies ist sogar mit Hunderten von Projekten und Mitarbeitern machbar. Sie könnten stattdessen ihre Indizes speichern, und Sie könnten sie sogar in einen längeren Integer-Typ packen (mit bis zu zwei Milliarden Projekten und Arbeitern, würde ein long tun).

Aber es ist eine ziemlich vorzeitige und wahrscheinlich nutzlose Optimierung, da andere Operationen höchstwahrscheinlich die Laufzeit dominieren werden.