Algorithmus für optimales Packen mit bekanntem Inventar
Krankenhäuser verändern die Art und Weise, wie sie ihre Ausrüstung sterilisieren. Zuvor behielten die örtlichen Chirurgen ihre gesamte Ausrüstung und stellten ihre eigenen Operationsschalen her. Jetzt müssen sie sich auf einen landesweiten Standard beschränken. Sie möchten wissen, wie viele der neuen Schalen sie aus ihrem vorhandenen Lager machen können und wie viel neue Ausrüstung sie kaufen müssen.
Das Inventar der medizinischen Ausrüstung sieht so aus:
Jedes Krankenhaus hat Codes für verschiedene medizinische Geräte und dann eine Nummer für die Anzahl der entsprechenden Artikel
In diesem Wörterbuch werden 3 Chirurgie-Trays mit ihren entsprechenden Artikeln angezeigt.
Es gibt insgesamt 144 verschiedene Arbeitsfächer
den Krankenhäusern wird gesagt, sie brauchen 25 von Fach x, 30 von Fach y, etc ...
Sie möchten die Menge der Schalen maximieren, die sie mit ihrem aktuellen Lager fertigstellen können. Sie möchten auch wissen, welche Ausrüstung sie kaufen müssen, um die restlichen Schalen zu beenden.
Ich habe über zwei mögliche Lösungen nachgedacht, wobei eines das Problem als ein lineares Programmierproblem darstellt. Der andere löst das Problem, indem er eine Round-Robin-Brute-Force-Lösung der ersten 90% des Problems durchführt und die restlichen 10% löst, indem er einen randomisierten Algorithmus mehrmals durchführt und dann die beste Lösung dieser Versuche auswählt.
Ich würde gerne hören, wenn jemand einen klugen Weg kennt, wie man dieses Problem angehen kann!
1 Antwort
Wenn ich das richtig verstehe, können wir für jedes Krankenhaus einzeln optimieren. Meine Vermutung ist, dass das Folgende ein guter Anfang für ein MIP (Mixed Integer Programming) -Modell wäre:
Ich verwende die folgenden Indizes: i ist Artikel und t sind Fächer. x(t,i) gibt an, wie viele Objekte wir jedem Tabletttyp zuweisen. y(t) zählt die Anzahl der Fächer jedes Typs, die wir mit den verfügbaren Elementen erstellen können. Aus der Lösung können wir die Engpässe berechnen, die wir bestellen müssen.
Natürlich maximieren wir nur die Anzahl der Schalen, die wir herstellen können. Es gibt keine Abwägung (viele Schalen eines Typs und wenige oder Null eines anderen). Ich mildere ein wenig, indem ich nicht erlaube, mehr Tabletts als nötig zu erstellen (wenn wir mehr Gegenstände haben, müssen sie zu anderen Tabletts gehen). Diese Anforderung wird als obere Grenze für y(t) formuliert.
Bei großen Problemen können wir die (t,i) -Kombinationen auf die möglichen beschränken. Dies wird das Modell kleiner machen. Bei genauer mathematischer Schreibweise:
Eine weitere Optimierung wäre, die Variablen x(t,i) zu ersetzen.
Das Hinzufügen von überschüssigen Versandstücken zu anderen Krankenhäusern würde das Modell erschweren. In diesem Fall könnten wir mit einem Modell enden, das alle Krankenhäuser gleichzeitig untersuchen muss. Kann ein interessanter Fall für einen Zersetzungsansatz sein.
Tags und Links algorithm dynamic-programming linear-programming