Algorithmus Krankenhausbelegung

[Brainiac]

Ich habe folgende Ausgangssituation:

1..n Patienten haben 1..6 Krankheiten

Die Krankheiten haben eine Behandlungsdauer, und einen bestimmten Behandlungsraum.

Das Krankenhaus hat 1..n Behandlungsräume.

Ich suche nun einen Algorithmus der der die 1..n Patienten möglichst effizient durch das Krankenhaus schiebt. (Traum wäre, wenn man dem später noch verschiedene Kriterien mitgeben könnte, aber das ist Zukunftsmusik)

Bin ich da im Bereich NP Schwer?

Ich weiß im Moment nicht so wirklich wie ich da Anfangen soll. Irgendwelche Hinweise, wie und wo ich da suchen kann? Stichworte oder ähnliches.

 

[Sonecc]

Problem des Handlungsreisenden ? Wikipedia

fällt mir da spontan zu ein

 

[ThreadPool]

Na da hast du dir ja was rausgesucht. Schau mal nach "scheduling problems" in Bezug zum Operations Research. Das was du da hast scheint eine Art "job shop scheduling"-Problem zu sein, also das Verteilen von "Arbeit" auf eine bestimmte Anzahl von Maschinen mit dem Ziel die Durchlaufzeit zu minimieren.

 

[Sonecc]

Stimmt. Das passt besser als mein erster Gedanke (@ThreadPool)

 

[Brainiac]

So danke euch für die Schubser in die richtige Richtung. Das wird wohl was komplexer, so wie es ausschaut. Ist wohl absolutes Forschungsgebiet. Zumindest finde ich nur universitäres Material dazu.

 

[muckelzwerg]

Noch bist Du nicht im Bereich NP-schwer sondern im Bereich "lass uns mal genauer hinschauen.

Du musst das Problem noch besser formalisieren.
1..n Patienten und 1..n Räume oder 1..m Räume?
Wieviele Krankheiten gibt maximal, bzw. was ist die Menge der Krankheiten, die behandelt werden kann?
Hat jeder Raum eine Liste von Krankheiten, die dort behandelt werden können? Oder gibt es für jede Krankheit genau einen Raum?
...
Was ist gesucht?
"Effizient" ist ungefähr so wie "geht nicht" als Fehlermedlung.
Wenn Du etwas optimieren willst, dann musst Du eine Kostenfunktion aufstellen, mit der man Arbeiten kann.
Vielleicht die Leerlaufzeiten der Räume, oder die Wartezeiten der Patienten, oder doch was anderes?


Dann kannst Du schauen, ob Du Dein Problem irgendwo bei Schedulingproblemen wiederfindest.
Als Buchreferenz ist da meist Gary, Johnson "Computers and Intractability" angesagt. Da gibt es eine große Liste mit solchen Problemen.
Im Netz findest Du aber auch viel.

Wenn Du Dein Problem auf ein bekanntes Problem übertragen kannst, dann musst Du mal schauen, was es da für Möglichkeiten gibt.
Evlt. existiert ein Scheduling-Verfahren, das optimal ist. Vielleicht hast Du aber auch richtig Pech.
Versuch zusätzliche Randbedingungen zu ermitteln, mit denen das Problem vielleicht ein anderer zu behandelnder Spezialfall wird.
Das angesprochene TSP z.B. ist NP-hart, aber bei metrischem TSP sieht es schon wieder anders aus.
Da musst Du dann mal nach Approximationsverfahren schauen.

 

[Brainiac]

Also es sind 1..n Patienten mit 1 bis 6 Krankheiten. Bei den Krankheiten sind es dann 1 bis m verschiedene. Jede Krankheit benötigt genau einen Behandlungsraum. Jeder Behandlungsraum kann aber mehr als eine Krankheit behandeln.
Im Krankenhaus gibt es von jedem Behandlungsraum mind. einen. Aber es können auch mehr sein. Es muss aber nicht von jeder Sorte gleich viele geben.

Soviel nochmal zum Problem

 

[muckelzwerg]

Komm schon, das kannst Du noch besser.
Jeder Patient hat 1..6 (unterschiedliche) Krankheiten.
Wenn m > 6 dann hat trotzdem kein Patient mehr als 6 Krankheiten?
Wenn m < 6 dann hat kein Patient mehr als m Krankheiten?

Ein Behandlungsraum kann 1..x unterschiedliche Krankheiten behandeln.
"Es gibt von jedem Behandlungsraum mind. einen" was meinst Du damit? Dass es für jede Krankheit mindestens einen Raum gibt, in dem sie behandelt werden kann?
So wie Du das schreibst, klingt es nach Typen von Behandlungsräumen.
Bei m verschiedenen Krankheiten gibt es |P(m)| = 2^|m| verschiedene Räume (Potenzmenge). Das würde bedeuten bei 10 verschiedenen Krankheiten gibt es genau 1024 Räume.
Ist es nicht eher
"für jede Krankheit gibt es einen Raum, der mindestens diese Krankheit (und vielleicht auch andere) behandelt"?

Mach Dir mal ein Modell für die Abbildungen von Patienten auf Räume bzw. umgekehrt.
Wenn Patient P1 mit Krankheit K1 behandelt wird ist damit die Behandlung aller P1Kx blockiert. Räume die sonst nichts zu tun haben, warten dann während auf den Raum von P1 noch ein anderer Patient wartet, der eine andere Krankheit hat.
Wenn Raum R1 belegt ist, dann warten alle Patienten, die nur noch Krankheiten haben, die in R1 behandelt werden können.
...

Und nach wie vor die wichtigste Frage:
Was soll optimiert werden, was soll "effizient" gemacht werden?
Wartezeit der Patienten verringern? Durchschnittliche? Maximale? ...
Patientendurchsatz des Krankenhauses erhöhen?
Auslastung der Räume maximieren?
...

Und welche Größenordnungen hast Du? VIELLEICHT hast Du ja glück und kommst trotz nichtpolynomieller deterministischer Zeit noch hin. (ist aber eher unwahrscheinlich)

 

[Brainiac]

Es gibt bei der ganzen Geschichte ein Level. Je größer desto mehr Patienten, Krankheiten und Räume stehen an.
Im Moment gibt es 122 Krankheiten. Jeder Krankheit hat ihre Behandlungszeit. Je Patient kommen 1 bis 6 verschiedene vor (es kann keine Krankheit doppelt vorkommen, aber es könnten alle Krankheiten für den selben Behandlungsraum sein).
Wenn die aktuell mögliche Anzahl an Krankheiten größer 6 ist hat ein Patient max. 6 Krankheiten.
Wenn die anzahl möglicher Krankheiten < 6 ist, hat kein Patient mehr als die mögliche Anzahl an Krankheiten.

Dein Zitat:
Wenn m > 6 dann hat trotzdem kein Patient mehr als 6 Krankheiten?
Wenn m < 6 dann hat kein Patient mehr als m Krankheiten?
JA

Es gibt 14 verschieden Behandlungsräume, auf die sich die Krankheiten verteilen. Jede Krankheit hat einen Behandlungsraum, aber jeder Behandlungsraum hat mehrere Krankheiten.
Im Krankenhaus gibt es nun eine beliebige Anzahl und Kombination dieser Behandlungsräume (in gewissen Grenzen, da das Krankenhaus nicht unendlich Platz hat, aber sollten nicht viel mehr als max. 60 sein. Wobei eher wengier.)
Die Patienten Anzahl ist theoretisch beliebig. Im Schnitt so gegen ~100 tendierend. Jeder Patient bringt Punkte und Geld. Allerdings erst wenn alle seine Krankheiten behandelt sind. Für den ersten Ansatz soll so optimiert werden, das alle Patienten in der kürzesten Gesamtbehandlungszeit durchs Krankenhaus sind. Wenn eine Gesamtbehandlungszeit > 24h (oder noch besser auswählbar) rauskommt, sollte entweder nach Punkten oder Geld optimiert werden können (in der gewählten Gesamtbehandlungszeit).

Jeder Behandlungsraum kann gleichzeitig nur einen Patienten aufnehmen. Und jeder Patient kann nur in einem Behandlungsraum sein. Nach jeder einzeln Krankheit kann der Raum gewechselt werden. Krankheiten die im gleichen Raum behandelt werden, können nicht in beliebiger Reihenfolge behandelt werden sondern nur in Richtung 1 nach 6.

So hoffe das ganze nun ausführlich genug formuliert zu haben. Ganz schön kompliziert das was man im Kopf hat und einem klar ist, sauber definiert zu Papier zu bringen.

@Edit: Frage Ergänzt

 

[Brainiac]

@Muckelzwerg keine Idee mehr? Oder fehlt noch was?

Alls job shop scheduling algorithmen gehen irgendwie davon aus, das die Maschienen auf denen gearbeitet wird gleich sind. Das ist ja bei mir anders. Maschine = Behandlungsraum. Oder hab ich da nen Denkfehler?

 

[tuttle64]

Problem des Handlungsreisenden ? Wikipedia

fällt mir da spontan zu ein

Etwas allgemeiner erinnert mich das an Operations Research ? Wikipedia

 

[Pippl]

Wenn ein Patient in einem Raum wegen mehreren Krankheiten behandelt wird gibt es zwischen den einzelnen Behandlungen (welche ja unterschiedlich dauern können) noch eine Wartezeit? (wegen Behandlungsraum säubern, neue Behandlungsgerätschaft holen usw.)

Wechselt ein Patient den Raum ist es wichtig zu beachten das ein Wechsel auch seine Zeit dauert?

 

[Brainiac]

Wenn ein Patient in einem Raum wegen mehreren Krankheiten behandelt wird gibt es zwischen den einzelnen Behandlungen (welche ja unterschiedlich dauern können) noch eine Wartezeit? (wegen Behandlungsraum säubern, neue Behandlungsgerätschaft holen usw.)

Wenn es sinn macht den Patienten mit all seinen Krankheiten für einen Raum auf einmal zu behandeln, geschieht dies in einem Rutsch. Keine Wartezeit, oder ähnliches. Die Sekunde, in der die eine Behandlung fertig ist, startet die nächste.

Wechselt ein Patient den Raum ist es wichtig zu beachten das ein Wechsel auch seine Zeit dauert?

Nein das eigentliche Wechseln erfordert keine Zeit. Bzw. muss nicht mitberücksichtigt werden. Wenn hier mal längere Pausen entstanden wären. Würde einfach auf die aktuelle Menge an Patienten mit ihren Krankheiten optimiert. Sprich man würde einen neuen Abarbeitungsplan berechnen. Sofern das nicht mehrere Stunden dauern würde.

P.S: Dabei gehts um ein Browsergame. Nicht um die Planung eines Realenkrankenhausablaufes. Kapi Hospital - Browsergames - Jetzt kostenlos im Browser spielen!

 

[muckelzwerg]

Puah, also wie gesagt, Du musst das Problem irgendwie formal zu packen kriegen.
Such mal nach Scheduling-Problemen und schau, ob Du Deinen Fall darauf übertragen kannst.
Wir hatten mal einen Fall, da ging es um die Migration von Anwendungen auf mehreren virtuellen Maschinen. Die Anwendung hatten verschiedene Anforderungen an Speicher und Prozessorleistung.
Da wurde auf das Bin-Packing Problem übertragen.
Als drittes schau mal nach Algorithmen für Warteschlangen.
Mit Scheduling Problems, multidimensional bin packing problems und Queueing Problems solltest Du schon was finden.
Den Gary & Johnson gibts auch als "Studentenversion", da kannst Du auch mal suchen.

Ich kann mir vorstellen, dass Du sogar mehr als nur eines dieser Probleme vor Dir hast.
Mehrdimensionale Anforderungen und mehrdimensionale, begrenzte Ressourcen ist schon kein Kindergarten mehr.
Für die weitere Vorgehensweise solltest Du auf jeden Fall den Brute-Force implementieren und dann an die Stelle kommen, wo die Rechenleistung nicht mehr ausreicht.

Also entwirf mal ein Format für die Ausgabe. Was soll das Verfahren am Ende abliefern? Das muss ja eine Reihenfolge von Zuordnungen Patient -> Raum sein.
Und dann schreibst Du einen einfachen Algorithmus, der JEDE mögliche Lösung (also jede mögliche Behandlungsreihenfolge) ausprobiert und deren Bewertung ermittelt.
Es wird da einen Punkt geben, ab dem die Rechenzeit nicht mehr ausreicht. Also fang mit kleinen Mengen an.


Edit: Ist ja vielleicht nur ein Browserspiel, aber das ändert nichts an den Problemen die dahinterstehen.
Das hättest Du aber auch gleich sagen können.
So oder so ist das kein einfaches Problem und mit der Lösung kann man nicht nur bei Browsergames schummeln, sondern auch Geld verdienen.
Deswegen musst Du ab hier, dann mal selbst weiterschaffen.

 

[Marlon]

Stichpunkte: Neuronale Netze, Genetische Algorithmen

Ich würde diesen Fall über genetische Algorithmen lösen, eine gute Einführung findest du hier:
Genetic Algorithms in Plain English - Genetische Algorithmen in verständlichem Deutsch

 

[homer65]

Irgentwie fehlt mir noch das Ziel. Was soll erreicht werden?

 

[Shulyn]

Mir ist das auch noch zu ungenau...
Kannst du evtl einen Konkreten Fall beschreiben?
Bsp.:
Wir haben 4 Patienten. A - D.
Diese haben folgende Krankheiten :
A = 1,2
B = 1,4
c = 1
D 1,2,3,4,5,6

Es stehen folgende Räume zur verfügung :
Raum 1, Raum 2, Raum 3
Raum 1 Heilt = Krankheit 1,2
Raum 2 Heilt = Krankheit 2,3,4
Raum 3 Heilt = Krankheit 1,2,3,4,5,6

Die Behandlungsdauer für die Räume ist wie folgt :
Raum 1 = 1h
Raum 2 = 6h
Raum 3 = 24h


Jetzt könntest du nach ver. Zielen die "belegung" Planen.
Max Ausnutzung der Räume,
Min. Wartezeit für Patienten,
Min. Behandlungsdauer
Max. Behandlungsdauer (Patienten die langen Behandelt werden bringen mehr Geld?!? )
oder oder oder...

Wo ich mir das alles so durch den Kopf gehen lasse, das hört sich etwas nach Theme Hospital ? Wikipedia an ^^

 

[Pippl]

Mir stellt sich nur noch eine Frage:

Es gibt den Patienten A, welcher die Krankheiten 1,2,5,10 hat

Nun gibt es zwei Behandlungsräume
Behandlungsraum 1 heilt Krankheit 1, 5 und
Behandlungsraum 2 heilt Krankheit 2, 10

Der Patient wird in Behandlungsraum 1 geschickt und es wird die Krankheit 1 geheilt. Muss er jetzt erst gegen Krankheit 2 behandelt werden bevor er gegen Krankheit 5 behandelt werden kann oder ist es nur wichtig das erst Krankheit 1 und dann Krankheit 5 behandelt wird?

Die Behandlungsdauer für die Räume ist wie folgt :
Raum 1 = 1h
Raum 2 = 6h
Raum 3 = 24h

Beachte jede Krankheit hat einen Behandlungsdauer, nicht der Raum!

Irgentwie fehlt mir noch das Ziel. Was soll erreicht werden?

Er hat das Ziel erst später gepostet ;-)
... . Jeder Patient bringt Punkte und Geld. Allerdings erst wenn alle seine Krankheiten behandelt sind. Für den ersten Ansatz soll so optimiert werden, das alle Patienten in der kürzesten Gesamtbehandlungszeit durchs Krankenhaus sind. ...

Wobei hier unklar ist ob jeder Patient gleich viel Punkte/Geld bringt wenn er von allen Krankheiten geheilt wird oder es auf die Dauer des Aufenthalt im Krankenhaus (kann ja sein das er x Stunden nicht behandelt wird weil alles voll) und die behandelten Krankheiten ankommt?