Gerechtigkeit am Fließband

Sequenzierung von Bitvektoren unter Nebenbedingungen

Robert Nickel, Winfried Hochstättler

Lehrstuhl für Mathematische Grundlagen der Informatik

Brandenburgische Technische Universität Cottbus

Folie 2 von 15

Eine Anwendung aus der Automobilherstellung

Pressen, Montieren und Verschweißen der Karosserie

„Body Shop“ „Paint Shop“ „Assembly Line“

Grundieren und Lackieren der Karosserie

Einbau aller Komponenten

Folie 3 von 15

Arbeit auf dem Fließband

Einbau aller Features erfolgt auf der Assembly Line durch separate TeamsEs gibt etwa 150 Features und mehrere hundert Zusammenstellungen pro TagesproduktionEine Tagesproduktion besteht aus etwa 2000 Modellen

Standardsitze

Sportsitze

Ledersitze

Auspuffanlage

KAT in verschiedenen Typen

Alufelgen

Stahlfelgen

Breitreifen

Motor (in verschiedenen Ausführungen)

Bremsanlage

Sonnendach

Scheiben(getönt?)

Beleuchtungs-Anlage

Folie 4 von 15

Modellbildung

Es gibt eine feste Menge einbaubarer Features und jedes Modell beinhaltet ein Teilmenge davon Jedes Modell kann als 0-1-Vektor aufgefasst werden

Modelle mit gleicher Menge an Features werden als ein Modelltyp bezeichnet Die Tagesproduktion ist eine Multimenge von Bitvektoren

Die Autos werden in regelmäßigen Abständen aufs Fließband gelegt Wir betrachten vereinfacht eine Sequenz von Bitvektoren

1 1 2 2F b , , b ,b , , b , , b , , b

Folie 5 von 15

Modellbildung II

Der Einbau eines Features benötigt eine bestimmte ZeitKein Team sollte zu lange nichts zu tun haben

Mindestabstände

Maximalabstände

1ib

2ib

3ib

Folie 6 von 15

Distance Constrained Bitvector Scheduling (DCBS)

Gegeben: Eine Multimenge F von -dimensionalen Bitvektoren

Sowie Zahlen und mit

Gesucht:Finde eine Sequenzierung der Vektoren von F, so dass zwischen zwei Einsen in der Komponente immer mindestens und maximal Nullen stehen!

1 1 2 2F b , , b , b , , b , , b , , b

jm jm j jm m j 1..

jm jmj

Folie 7 von 15

Komplexitätsanalyse

Allgemeiner Fall: Pseudo-polynomielle Reduktion vom Three-Partition-Problem

Fixierte Schranken: Reduktion vom Hamiltonian-Path-Problem

Fixierte Schranken, beschränkte Anzahl Features: Reduktion auf Shortest-Path

Allgemeine Schranken, beschränkte Anzahl Features: Reduktion auf Shortest-Path

Folie 8 von 15

Der allgemeine Fall - Beweisskizze

1A1 2 3j j ja ,a ,a

mA3m 2 3m 1 3mj j ja ,a ,a

(3P)

1ja

1ja

2ja

2ja

3ja

3ja

1j

2j

3j

(DCBS)

2b 5

Folie 9 von 15

5

14

2

Ein einfacher Spezialfall

Zwei Einsen dürfen durch maximal eine Null getrennt seinReduktion vom Hamiltonian-Path-Problem

35

14

2GG35

14

2

1

2

3 4

5

3

Folie 10 von 15

Polynomielle Fälle

Wir betrachten wieder den einfachen FallReduktion auf die Suche eines Weges in einer Arboreszenz von der Wurzel zu einem BlattBeschränkt man die Anzahl der vorkommenden Varianten durch eine Konstante und bezeichnet man mit das Vorkommen von Variante in für so ist

eine Menge mit in polynomieller GrößeFüge einen Bogen genau dann ein, wenn eine der ersten Komponenten um eins reduziert wird und die korrespondierenden Vektoren aufeinander folgen dürfen

m 0,m 1

iN

i F i 1..

11,...,N ... 1,...,N 1,...,

Folie 11 von 15

Polynomielle Fälle II

N1

N2

N

0

N1-1

N2

N

1

0

0

0

i1

N1

N2

N-1

0

0

0

ix

Folie 12 von 15

Ein Vergleich

T O 3 5 7 3 5 7

10 0.03 0.06 0.10 0.03 0.03 0.03

15 0.19 0.27 0.62 0.08 0.18 0.18

20 0.88 1.11 2.36 0.31 0.53 1.05

30 9.31 22.17 24.14 2.41 5.97 9.28

40 119.78 124.15 256.86 19.56 28.45 39.19

50 1073.94 2447.47 415.50 355.15 161.90 147.25

T O 3 5 7 3 5 7

10 0.000 0.000 0.000 0.000 0.000 0.000

15 0.000 0.000 0.000 0.000 0.010 0.010

20 0.000 0.010 0.010 0.000 0.070 0.080

30 0.000 X 46.827 2.183 X X

40 2.123 X X X X X

Column Generation + CPLEX : (vergl. Drexl, Kimms: Sequencing JIT Mixed Model Assembly Lines 03/2001)

Dynamische Programmierung:

Folie 13 von 15

Eine parametrisierte Heuristik

Anforderungen an eine Sequenz:Möglichst wenige RegelverstößeGleichmäßiger Feature-Fluss

Goal Chasing (Y. Monden: Toyota Production System)

Strategie:Baue die Sequenz von links nach rechts aufWähle in jedem Iterationsschritt aus der Menge der Vektoren mit den geringsten Regelverstößen denjenigen aus, der am besten die momentanen Anforderungen an den Feature-Fluss erfülltBenutze diese Startsequenz für eine lokale Verbesserung

Folie 14 von 15

Beispiel

6x 3x 2x 2x Anzahl MinDist MaxDist654

112

223

1.21.6

2.25

Folie 15 von 15

Parametrisierung und Erweiterung

Benutze eine gewichtete euklidische Norm beim Goal ChasingFühre unterschiedliche Strafen für Regelverletzungen ein

Ersetze die Abstandsrestriktionen durchRestriktionen der Form

Dadurch können weitere Restriktionen sowohl im linearen Programm als auch in der Heuristik verwendet werden

j j,k j,k Lj 1

W X X M k L 1..n

Folie 16 von 15

Ausblick

Paralleles Zonensystem mit ungleicher Verteilung auf parallele Zonen (Regeln werden hier für jede einzelne Zone aufgestellt)

Erweitertes RegelwerkBANNING : Verbieten von Sequenzpositionen und Zonen für einzelne FeaturesCLUSTERING : Die Sequenz wird in y gleiche Teile geteilt und ein Feature darf nur in x davon vorkommenGROUPING : Ein Feature soll nur in Gruppen (mit Mindest- und Maximalgröße) auftauchen und zwischen den Gruppen gilt ein MindestabstandDELAY : Ein Feature verspätet sich auf einer Zone erwartungsgemäß(trotzdem müssen auf nachfolgenden Zonen die Regeln gelten)