Name tasks objectives and give a example for cutting and packing
Name more objectives for cutting and packing.
Which things cutting and packing have in common?
What are the dimensions of cutting & packing?
What types of cutting & packing problems we have whoch of them are np hard?
What are the subproblems of cutting and packing?
What types of Assignment types we have ?
What types of object and item properties we have?
What types of pattern restrictions we have?
Neues Model: One-Dimensional Bin Packing
Give the General overview with an objective for Bin Packing (one dimensional)
Give the mathematical formulation of one-dimensional bin packing is this Problem NP-hard? What is the idea/trick of the model?
Der Trick ist hier, dass yj die größe 1 hat webb der bin genutzt wird. die Summe aus sixij kann nicht größer als 1 werden. Durch die min funktion soll yj immer 0 sein außer es wurde etwas zu bin j zugeteilt. Dann wird yj 1 und die Summe aus sixij kann maximal 1 werden.
What type of heursitic are there for one-dimensional bin packing? Give a Example
Wir müssen erst sortieren vor Anwendung der Heuristiken —> größtes S am Anfang
Wie beim packen —> man nimmt die größten am Anfang und kann dadruch am Ende noch ausgleichen mit den kleinen
First fit: wir wählen nachdem der nächste nicht mehr reinpasst das kleinste paket auf und füllen es dort rein wo es nicht reingepasst hat. hier hat 0,5 nicht mehr zu 0,7 gepasst. Deshalb nehmen wir den kleinsten (0,1) und füllen solange auf bis es voll ist. wenn es nciht mehr reinpasst nehmen wir einen neuen bin und beginnen wieder mit dem nächsten (0,5).
Best fit: Nach dem auffüllen sind wir bei der ersten 0,1 und die geht zum höchsten also 0,8. dann sind wir bei der 0,4 und die kann dann nicht zum 3. balken und auch nicht zum zweitgrößten (1.Balken) und muss dann zu 0,5 (2. Balken). Danach kommt die 0,8 und die passt nirgends rein.
Give the Bounds for:
Next Fit
First Fit
Best Fit
FF Decreasing
BF Decreasing
Neues Model: Two-Dimensional Bin Packing
Give the mathematicaö Formulation for two-dimensional bin packing. How is the procedure ?
Name the decision variables for levels are initialized by items and bins are initialized by levels.
New Model: Cutting Stock Problems (One-Dimensional Cutting Stock)
Desicrebe the Cutting Stock Problem in General an give the objective
Name the mathematical formulation of one-dimensional cutting stock
Describe the Procedure of Column generation
What are the advantages and disadvantages of column generation
New Model: Knapsack Problem
Give the generals of Knapsack Problems
Give the common Charakteristics of Knapsack Problems
Give the mathemaatical formulation of the One-Dimensional Knapsack Problem
Describe how we build cover cuts as valid inequalities
Lösungszeit wird besser wenn wir Nebenbedingungen hinzufügen die auf jeden fall wahr sein müssen (siehe Beispiel)
Neues Model: Knapsack Problems
Give the mathematical formulation of Two-dimensional Knapsack Problem
Neues Model Pallet Loa
Last changeda year ago
