Ist dies ein bekanntes kombinatorisches Optimierungs- / Planungsproblem?

8

Wir erhalten Stapel, die "Gegenstände" unterschiedlicher Farbe enthalten, und eine Maschine, die mehrere Gegenstände derselben Farbe auf einmal verarbeiten kann. Bei jedem Schritt können wir einen Gegenstand von der Oberseite jedes Stapels entfernen und in unsere Maschine legen (so effektiv kann die Maschine höchstens n Gegenstände in einem Schritt verarbeiten - dazu müssen alle Stapel Gegenstände derselben Farbe haben oben drauf). Ziel ist es, alle Artikel in kürzester Zeit zu bearbeiten.nn

Beispieleingabe:

Eine mögliche Lösung ist ein gieriger Algorithmus: Nehmen Sie bei jedem Schritt so viele Gegenstände wie möglich und stopfen Sie sie alle in die Maschine. Leider ist der Greedy-Algorithmus nicht optimal - er erzeugt den folgenden Zeitplan für die Beispieleingabe:

Der optimale Zeitplan ist der folgende:

Ich habe vor, eine Form der Zustandsraumsuche durchzuführen, aber vielleicht gibt es einen problemspezifischeren und effizienteren Ansatz? Links zu einschlägiger Literatur sind willkommen.

Mikhail Glushenkov
quelle
Bei jedem Schritt dürfen Sie nur einen Gegenstand von der Oberseite jedes Stapels nehmen (und alle Gegenstände, die Sie in die Maschine legen, müssen dieselbe Farbe haben). Der Greedy-Algorithmus erzeugt also einen nicht optimalen Zeitplan (siehe Abb. 2).
Mikhail Glushenkov
Und Sie müssen alle Artikel der Reihe nach bearbeiten, dh nur von oben nehmen.
Mikhail Glushenkov
Ahh. Ich habs. Interessantes Problem. Ich würde eine optimale Nachschlagetabelle erstellen, um die ersten Zeilen zu bestimmen, wenn dies ein Echtzeitsystem wäre. Was die genaue Komplexität betrifft ... beweisen Sie zuerst das Optimum für den zweispaltigen Fall.
Chad Brewbaker
Die Frage wäre noch interessanter, wenn Sie eine Reihe von FIFO-Listen bearbeiten, in denen Sie nur Elemente bis zu einer bestimmten Tiefe für die Berechnung einsehen können.
George Polevoy

Antworten:

7

[1]]Ö(n2) [2]]

Was die Annäherbarkeit einer guten Quelle betrifft, ist ein Kompendium von NP-Optimierungsproblemen .

[3,4]]

[5]][6]]

  1. Brauner N., Naves G. Planen von Betriebsketten auf einer Dosiermaschine mit disjunkten Betriebskompatibilitätssätzen .
  2. Brucker P. Planungsalgorithmen (Kapitel 8. Stapelprobleme).
  3. Timkovsky VG Einige Annäherungen für kürzeste häufige Nicht-Subsequenzen und Supersequenzen .
  4. Gotthilf Z. und Lewenstein M. Verbesserte Approximationsergebnisse für das kürzeste gemeinsame Supersequenzproblem .
  5. Kubalik J. Effizienter stochastischer lokaler Suchalgorithmus zur Lösung des kürzesten häufigen Supersequenzproblems .
  6. Blum, C., Cotta, C., Fernandez, AJ, Gallardo, JE Ein probabilistischer Strahlensuchansatz für das kürzeste gemeinsame Supersequenzproblem .
Oleksandr Bondarenko
quelle
1
knÖ(nk)
2

Ω(Logδn)

kkX.|X.|=xX.xxX.x/.k

Sasho Nikolov
quelle