Autor Beitrag
Borg-Cube
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 37


Delphi 2009
BeitragVerfasst: Do 06.11.25 14:48 
Hallo
Ich habe folgendes Optimierungsproblem und bin ein wenig ratlos wie ich das umsetzen könnte.
Es geht um die Planung von Konferenzschienen mit mehreren Personen.
Es soll 3 Slots geben, in den Slots finden jeweils mehrere Konferenzen von Teams parallel statt. Jedem Team sind feste Teilnehmer zugeordnet. Die Teilnehmer gehören aber zum Teil mehreren Teams an.
Die Teams in den Slots sollen so gesetzt werden, dass jede Person in einem Slot an max. 1 Konferenz eingeplant ist.
Beispiel
Slot 1:
Team A (P1,P2,P3)
Team B (P4, P5, P6)
Team C (P7, P8, P9)
Das wurde bisher händisch gemacht und war teilweise sehr viel Arbeit, die Anzahl der Teams ist aber inzwischen so groß, dass es unverhältnismäßig lange dauert, daher hatte ich überlegt, ob man das mit einem Programm lösen könnte.

Wahrscheinlich ist es sinnvoll für jedes Team ein arry zu erstellen und dann da irgendwie zu vergleichen (oder im schlimmsten Fall bruteforcen?).
Da es ggf. keine Lösung für die Kombinationen gibt könnte man als Zusatzkriterium hereinnehmen, dass z.b. die ersten 2 Personen unbedingt dabei sein müssen, der Rest wäre schön, wenn es aber nicht geht, dann ist das halt so. Die Anzahl der fehlenden Personen zu minimieren wäre dann der optimale Zustand.

Wie könnte man sowas umsetzen?


Moderiert von user profile iconTh69: Topic aus Grafische Benutzeroberflächen (VCL & FireMonkey) verschoben am Fr 07.11.2025 um 09:42
Sinspin
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1336
Erhaltene Danke: 118

Win 10
RIO, CE, Lazarus
BeitragVerfasst: Fr 07.11.25 12:16 
Kennst du Prolog? Das ist ein perfekter Kandidat zum lösen solcher Probleme.
Das basiert auf Brute Force.
Allerdings lässt sich recht einfach beschreiben was man will, den Rest macht Prolog.

Ich kann mich erinnern das wir sowas wie dein Beispiel mal im Studium hatten.
Ist aber so ewig her das ich da fast bei Null anfange.

_________________
Wir zerstören die Natur und Wälder der Erde. Wir töten wilde Tiere für Trophäen. Wir produzieren Lebewesen als Massenware um sie nach wenigen Monaten zu töten. Warum sollte unser aller Mutter, die Natur, nicht die gleichen Rechte haben?
Borg-Cube Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 37


Delphi 2009
BeitragVerfasst: Fr 07.11.25 14:18 
Hast du einen Link wo ich da weitere Infos dazu finden kann?
Th69
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 4801
Erhaltene Danke: 1059

Win10
C#, C++ (VS 2017/19/22)
BeitragVerfasst: Sa 08.11.25 10:01 
Schau mal in The Power of Prolog, besonders Combinatorial Optimization with Prolog. Der dortige Link unter scheduling (The Social Golfer Problem) sowie bei den GitHub-Beispielen das Beispiel tasks.pl könnten dir evtl. als Ausgangspunkt für dein Optimierungsproblem dienen.
Blup
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 175
Erhaltene Danke: 43



BeitragVerfasst: Gestern um 10:17 
Dieser Lösungsansatz berücksichtigt noch kein Zusatzkriterium.
Wenn jede Person eine fortlaufende Nummer erhält, lassen sich Mengen von Personen als Bitfelder darstellen.
Die können durch einfache binäre Operatoren verknüpft werden.
Jedes Team und jeder Slot hat eine Menge von Personen.
Überscheiden sich die Personen nicht ( Slot and Team = [leere Menge] ), kann das Team dem Slot hinzugefügt werden ( Slot or Team).
ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
Person    Team                              Lösung 1                        Lösung 2      
          A      B      C      D            Slot 1 = A+B+C  Slot 2 = D      Slot 1 = A+D  Slot 2 = B+C
1         1      0      0      0            1               0               1             0
2         1      0      0      0            1               0               1             0
3         1      0      0      0            1               0               1             0
4         0      1      0      0            1               0               0             1
5         0      1      0      0            1               0               0             1
6         0      1      0      1            1               1               1             1
7         0      0      1      0            1               0               0             1
8         0      0      1      0            1               0               0             1
9         0      0      1      1            1               1               1             1

ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
Eine Funktion der eine Liste von Teams übergeben wird:
  Lege einen neuen Slot an.
  Finde alle Kombinationen, mit denen der aktuelle Slot aus den restlichen Teams gefüllt werden kann.
    Für jede gefunde Kombination:
    Wurden alle Teams verwendet, wird die Lösung gespeichert.
    Andernfalls rekursiver Start der Funktion mit den noch nicht verwendeten Teams.
  Entferne den angelegten Slot

Die gefundenen Lösungen können bewertet und ausgewählt werden.
Die Reihenfolge der Slots kann nachträglich geändert werden, aber das ist im Prizip keine andere Lösung.