Implementieren einer dynamischen Warteschlange mit mehreren Zeitachsen

Question

Einführung

Ich möchte eine dynamische Mehrfach-Timeline-Warteschlange implementieren. Der Kontext hier ist allgemeine Terminplanung.

Was ist eine Timeline-Warteschlange?

Das ist noch einfach: Es handelt sich um eine Zeitachse von Aufgaben, bei der jedes Ereignis seine Start- und Endzeit hat. Aufgaben sind als Jobs gruppiert. Diese Gruppe von Aufgaben muss ihre Reihenfolge bewahren, kann aber als Ganzes in der Zeit verschoben werden. Zum Beispiel könnte es so dargestellt werden:

 --t1--   ---t2.1-----------t2.2-------
 '    '   '        '                  '
20    30  40       70                120 

Ich würde dies als eine Heap-Warteschlange mit einigen zusätzlichen Einschränkungen implementieren. Das Python sched Modul hat einige grundlegende Ansätze in diese Richtung.

Definition mehrfache Timeline-Warteschlange

Ein Warteschlange steht für eine Ressource und eine Ressource wird von einer Aufgabe benötigt. Grafisches Beispiel:

R1  --t1.1----- --t2.2-----      -----t1.3--    
            /  \                /
R2  --t2.1--     ------t1.2-----

Erklärung "dynamisch"

Es wird interessant, wenn eine Aufgabe eine der mehreren Ressourcen verwenden kann. Eine zusätzliche Einschränkung besteht darin, dass aufeinanderfolgende Aufgaben, die auf derselben Ressource ausgeführt werden können, dieselbe Ressource verwenden müssen.

Beispiel: Wenn (aus obigem Beispiel) die Aufgabe t1.3 auf R1 oder R2 ausgeführt werden kann, sollte die Warteschlange wie folgt aussehen:

R1  --t1.1----- --t2.2-----      
            /  \                
R2  --t2.1--     ------t1.2----------t1.3--    

Funktionalität (in Prioritätsreihenfolge)

• ErstesFreiesFeld(Dauer, Start): Finde den ersten freien Zeitschlitz ab Start, in dem es freie Zeit für Dauer gibt (siehe detaillierte Erklärung am Ende).
• WarteschlangeEinreihen eines Jobs so früh wie möglich auf den mehreren Ressourcen unter Berücksichtigung der Einschränkungen (hauptsächlich: richtige Reihenfolge der Aufgaben, aufeinanderfolgende Aufgaben auf derselben Ressource) und Verwendung von ErstesFreiesFeld.
• Platzieren eines Jobs zu einer bestimmten Zeit und Verschieben des Endes nach hinten
• Löschen eines Jobs
• Neuberechnen: Nach dem Löschen überprüfen, ob einige Aufgaben früher ausgeführt werden können.

Schlüsselfrage

Der Punkt ist: Wie kann ich diese Informationen effizient darstellen, um die Funktionalität effizient bereitzustellen? Die Umsetzung liegt bei mir ;-)

Update: Ein weiterer zu berücksichtigender Punkt: Die typischen Intervallstrukturen konzentrieren sich auf "Was ist an Punkt X?" In diesem Fall ist jedoch das einfügen und somit die Frage "Wo ist der erste leere Slot für Dauer D?" viel wichtiger. Ein Segment-/Intervallbaum oder etwas in dieser Richtung ist wahrscheinlich nicht die richtige Wahl.

Um den Punkt mit den freien Slots weiter zu erläutern: Aufgrund der Tatsache, dass wir mehrere Ressourcen und die Einschränkung gruppierte Aufgaben haben, können freie Zeitslots für einige Ressourcen vorhanden sein. Einfaches Beispiel: t1.1 läuft auf R1 für 40 und dann t1.2 läuft auf R2. Es gibt also ein leeres Intervall von [0, 40] auf R2, das durch den nächsten Job gefüllt werden kann.

---

Update 2: Es gibt einen interessanten Vorschlag in einer anderen SO-Frage. Wenn jemand ihn auf mein Problem übertragen und zeigen kann, dass er für diesen Fall funktioniert (insbesondere unter Berücksichtigung mehrerer Ressourcen), wäre dies wahrscheinlich eine gültige Antwort.

Answer 1

class Task:
    name=''
    duration=0
    resources=list()

class Job:
    name=''
    tasks=list()

class Assignment:
    task=None
    resource=None
    time=None

class MultipleTimeline:
    assignments=list()
    def enqueue(self,job):
        pass
    def put(self,job):
        pass
    def delete(self,job):
        pass
    def recalculate(self):
        pass

Ist dies ein erster Schritt in die Richtung, in die Sie suchen, d.h. ein Datenmodell in Python?

Aktualisierung:

Hierbei mein effizienteres Modell:

Es platziert alle Aufgaben in einer verketteten Liste, die nach Endzeit sortiert ist.

class Task:
    name=''
    duration=0    # die Menge an Arbeit, die erledigt werden muss
    resources=0   # Bitmap, die angibt, welche Ressourcen diese Aufgabe verwendet
# die folgenden Variablen werden nur verwendet, wenn die Aufgabe geplant ist
    next=None     # die nächste geplante Aufgabe nach Endzeit
    resource=None # die Ressource, auf der diese Aufgabe geplant ist
    gap=None      # die Zeitmenge, bis die nächste geplante Aufgabe auf dieser Ressource beginnt

class Job:
    id=0
    tasks=list() # die Task-Instanzen dieses Jobs in Reihenfolge

class Resource:
    bitflag=0       # ein Bit-Flag, das bitweise mit Task.resources arbeitet
    firsttask=None  # die erste Task-Instanz, die auf dieser Ressource geplant ist
    gap=None        # die Zeitmenge, bis die erste Aufgabe beginnt

class MultipleTimeline:
    resources=list()
    def FirstFreeSlot():
            pass
    def enqueue(self,job):
        pass
    def put(self,job):
        pass
    def delete(self,job):
        pass
    def recalculate(self):
        pass

Aufgrund der Aktualisierungen durch enqueue und put habe ich mich entschlossen, keine Bäume zu verwenden. Aufgrund von put, der Aufgaben in der Zeit verschiebt, habe ich beschlossen, keine absoluten Zeiten zu verwenden.

FirstFreeSlot gibt nicht nur die Aufgabe mit dem freien Slot zurück, sondern auch die anderen laufenden Aufgaben mit ihren Endzeiten.

enqueue funktioniert wie folgt: Wir suchen nach einem freien Slot mit FirstFreeSlot und planen die Aufgabe hier. Wenn genügend Platz für die nächste Aufgabe ist, können wir sie auch planen. Wenn nicht: Schauen Sie sich die anderen laufenden Aufgaben an, ob sie freien Platz haben. Wenn nicht: Führen Sie FirstFreeSlot mit Parametern dieser Zeit und laufenden Aufgaben aus.

Verbesserungen: Wenn put nicht sehr oft verwendet wird und enqueue von Zeit null aus durchgeführt wird, könnten wir die sich überschneidenden Aufgaben nachverfolgen, indem wir ein dict() pro Aufgabe einschließen, das die anderen laufenden Aufgaben enthält. Dann ist es auch einfach, eine list() pro Ressource zu führen, die die geplanten Aufgaben mit absoluter Zeit für diese Ressource enthält, sortiert nach Endzeit. Es werden nur die Aufgaben einbezogen, die größere Zeitlücken als zuvor haben. Jetzt können wir leichter einen freien Slot finden.

Fragen: Müssen Aufgaben, die von put geplant sind, zu diesem Zeitpunkt ausgeführt werden? Wenn ja: Was ist, wenn eine andere Aufgabe, die durch put geplant werden soll, sich überschneidet? Führen alle Ressourcen eine Aufgabe gleich schnell aus?

Answer 2

Lassen Sie uns uns zunächst auf den einfachsten Fall beschränken: Finden Sie eine geeignete Datenstruktur, die eine schnelle Implementierung von FirstFreeSlot() ermöglicht.

Die freien Zeitfenster liegen in einem zweidimensionalen Raum: Eine Dimension ist die Startzeit s, die andere ist die Länge d. FirstFreeSlot(D) beantwortet effektiv die folgende Abfrage:

min s: d >= D

Wenn wir uns s und d als kartesischen Raum vorstellen (d=x, s=y), bedeutet dies, den niedrigsten Punkt in einer Teilfläche begrenzt durch eine vertikale Linie zu finden. Ein Quad-Tree, vielleicht mit einigen Zusatzinformationen in jedem Knoten (nämlich min s über alle Blätter), wird helfen, diese Abfrage effizient zu beantworten.

Für Enqueue() angesichts von Ressourcenbeschränkungen sollten Sie in Betracht ziehen, für jede Ressource einen separaten Quad-Tree zu führen. Der Quad-Tree kann auch Abfragen wie beantworten

min s: s >= S & d >= D

(erforderlich zur Einschränkung der Startdaten) auf ähnliche Weise: Jetzt wird ein Rechteck (oben links offen) abgeschnitten, und wir suchen nach min s in diesem Rechteck.

Put() und Delete() sind einfache Update-Operationen für den Quad-Tree.

Recalculate() kann durch Delete() + Put() implementiert werden. Um Zeit für unnötige Operationen zu sparen, definieren Sie ausreichende (oder idealerweise ausreichende + notwendige) Bedingungen, um eine Neuabrechnung auszulösen. Das Beobachtermuster könnte hier hilfreich sein, aber denken Sie daran, die Aufgaben für die Neuplanung in eine FIFO-Warteschlange oder eine nach Startzeit sortierte Prioritätswarteschlange einzufügen. (Sie möchten die aktuelle Aufgabe fertig neu planen, bevor Sie zur nächsten übergehen.)

Allgemeiner gesagt, bin ich sicher, dass Sie sich bewusst sind, dass die meisten Arten von Terminplanungsproblemen, insbesondere solche mit Ressourcenbeschränkungen, zumindest NP-vollständig sind. Erwarten Sie also keinen Algorithmus mit einer anständigen Laufzeit im Allgemeinen Fall.

Answer 3

Nachdem ich eine Weile darüber nachgedacht habe, denke ich, dass ein Segmentbaum möglicherweise besser geeignet ist, um diese Zeitachse zu modellieren. Das Job-Konzept entspricht einer LIST-Datenstruktur.

Ich gehe davon aus, dass die Aufgabe folgendermaßen modelliert werden kann (PSEUDO-CODE). Die Reihenfolge der Aufgaben im Job kann durch die start_time sichergestellt werden.

class Task:
    name=''

    _seg_starttime=-1; 
    # Dies ist die früheste Zeit, zu der die Aufgabe im Segmentbaum starten kann,
    # in vielen Fällen kann dies auf -1 gesetzt werden, was bedeutet, dass sie nach ihrem Vorgänger startet.
    # Dies wird durch den Vorgänger im Segmentbaum bestimmt.
    # Wenn dies nicht gleich -1 ist, bedeutet dies, dass diese Aufgabe angegeben ist, um zu dieser Zeit zu starten.
    # Wenn der Vorgänger sich ändert, muss diese Information berücksichtigt werden.

    _job_starttime=0; 
    # Dies ist die früheste Zeit, zu der die Aufgabe im Jobablauf starten kann, begrenzt durch die Jobdefinition

    _dauer=0;      
    # Dies ist die Zeit, die die Aufgabe benötigt, um ausgeführt zu werden

    def get_segstarttime():
       if _seg_starttime == -1 :
           return VORHERIGER_KNOTEN.get_segstarttime() + _dauer
       return __seg_startime + _dauer

    def get_jobstarttime():
       return VORHERIGER_JOB.get_endzeit()

    def get_startzeit():
       return max( get_segstarttime(), get_jobstarttime() )

• Einreihen bedeutet lediglich das Anhängen eines Taskknotens an den Segmentbaum, beachte, dass _seg_startime auf -1 gesetzt ist, um anzuzeigen, dass er unmittelbar nach seinem Vorgänger gestartet wird
• Einsetzen fügt ein Segment in den Baum ein, das Segment wird durch start_time und duration angezeigt.
• Löschen entfernt das Segment im Baum, aktualisiert den Nachfolger gegebenenfalls (falls der gelöschte Knoten einen _seg_start_time enthält)
• Neu berechnen Beim erneuten Aufrufen von get_starttime() wird direkt die früheste Startzeit abgerufen.

Beispiele (ohne Berücksichtigung der Jobeinschränkung)

                  t1.1( _segst = 10, du = 10 )
                      \
                      t2.2( _segst = -1, du = 10 ) bedeutet st=10+10=20
                        \
                        t1.3 (_segst = -1, du = 10 ) bedeutet st = 20+10 = 30

Wenn wir einsetzen:

                    t1.1( _segst = 10, du = 10 )
                        \
                        t2.2( _segst = -1, du = 10 ) bedeutet st=20+10=30
                        /  \
t2.3(_segst = 20, du = 10)  t1.3 (_segst = -1, du = 10 ) bedeutet st = 30+10 = 30

Wenn wir t1.1 löschen:

                      t2.2( _segst = 20, du = 10 ) 
                        \
                        t1.3 (_segst = -1, du = 10 ) bedeutet st = 20+10 = 30

Jede Ressource kann durch 1 Instanz dieses Intervallbaums dargestellt werden. Beispiel:

Aus der Perspektive des Segmentbaums (Zeitachse):

t1.1                      t3.1
  \                        / \
  t2.2                  t2.1  t1.2

Aus der Jobsicht:

t1.1 <- t1.2
t2.1 <- t2.2
t3.1

t2.1 und t2.2 sind über eine verkettete Liste verbunden, wie angegeben: t2.2 erhält seinen _sg_start_time aus dem Segmentbaum, erhält seine _job_start_time aus der verketteten Liste, vergleicht die beiden Zeiten und die tatsächlich früheste Zeit, zu der es ausgeführt werden kann, kann abgeleitet werden.

Answer 4

Ich habe schließlich nur eine einfache Liste für meine Warteschlangen-Elemente verwendet und eine In-Memory-SQLite-Datenbank für die Speicherung der leeren Slots, da mehrdimensionale Abfragen und Aktualisierungen mit SQL sehr effizient sind. Ich muss nur die Felder start, duration und index in einer Tabelle speichern.