Planung der Prozessfertigung mit Setup-Zeiten

Question

Übersicht

Die Prozessfertigung ist (im Gegensatz zur diskreten Fertigung) auf die Herstellung von Endlosgütern wie Öl ausgerichtet. Die Planung ist typischerweise durch lineare Programmierungen lösbar, die Einschränkungen für MILP eingeführt werden können.

Problemformulierung

Das Problem besteht aus

• Reihenfolge der aufeinanderfolgenden Zeitintervalle $ t \ in \ {1, \ dots, n_t \} $ jeweils mit Start- und Ende $ (s_t, e_t) $ und länge $ l_t= e_t-s_t $ . Aufeinanderfolgende Mittel $ E_ {T}= S_ {T + 1} $ für alle $ t \ in \ {1, \ Punkte, n_t-1 \} $ .
• Liste der Art von Waren, die produziert werden: $ j \ in \ {1, ..., n_j \} $
• Bedarf an jeder Art von GUT-pro Zeitintervall $ d_ {j, t} $ .
• Liste der Produktionslinien $ i \ in {1, \ dots, n_i} $
• Verfügbarkeit von Produktionslinien pro Zeitintervall $ A_ {I, T} $ . $ A_ {I, T} $ ist binär - egal ob verfügbar oder nicht.
• Fertigungsgeschwindigkeit pro Fertigungslinie pro Typen Waren $ v_ {i, j} $ .
• Setup-Zeit von einer Art von Waren in einen anderen $ U_ {J, J '} $ .
• Preis für die Verwendung einer Produktionslinie (Leasingbasis), zählte pro Minute $ C_ {I} $

Das Ziel ist es, die Produktionslinien zu planen, damit die Nachfrage abgedeckt ist, und der Preis für das Leasing ist minimal.

Hinweise:

• Die Setup-Zeit kann kürzer oder länger oder gleich der Länge der Intervalle sein
sein
• es ist akzeptabel, dass die Produktionslinie nicht das gesamte Zeitintervall auswirkt, wenn das Angebot früher abgeschlossen ist
• Das Setup zur Herstellung eines weiteren Guten kann jederzeit beginnen, nicht unbedingt zu Beginn eines Intervalls.

Beispiel

Es gibt zwei Produktionslinien, dh $ n_i= 2 $ und es gibt zwei Arten von Waren, dh $ n_j= 2 $ .

Wir haben zwei Intervalle, d. H. $ n_t= 2 $ , jeder hat ein LeggHT von 1 Stunde. Sagen, man beginnt um 13 Uhr, der zweite um 14 Uhr.

Die Nachfrage ist:

• $ d_ {1,1}= 1.1 $
• $ d_ {1,2}= 1 $
• $ d_ {2,1}= 1 $
• $ d_ {2,2}= 0,5 $

Das Laufen der Produktionslinien sind:

• $ c_ {1}= c_ {2}= 1 $ USD / Minute

Alle möglichen Setupzeiten sind 30 Minuten, d. H.:

• $ u_ {j, j '}= 0,5 $ für alle $ j, j' $ wo $ j \ neq j '$ .

Die Geschwindigkeiten sind:

• $ v_ {1,1}= 1.1 $
• $ v_ {1,2}= 1,5 $
• $ v_ {2,1}= 1 $
• $ v_ {2,2}= 1 $

Natürlich ist die Nachfrage erfüllt, wenn die erste Linie die erste Art von Waren in beiden Intervallen erzeugt und die zweite Zeile den zweiten Typ erzeugt. Die Kosten beträgt 204.55. Siehe die Lösung hier:

Es kann jedoch möglicherweise verlockend sein, sie zu wechseln. Linie 1 ist wesentlich effizienter für die zweite Art von Waren (1.5). Wenn es keine Setup-Zeit gibt, hätten wir die Kosten von 180 USD. Dies ist jedoch nicht möglich.

Frage

Wie hoch ist der Algorithmus, um diesen Herstellungsprozess optimal zu planen?

Eine Antwort ist willkommen, auch wenn er den Weg und den Ansatz (Milp, SAT, CSP, ...) umreißen würde.

Ideen für fernen

• Wenn die Dauer der Intervalle fixiert wäre, sagen Sie 1 Stunde und die Setupzeit in Bezug auf diese Einheiten, sagen Sie 2 Stunden. Dann könnte es von SAT / CSP lösbar sein.
• Eine Idee ist, einen evolutionären Algorithmus zu nutzen, der Folgendes aus einer Folge von Aktivitäten mit Mutationen bestehen würde (eine Aktivität hinzufügen, Aktivität, Prolong-Aktivität) und Crossover hinzufügen (Mischen Sie zwei Pläne auf zufällige Weise).

Answer 1

Wir verwenden den Index $ K $ für die Zeit, so dass $ k \ in [S_1, E_ {n_t}] $

Wir führen die folgenden Variablen ein:

$ \ ell ^ {i, k} $ - linie $ i $ wird in der linie gelöscht $ K $

$ \ alpha ^ {i, k} _ {j, j '} $ - Binäranzeige für Zeile $ I $ wechselt von $ j $ bis $ j '$ at time $ K $ .

$ p ^ {i, k} _j $ - Binäranzeige für Zeile $ i $ ist Erzeugung guter $ J $ Zum Zeitpunkt $ K $ .

$ h ^ {i, j} _j $ - Binäranzeige, die Linie $ i $ ist Warten auf den Warten, um gute $ J $ zum Zeitpunkt $ K $

$ g ^ {i, k} _j $ - erzeugter Betrag für Zeile $ i $ für Gute $ J $ Zum Zeitpunkt $ K $ (entweder $ v_ {i, j} $ oder $ 0 $ )

Ziel ist es, $ \ sum_ {i, k} c_i \ tig ^ {i, k} $ Vorbehalt der Einschränkungen:

Einschränkungen für jeden $ i, k $ :

• kann nur zu einem Zeitpunkt auf 1 Gut wechseln: $ \ textrm {At-most-1} \ alpha ^ {i, k} _ {j, j '} $ < / span>
• kann nur zu einem Zeitpunkt 1 gut machen: $ \ textrm {At-nun-1} p ^ {i, k} _j $
• kann zu einem Zeitpunkt nur für 1 Gut halten: $ \ textrm {AT-MOST-1} h ^ {i, k} _j $
• Wenn produziert, nicht umschalten: $ \ Bigvee_j p ^ {i, k} _j \ rightarrow \ neg \ bigwedge_ {j, j '} \ alpha ^ {i, k} _ {j, j '} $
• Leasing IFF produzieren oder wechseln: $ \ ell ^ {i, k {j, j '} \ alpha ^ {i, k} _ {j, J '} \ Vee \ Bigveee_j p ^ {i, k} _j $
• Nicht-Leasing impliziert, das für einige gute Holding hält: $ \ neg \ ell ^ {i, k \ neg \ rightarrow \ bigveee_j h ^ {i, k _j $ < / li>

MATH-Container> $ I, K, J $ :

• Erzeugung nur, wenn erzeugt wird: $$ P ^ {i, k} _j \ Rightarrow g ^ {i, k} _j= v_ {i, j} $$ $$ \ neg p ^ {i, k} _j \ rightarrow g ^ {i, k} _j= 0 $$
• Beim Stoppen der Herstellung muss es sofort für das gleiche Gut gedrückt sein oder auf ein anderes Wechseln zu einem anderen Wechseln (für $ k ): $ P ^ {i, K} _j \ wedge \ neg p ^ {i, k + 1} _j \ rightarrow h ^ {i, k + 1} _j \ vee \ bigvee_ { j '} \ alpha ^ {i, k + 1} _ {j, j'} $
• Wenn Sie bei $ k + 1 $ erzeugt oder gedrückt halten müssen, muss auf $ k : $ p ^ {i, k + 1} _j \ vee h ^ {i, k + 1} _j \ rightarrow p ^ {i, k} _j \ vee h ^ {i, k} _j \ vee \ bigvee_ {j '} \ alpha ^ {i, k} _ {j', j} $

Einschränkungen für jeden $ i, k :

• Beim Umschalten muss es lang genug wechseln: $ (p ^ {i, k} _j \ Vee h ^ {i, k} _j) \ wedge \ alpha ^ {i, k + 1} _ {j, j '} \ Rightarrow \ bigwedge_ {k '= k + 2} ^ {\ min (k + u_ {j, j'}, e_ {n, t})} \ alpha ^ {i, k '} _ {j, j' } $

Einschränkungen für jeden $ d_ {j, t} $ :

• $ \ sum_ {k= s_t} ^ {e_t} \ sum_i g ^ {i, k} _j \ geq d_ {j, t} $