Algorithmus gesucht Blöcke auf einer Zeitachse zu Verteilen

Hallo Forum,

ich suche einen möglichst einfachen Algorithmus. Die Problemstellung ist die folgende:

Ich habe eine Zeitachse. Auf dieser Zeitachse möchte ich "Blöcke" (zB. zeitliche tätigkeiten)verteilen.
Nun ist es so, dass die Blöcke sich in einem definierten Zeitfenster befinden dürfen.(Zeitfenster größer alsein block).

Ich möchte gerne diese Blöcke innerhalb der vorgesehenen Zeitfenster derart verteilen, dass es möglichst zu keinen überschneidungen der Blöcke kommt.

Gibt es da einen einfachen Algorithmus?

Beispiel:

Block 1 hat die länge 3h, das Zeitfenster zu diesem Block beträgt 12-16 Uhr
Block 2 hat die länge 4h, das Zeitfenster zu diesem Block beträgt 15-20 Uhr
[...]

Ich möchte diese derart anordnen, sodass zeitliche Überschneidungen möglichst minimiert (wenn möglich: verhindert werden)

Allesquatsch

czi schrieb:

Gibt es da einen einfachen Algorithmus?

Gibt es da noch irgendwelche Restriktionen oder Zielfunktionen?

Muss es nur passen oder ist da was zu optimieren? Muss das Optimum gefunden werden oder nur eine gute Lösung in bestimmter Zeit? Sind die Anzahl der Fenster begrenzt oder zu minimieren? Ist das Problem vollständig zu Beginn definiert?

So aus dem Bauch heraus hätte ich - mit meinem momentanen Verständnis - gesagt: Fenster und Blöcke absteigend sortieren, die größten Blöcke in die jeweils größten (Rest-)Fenster einordnen.

Ciao, Allesquatsch

Die einzige Restriktion sind die Zeitfenster innerhalb deren sich die Blöcke befinden müssen.

Jeder Block hat ein eigenes Fenster. Er darf nicht in ein fremdes Fenster gelegt werden. Wenn das Zeitfenster lautet 13 Uhr - 18 Uhr, dann muss der (zeitlich kleinere) Block innerhalb dieses Zeitintervalls gelegt werden.

Ziel ist: möglichst wenige (zeitliche) Überschneidungen der Blöcke.
Wenn möglich: eine solche Anordnung der Blöcke finden, dass keine Überschneidungen auftreten, allerdings wird es wohl darauf hinaus laufen dass auch Überschneidungen auftreten und diese gilt es möglichst zu minimieren im Rahmen der Möglichkeiten.

Wenn möglich: optimum finden.
Eine Heuristik ist auch okay.

Es sollte möglichst einfach ohne aufwensdige numerische Berechnungen machbar sein.
Am liebsten wäre mir ein Algorithmus, dessen Funktionsweise ich auf DINA4 Blatt skizieren könnte.

Allesquatsch

czi schrieb:

Jeder Block hat ein eigenes Fenster.

Verstehe ich nicht. Meinst Du: "Jeder Block muss vollständig innerhalb eines Zeitfensters liegen." Was aber gerade nicht heißt, dass das Fenster allein diesem Block gehört, da in der Restzeit kollissionsfrei ja noch weitere Blöcke liegen können.

czi schrieb:

Er darf nicht in ein fremdes Fenster gelegt werden.

Verstehe ich nicht. Wenn Du meinst: "Jeder Block muss vollständig innerhalb eines Zeitfensters liegen.", ist das gleichbedeutend, dass er nicht auf zwei Fenster aufgeteilt werden darf.
Im Schluss heißt das, dass es gar keine zulässige Lösung gibt, wenn die größte Dauer länger als das größte Fenster ist.

czi schrieb:

Ziel ist: möglichst wenige (zeitliche) Überschneidungen der Blöcke.

Hierin scheint die Zielfunktion zu liegen. Wobei unklar ist, was genau die Zielfunktion ist. Die Anzahl, die Dauer oder die "Höhe" (wie viele Dauern "übereinander") der Überschneidungen? Gerechnet nach der Gesamtzahl oder nach dem Maximum?

czi schrieb:

Wenn möglich: eine solche Anordnung der Blöcke finden, dass keine Überschneidungen auftreten,

Ist klar und damit immer das Optimum, wenn die Zielfunktion nur nach Überschneidungen geht.

czi schrieb:

allerdings wird es wohl darauf hinaus laufen dass auch Überschneidungen auftreten und diese gilt es möglichst zu minimieren im Rahmen der Möglichkeiten.

Wenn möglich: optimum finden.
Eine Heuristik ist auch okay.

czi schrieb:

Es sollte möglichst einfach ohne aufwensdige numerische Berechnungen machbar sein.

eher aufwendig als numerisch. Wobei meines Erachtens alles von der Zielfunktion abhängt.

czi schrieb:

Am liebsten wäre mir ein Algorithmus, dessen Funktionsweise ich auf DINA4 Blatt skizieren könnte.

Das ist wahrscheinlich leichter als die Qualität der Heuristik auszurechnen. Also mathematisch zu ermitteln, wie gut die Lösung mindestens ist und wie schlecht im schlechtesten Fall.

Bisher erkenne ich nicht, dass die Lage der Zeitfenster (Uhrzeit) und die chronologische Reihung relevant ist.

Ciao, Allesquatsch

Die einzelnen Fenster können sich überschneiden. Dadurch kommen auch die zeitlichen Überschneidungen der Blöcke zustande.

Wie bereits gesagt: Jeder block (z.B. 3h lang) hat ein Fenster 12Uhr-17Uhr.
Der Block kann innerhalb des Fensters beliebig positioniert werden. Allerdings darf der Block nciht vor 12 uhr anfangen und nicht nach 17 uhr enden.

die einzelnen fenster können sich überschneiden. Nun gilt es die Blöcke innerhalb deren eigenen Fenster derart zu platzieren dass die Überschneidugnszeit minimiert wird. (Auf der Zeitachse entsprich das der Breite der Überschneidung)

Zielfunktion: Minimiere die zeitliche Überschneidung der Blöcke

Restriktionen: Zeitfenster