Changeset 15822 for branches/2817-BinPackingSpeedup

Timestamp:

02/28/18 15:33:30 (7 years ago)

Author:

rhanghof

Message:

#2817:

• Added the property SequenceGroup to the PackingItem
• Fixed a bug related to the sequence group

Location:

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D

Files:

• ExtremePointCreation/PointProjectionBasedEPCreator.cs (modified) (1 diff)
• ExtremePointPruning/ExtremePointPruning.cs (modified) (1 diff)
• ExtremePointPruning/IExtremePointPruning.cs (modified) (1 diff)
• Instances/ThreeDInstanceParser.cs (modified) (1 diff)
• Packer/BinPacker.cs (modified) (1 diff)
• Packer/BinPackerMinRSLeft.cs (modified) (1 diff)
• PackingItem.cs (modified) (5 diffs)
• Sorting/PermutationPackingItemSorter.cs (modified) (6 diffs)

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointCreation/PointProjectionBasedEPCreator.cs

@@ -50 +50 @@
       }
       
-      // generate all new extreme points parallel. This speeds up the creator.
-      var items = binPacking.Items.OrderBy(x => x.Value.Layer);
-      Parallel.ForEach(items.Where(x => x.Value.Layer < item.Layer), i => {
-        PackingItem it = i.Value;
-        PackingPosition pos = binPacking.Positions[i.Key];
-        GenerateNewExtremePointsForItem(binPacking, it, pos);
-      });
-      
-      Parallel.ForEach(items.Where(x => x.Value.Layer >= item.Layer), i => {
+      // generate all new extreme points parallel. This speeds up the creator.      
+      Parallel.ForEach(binPacking.Items, i => {
         PackingItem it = i.Value;
         PackingPosition pos = binPacking.Positions[i.Key];

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointPruning/ExtremePointPruning.cs

@@ -47 +47 @@
     }
 
-    public void PruneExtremePoints(BinPacking3D binPacking, int layer) {
+    public void PruneExtremePoints(BinPacking3D binPacking, int sequenceNumber) {
       var pruningPositions = new List<KeyValuePair<int, PackingPosition>>();
       var pruning = new Dictionary<BinPacking3D, List<KeyValuePair<int, PackingPosition>>>();
       pruning.Add(binPacking, pruningPositions);
-      foreach (var item in binPacking.Items.Where(x => x.Value.Layer <= layer)) {
+      foreach (var item in binPacking.Items.Where(x => x.Value.SequenceGroup <= sequenceNumber)) {
         pruningPositions.Add(new KeyValuePair<int, PackingPosition>(item.Key, binPacking.Positions[item.Key]));
       }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointPruning/IExtremePointPruning.cs

@@ -50 +50 @@
     /// <param name="binPacking"></param>
     /// <param name="layer"
-    void PruneExtremePoints(BinPacking3D binPacking, int layer);
+    void PruneExtremePoints(BinPacking3D binPacking, int sequenceNumber);
   }
 }

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/ThreeDInstanceParser.cs

@@ -56 +56 @@
             var tilt = GetNextInteger(reader);
             for (var i = 0; i < pieces; i++) {
-              PackingItem item = new PackingItem(width, height, length, Bin, weight, material) {
+              PackingItem item = new PackingItem(width, height, length, Bin, weight, 0, material) {
                 RotateEnabled = rotate == 0 ? false : true,
                 TiltEnabled = tilt == 0 ? false : true,

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs

@@ -94 +94 @@
         packingItem.Height,
         packingItem.Depth,
-        packingItem.TargetBin, packingItem.Weight, packingItem.Layer);
+        packingItem.TargetBin, 
+        packingItem.Weight, 
+        packingItem.SequenceGroup, 
+        packingItem.Layer);
 
       // The extremepoints are sortet by Y / Z / X

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerMinRSLeft.cs

@@ -112 +112 @@
         var item = items[itemId];
         var clonedPackingBin = packingBin.Clone() as BinPacking3D;
-        ExtremePointPruningFactory.CreatePruning(ExtremePointPruningMethod.PruneBehind).PruneExtremePoints(clonedPackingBin, item.Layer - 1);
+        ExtremePointPruningFactory.CreatePruning(ExtremePointPruningMethod.PruneBehind).PruneExtremePoints(clonedPackingBin, item.SequenceGroup - 1);
 
         // If an item doesn't support any weight it should have a minimum waste of the residual space.

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/PackingItem.cs

@@ -45 +45 @@
     }
 
+    public IFixedValueParameter<IntValue> SequenceGroupParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters["SequenceGroup"]; }
+    }
+
     public IFixedValueParameter<IntValue> IdParameter {
       get { return (IFixedValueParameter<IntValue>)Parameters["Id"]; }
@@ -64 +68 @@
     }
 
+    public int SequenceGroup {
+      get { return SequenceGroupParameter.Value.Value; }
+      set { SequenceGroupParameter.Value.Value = value; }
+    }
+    
     public int Id {
       get { return IdParameter.Value.Value; }
@@ -324 +333 @@
       : base() {
       Parameters.Add(new ValueParameter<PackingShape>("TargetBin"));
-      Parameters.Add(new FixedValueParameter<DoubleValue>("Weight"));
+      Parameters.Add(new FixedValueParameter<DoubleValue>("Weight"));      
       Parameters.Add(new FixedValueParameter<IntValue>("Layer"));
+      Parameters.Add(new FixedValueParameter<IntValue>("SequenceGroup"));
       Parameters.Add(new FixedValueParameter<IntValue>("Id"));
 
@@ -356 +366 @@
     }
 
-    public PackingItem(int width, int height, int depth, PackingShape targetBin, double weight, int layer)
+    public PackingItem(int width, int height, int depth, PackingShape targetBin, double weight, int sequenceNumber, int layer)
       : this(width, height, depth, targetBin) {
       this.Weight = weight;
       this.Layer = layer;
-    }
-
-
+      this.SequenceGroup = sequenceNumber;
+    }
 
     public PackingItem(PackingItem packingItem) : this() {
@@ -371 +380 @@
       Weight = packingItem.Weight;
       Layer = packingItem.Layer;
+      SequenceGroup = packingItem.SequenceGroup;
       Id = packingItem.Id;
       Rotated = packingItem.Rotated;

branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Sorting/PermutationPackingItemSorter.cs

@@ -136 +136 @@
       return new Permutation(PermutationTypes.Absolute,
                     items.Select((v, i) => new { Index = i, Item = v })
-                         .OrderBy(x => x.Item.Layer)
+                         .OrderBy(x => x.Item.SequenceGroup)
                          .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
                          .ThenByDescending(x => x.Item.Height)
@@ -150 +150 @@
       return new Permutation(PermutationTypes.Absolute,
                     items.Select((v, i) => new { Index = i, Item = v })
-                         .OrderBy(x => x.Item.Layer)
+                         .OrderBy(x => x.Item.SequenceGroup)
                          .ThenByDescending(x => x.Item.Height)
                          .ThenByDescending(x => x.Item.Depth * x.Item.Width * x.Item.Height)
@@ -164 +164 @@
       return new Permutation(PermutationTypes.Absolute,
                     items.Select((v, i) => new { Index = i, Item = v })
-                         .OrderBy(x => x.Item.Layer)
+                         .OrderBy(x => x.Item.SequenceGroup)
                          .ThenByDescending(x => x.Item.Depth * x.Item.Width)
                          .ThenByDescending(x => x.Item.Height)
@@ -178 +178 @@
       return new Permutation(PermutationTypes.Absolute,
                     items.Select((v, i) => new { Index = i, Item = v })
-                         .OrderBy(x => x.Item.Layer)
+                         .OrderBy(x => x.Item.SequenceGroup)
                          .ThenByDescending(x => x.Item.Height)
                          .ThenByDescending(x => x.Item.Depth * x.Item.Width)
@@ -198 +198 @@
                 items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Width * v.Depth / clusterRange)) })
                     .GroupBy(x => x.ClusterId)
-                    .Select(x => new { Cluster = x.Key, Items = x.OrderBy(z => z.Item.Layer).ThenByDescending(y => y.Item.Height).ToList() })
+                    .Select(x => new { Cluster = x.Key, Items = x.OrderBy(z => z.Item.SequenceGroup).ThenByDescending(y => y.Item.Height).ToList() })
                     .OrderByDescending(x => x.Cluster)
                     .SelectMany(x => x.Items)
@@ -218 +218 @@
                 items.Select((v, i) => new { Index = i, Item = v, ClusterId = (int)(Math.Ceiling(v.Height / clusterRange2)) })
                     .GroupBy(x => x.ClusterId)
-                    .Select(x => new { Cluster = x.Key, Items = x.OrderBy(z => z.Item.Layer).ThenByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
+                    .Select(x => new { Cluster = x.Key, Items = x.OrderBy(z => z.Item.SequenceGroup).ThenByDescending(y => y.Item.Depth * y.Item.Width).ToList() })
                     .OrderByDescending(x => x.Cluster)
                     .SelectMany(x => x.Items)