Auftragsplanung mit Engpassproblem

11

Bei Jobs J 1 , J 2 , . . . , J n , jeder Job benötigt T i > 0 , T iN Zeit, um abgeschlossen zu werden.nJ1,J2,...,JnTi>0,TiN

Jeder Auftrag muss von einer einzelnen Maschine M vor- und nachbearbeitet werden, die jeweils nur einen Auftrag verarbeiten kann, und beide Phasen erfordern 1 Zeiteinheit. Nach der Vorverarbeitung wird der Job an eine Maschine mit unbegrenzter Leistung gesendet (die eine unbegrenzte Anzahl von Jobs parallel verarbeiten kann) und er wird zum Zeitpunkt T i bereit sein , dann muss er ( sofort ) an die Maschine M gesendet werden wieder zur Nachbearbeitung.JiTi

Geben Sie hier die Bildbeschreibung ein

Das damit verbundene Entscheidungsproblem ist:

Eingabe: die Verarbeitungszeiten von N Jobs, eine ganze Zahl K 2 N Frage: Können wir alle Jobs in der Zeit K unter Verwendung des obigen "Engpass" -Modells verarbeiten?Ti>0,TiNNK2N
K

Hat dieses Problem einen Namen?
Was ist ihre Komplexität? ( Ist es in oder ist es N P- vollständig?) PNP

UPDATE 29. März:
Wie von M.Cafaro in seiner Antwort richtig bemerkt, ähnelt das Problem dem UMFT-Problem (Unconstrained Minimum Finish Time Problem) (siehe Kapitel 17 des Handbuchs für Planungsalgorithmen ), das -hard ist (bewiesen in W. Kern und W. Nawijn, "Planen von Jobs mit mehreren Operationen mit Zeitverzögerungen auf einer einzelnen Maschine", University of Twente, 1993). Wie ich sehen kann, gibt es einige Unterschiede in meinem Modell:NP

  • Die Vor- / Nachbearbeitungszeit ist konstant (1 Zeiteinheit).
  • Sobald der Auftrag abgeschlossen ist, muss er sofort nachbearbeitet werden (das UMFT-Modell ermöglicht Verzögerungen).

Ich habe den Kern & Nawijn-Beweis nicht online gefunden, daher weiß ich immer noch nicht, ob die oben genannten Einschränkungen die Schwierigkeit des Problems ändern.

Schließlich können Sie sich den gesamten Prozess wie einen einzelnen Kochroboter mit einem großen Ofen vorstellen. Der Roboter kann nacheinander verschiedene Arten von Lebensmitteln zubereiten (alle erfordern die gleiche Zubereitungszeit), sie in den Ofen stellen. Sobald sie gekocht sind, muss er sie aus dem Ofen nehmen und einige kalte Zutaten hinzufügen ... das " Kochroboterproblem " :-)

Vor
quelle
Nett. Ich habe das Gefühl, dass der Engpass die Dinge vereinfachen sollte.
Raphael
Die Bedingung wird immer überprüft, da die Kosten vor und nach der Verarbeitung beide 1 Zeiteinheit betragen und Sie n habenk2nn Jobs haben. Sind Sie sicher, dass die Einschränkung korrekt ist?
Massimo Cafaro
Entschuldigung, mir war nicht klar, was ich im vorherigen Kommentar gemeint habe. Wird in der Eingabe explizit als "Frist" angegeben oder fragen Sie nach einem Algorithmus zur Minimierung?k ? k
Massimo Cafaro
@MassimoCafaro: wird als Eingabe angegeben (um das Optimierungsproblem zu einem Entscheidungsproblem zu machen). Wie Sie bemerkt haben, habe ich k 2 n geschrieben, denn wenn k < 2 n ist , lautet die Antwort trivial NEIN. Aber vielleicht ist es verwirrend und ich sollte es löschen. kk2nk<2n
Vor dem
1
Ihre Frage ist nachweislich NP-vollständig in von W. Yu, H. Hoogeveen und JK Lenstra (2004), die dies ebenfalls sagen, "Die Minimierung der Makespan in einem Zwei-Maschinen-Flow-Shop mit Verzögerungen und Zeitbetrieb ist NP-schwer" Kern und Nawijn haben es nicht gelöst. Ich zitiere: "Der Komplexitätsstatus des Sonderfalls mit Aufgaben zur Verarbeitung der Einheitszeit war sowohl für minimale als auch für genaue Verzögerungen offen. Der Komplexitätsstatus desjenigen mit minimalen Verzögerungen wird von Kern und Nawijn (1991) als offene Frage gestellt."
Peter Shor

Antworten:

5

Die Frage wurde von W. Yu, H. Hoogeveen und JK Lenstra (2004) in "Minimierung der Makespan in einem Zwei-Maschinen-Flow-Shop mit Verzögerungen und Einheitszeitbetrieb ist NP-schwer" bewiesen . Dies wird in Abschnitt 9 des Papiers bewiesen:

Satz 24. Das Problem der Minimierung der Makespan auf einer einzelnen Maschine mit zwei Zeiteinheiten pro Job mit willkürlichen Zwischenverzögerungen ist stark NP-schwer.

Das genaue Modell, das hier untersucht wird, besteht darin, dass Job aus zwei Operationen besteht, die Zeiteinheiten benötigen, die durch eine Verzögerungszeit T i getrennt sindiTi . Das Problem ist stark NP-vollständig, sowohl wenn der genaue Wert der Verzögerung für jeden Job angegeben wird, als auch wenn für jeden Job eine minimale Verzögerungszeit angegeben wird.Ti

Peter Shor
quelle
5

Dies sieht aus wie das von Sahni eingeführte sogenannte Master-Slave-Planungsmodell . Insbesondere fällt Ihr Problem unter die Single-Master-Master-Slave-Systeme. Sie können mehrere Fälle unterscheiden:

1) Wenn Sie keine zusätzliche Einschränkung für die Reihenfolge der Jobausführung hinzufügen (wie in Ihrem Fall), wird das Problem als uneingeschränktes Problem der minimalen Endzeit (UMFT) bezeichnet und hat sich als NP-hart erwiesen.

2) Gleiche Vor- und Nachbearbeitungsaufträge: Es ist möglich, ein O ( n log n ) zu entwerfen.O(nlogn) -Algorithmus , um einen Auftrag zu erstellen , der die Mindestendzeit (OPMFT) beibehält.

Daher ist in Fall 1 Ihr Problem -hart, während es in istNPP

Zusätzliche verwandte Probleme sind:

3) Nachbearbeitung in umgekehrter Reihenfolge: Für jede gegebene Vorverarbeitungspermutation ist es möglich, einen Zeitplan in umgekehrter Reihenfolge zu erstellen , der als kanonischer Zeitplan in umgekehrter Reihenfolge (CROS) bezeichnet wird. Bei einer Vorverarbeitungspermutation σσσ ist der entsprechende CROS eindeutig. Es ist leicht festzustellen, dass jeder ROMFT-Zeitplan ( Minimum Finish Time Reverse Order ) ein CROS ist.

4) Keine Wartezeit im Prozess:

a) [MFTNW] Minimieren Sie die Endzeit unter der Bedingung, dass kein Warten auf den Prozess erforderlich ist. b) [OP-MFTNW] Dies ist die auftragserhaltende Version von MFTNW. Das heißt, minimieren Sie die Endzeit, vorbehaltlich der Einschränkungen, dass keine Wartezeiten bestehen und die Reihenfolge erhalten bleibt. c) [RO-MFTNW] Minimieren Sie die Endzeit vorbehaltlich der Einschränkungen, dass keine Wartezeit besteht und die Reihenfolge umgekehrt ist.

abc

Weitere Details finden Sie im Handbuch zur Zeitplanung , Kapitel 17.

Massimo Cafaro
quelle
n
nnnn
2
Es sieht für mich so aus, als würde der NP-Härtenachweis von Sahni kritisch die Tatsache nutzen, dass die Vorverarbeitungs- und Nachbearbeitungszeiten beliebig sein können. Das Problem des OP ist alle diese Zeiten gleich 1. Funktioniert der Beweis in diesem Fall?
Peter Shor
Vor, das Papier, auf das Sie sich beziehen, ist nur ein Auszug mit vielen fehlenden Teilen aus Kapitel 17 des Buches. Der fehlende Teil verhindert jedoch, dass Sie richtig verstehen (fehlende Notation usw.).
Massimo Cafaro
O(nlogn)