Changeset 15460 for branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3

Timestamp:

11/08/17 07:34:46 (7 years ago)

Author:

abeham

Message:

#2747: worked on the CFSAP

• Added problem definition that defines both sequence and assignment for a single nest
• Added problem definition that would optimizes both sequence and assignment for multiple nests
• Added interface
• Added solving strategy that would use multiple instances of a template algorithm to optimize the worst nest
• Fixed bug in parser regarding setup times

Location:

branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3

Files:

• CFSAP.cs (copied) (copied from branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/CFSAPSequenceOnly.cs) (7 diffs)
• CFSAPSequenceOnly.cs (modified) (4 diffs)
• HeuristicLab.Problems.Scheduling.CFSAP-3.3.csproj (modified) (1 diff)
• ICFSAP.cs (added)
• MultiNestCFSAP.cs (added)
• MultiNestCFSAPSolvingStrategy.cs (added)

branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/CFSAP.cs

@@ -27 +27 @@
 using HeuristicLab.Core;
 using HeuristicLab.Data;
+using HeuristicLab.Encodings.BinaryVectorEncoding;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Optimization;
@@ -34 +35 @@
 
 namespace HeuristicLab.Problems.Scheduling.CFSAP {
-  [Item("Cyclic flow shop with two machines and a single nest (CFSAP) sequencing problem", "Non-permutational cyclic flow shop scheduling problem with a single nest of two machine from W. Bozejko.")]
+  [Item("Cyclic flow shop with two machines and a single nest (CFSAP)", "Non-permutational cyclic flow shop scheduling problem with a single nest of two machine from W. Bozejko.")]
   [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
   [StorableClass]
-  public class CFSAPSequenceOnly : SingleObjectiveBasicProblem<PermutationEncoding>, IProblemInstanceConsumer<CFSAPData> {
+  public class CFSAP : SingleObjectiveBasicProblem<MultiEncoding>, ICFSAP, IProblemInstanceConsumer<CFSAPData> {
     public override bool Maximization { get { return false; } }
 
@@ -44 +45 @@
     }
 
+    public IntMatrix ProcessingTimes {
+      get { return ProcessingTimesParameter.Value; }
+      set { ProcessingTimesParameter.Value = value; }
+    }
+
     public IValueParameter<ItemList<IntMatrix>> SetupTimesParameter {
       get { return (IValueParameter<ItemList<IntMatrix>>)Parameters["SetupTimes"]; }
     }
 
+    public ItemList<IntMatrix> SetupTimes {
+      get { return SetupTimesParameter.Value; }
+      set { SetupTimesParameter.Value = value; }
+    }
+
     [StorableConstructor]
-    protected CFSAPSequenceOnly(bool deserializing) : base(deserializing) {}
-    protected CFSAPSequenceOnly(CFSAPSequenceOnly original, Cloner cloner)
+    protected CFSAP(bool deserializing) : base(deserializing) {}
+    protected CFSAP(CFSAP original, Cloner cloner)
       : base(original, cloner) {}
-    public CFSAPSequenceOnly() {
-      Parameters.Add(new ValueParameter<IntMatrix>("ProcessingTimes", "The processing times of each job for each machine nest."));
-      Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("SetupTimes", "The sequence dependent set up times among all jobs for each machine nest."));
+    public CFSAP() {
+      Parameters.Add(new ValueParameter<IntMatrix>("ProcessingTimes", "The processing times of each machine and each job."));
+      Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("SetupTimes", "The sequence dependent set up times of each machine and between all jobs."));
 
       ProcessingTimesParameter.Value = new IntMatrix(new int[,] {
@@ -77 +88 @@
       }));
 
-      Encoding.Length = 5;
+      Encoding.Add(new PermutationEncoding("sequence", 5, PermutationTypes.RelativeDirected));
+      Encoding.Add(new BinaryVectorEncoding("assignment", 5));
 
       Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);
@@ -85 +97 @@
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new CFSAPSequenceOnly(this, cloner);
+      return new CFSAP(this, cloner);
     }
 
     public override double Evaluate(Individual individual, IRandom random) {
-      var order = individual.Permutation(Encoding.Name);
-      int T = EvaluateSequence(order);
-      return T;
-    }
-
-    public int EvaluateSequence(Permutation order) {
-      var N = order.Length;
-      var processingTimes = ProcessingTimesParameter.Value;
-      var setupTimes = SetupTimesParameter.Value;
-
-      int[,,] weights = new int[2, 2 * N, 2 * N];
-      int[,] graph = new int[2, N];
-      int[,] prevPath = new int[2, N + 1];                     //Only for optimal assignment evaluation
-      int[] optimalAssignment = new int[N];                //Only for optimal assignment evaluation
-
-      //Calculate weights in the graph
-      for (int S = 0; S < N; S++) { //Starting point of the arc
-        for (int sM = 0; sM < 2; sM++) {    //Starting point machine
-          int eM = sM == 0 ? 1 : 0;
-          weights[sM, S, S + 1] = 0;
-
-          for (int E = S + 2; E < S + N; E++)
-            weights[sM, S, E] =
-              weights[sM, S, E - 1] +
-              processingTimes[eM, order[(E - 1) % N]] +
-              setupTimes[eM][order[(E - 1) % N], order[E % N]];
-
-          for (int E = S + 1; E < S + N; E++)
-            weights[sM, S, E] += (
-              processingTimes[sM, order[S % N]] +
-              setupTimes[sM][order[S % N], order[(E + 1) % N]]
-            );
-        }
-      }
-
-      //Determine the shortest path in the graph
-      int T = int.MaxValue / 2;
-      for (int S = 0; S < N - 1; S++)      //Start node in graph          O(N)
-        for (int SM = 0; SM < 2; SM++) {   //Start node machine in graph  O(1)
-          graph[SM, S] = 0;
-          graph[SM == 0 ? 1 : 0, S] = int.MaxValue / 2;
-          prevPath[SM, 0] = -1;
-          for (int E = S + 1; E < N; E++)      //Currently calculated node          O(N)
-            for (int EM = 0; EM < 2; EM++) {   //Currently calculated node machine  O(1)
-              graph[EM, E] = int.MaxValue / 2;
-              for (int EC = S; EC < E; EC++) { //Nodes connected to node E          O(N)
-                int newWeight = graph[EM == 0 ? 1 : 0, EC] + weights[EM == 0 ? 1 : 0, EC, E];
-                if (newWeight < graph[EM, E]) {
-                  graph[EM, E] = newWeight;
-                  prevPath[EM, E] = EC;
-                }
-              }
-            }
-
-          int EP = S + N; //End point.
-          int newT = int.MaxValue / 2;
-          for (int EC = S + 1; EC < N; EC++) { //Nodes connected to EP O(N)
-            int newWeight = graph[SM == 0 ? 1 : 0, EC] + weights[SM == 0 ? 1 : 0, EC, EP];
-            if (newWeight < newT) {
-              newT = newWeight;
-              prevPath[SM, S] = EC;
-            }
-          }
-
-          if (newT < T) {
-            T = newT;
-            optimalAssignment = MakeAssignement(S, SM, prevPath, order);
-          }
-        }
-
-      //Omitted solutions
-      for (int machine = 0; machine < 2; machine++) {
-        int[] assignment = Enumerable.Repeat(machine, N).ToArray();
-        int newT = EvaluateAssignement(order, assignment, processingTimes, setupTimes);
-        if (newT < T) { //New best solution has been found
-          T = newT;
-          assignment.CopyTo(optimalAssignment, N);
-        }
-      }
-
+      var order = individual.Permutation("sequence");
+      var assignment = individual.BinaryVector("assignment");
+      int T = EvaluateAssignement(order, assignment.Select(x => x ? 1 : 0).ToArray(),
+        ProcessingTimesParameter.Value, SetupTimesParameter.Value);
       return T;
     }
@@ -203 +139 @@
     }
 
-    private int[] MakeAssignement(int start, int startMach, int[,] prevPath, Permutation order) {
-      var N = order.Length;
-      int[] assignment = Enumerable.Repeat(-1, N).ToArray();
-      var inverseOrder = new int[N];
-
-      for (int i = 0; i < N; i++)
-        inverseOrder[order[i]] = i;
-
-      int end = start + N;
-
-      int currMach = startMach;
-      int currNode = start;
-      while (true) {
-        assignment[inverseOrder[currNode]] = currMach;
-        currNode = prevPath[currMach, currNode];
-        currMach = currMach == 0 ? 1 : 0;
-        if (currNode == start)
-          break;
-      }
-
-      currMach = startMach;
-      for (int i = 0; i < N; i++) {
-        if (assignment[inverseOrder[i]] != -1)
-          currMach = currMach == 0 ? 1 : 0;
-        else
-          assignment[inverseOrder[i]] = currMach;
-      }
-
-      return assignment;
+    public void UpdateEncoding() {
+      Encoding.Encodings.OfType<PermutationEncoding>().Single().Length = ProcessingTimes.Columns;
+      Encoding.Encodings.OfType<BinaryVectorEncoding>().Single().Length = ProcessingTimes.Columns;
     }
 
@@ -265 +175 @@
       }
       SetupTimesParameter.Value = setups;
-      Encoding.Length = data.Jobs;
+      UpdateEncoding();
       Name = data.Name + "-nest" + nest;
       Description = data.Description;
+      if (data.BestKnownCycleTime.HasValue)
+        BestKnownQuality = data.BestKnownCycleTime.Value;
+      else BestKnownQualityParameter.Value = null;
     }
   }

branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/CFSAPSequenceOnly.cs

@@ -44 +44 @@
     }
 
+    public IntMatrix ProcessingTimes {
+      get { return ProcessingTimesParameter.Value; }
+      set { ProcessingTimesParameter.Value = value; }
+    }
+
     public IValueParameter<ItemList<IntMatrix>> SetupTimesParameter {
       get { return (IValueParameter<ItemList<IntMatrix>>)Parameters["SetupTimes"]; }
+    }
+
+    public ItemList<IntMatrix> SetupTimes {
+      get { return SetupTimesParameter.Value; }
+      set { SetupTimesParameter.Value = value; }
     }
 
@@ -162 +172 @@
       for (int machine = 0; machine < 2; machine++) {
         int[] assignment = Enumerable.Repeat(machine, N).ToArray();
-        int newT = EvaluateAssignement(order, assignment, processingTimes, setupTimes);
+        int newT = CFSAP.EvaluateAssignement(order, assignment, processingTimes, setupTimes);
         if (newT < T) { //New best solution has been found
           T = newT;
-          assignment.CopyTo(optimalAssignment, N);
+          optimalAssignment = assignment;
         }
-      }
-
-      return T;
-    }
-
-    //Function to evaluate individual with the specified assignment
-    public static int EvaluateAssignement(Permutation order, int[] assignment, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes) {
-      var N = order.Length;
-      int T = 0;
-
-      for (int i = 0; i < N; i++) {
-        int operation = order[i];
-        int machine = assignment[operation];
-        T += processingTimes[machine, operation];
-      }
-
-      for (int machine = 0; machine < 2; machine++) {
-        int first = -1;
-        int last = -1;
-        for (int i = 0; i < N; i++) {
-          int operation = order[i];
-          if (assignment[operation] == machine) {
-            if (first == -1)
-              first = operation;
-            else
-              T += setupTimes[machine][last, operation];
-            last = operation;
-          }
-        }
-        if (last != -1 && first != -1)
-          T += setupTimes[machine][last, first];
       }
 
@@ -232 +211 @@
 
       return assignment;
+    }
+
+    public void UpdateEncoding() {
+      Encoding.Length = ProcessingTimes.Columns;
     }
 
@@ -265 +248 @@
       }
       SetupTimesParameter.Value = setups;
-      Encoding.Length = data.Jobs;
+      UpdateEncoding();
       Name = data.Name + "-nest" + nest;
       Description = data.Description;
+      if (data.BestKnownCycleTime.HasValue)
+        BestKnownQuality = data.BestKnownCycleTime.Value;
+      else BestKnownQualityParameter.Value = null;
     }
   }

branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/HeuristicLab.Problems.Scheduling.CFSAP-3.3.csproj

@@ -114 +114 @@
   <ItemGroup>
     <None Include="Plugin.cs.frame" />
+    <Compile Include="CFSAP.cs" />
     <Compile Include="CFSAPSequenceOnly.cs" />
+    <Compile Include="ICFSAP.cs" />
+    <Compile Include="MultiNestCFSAP.cs" />
+    <Compile Include="MultiNestCFSAPSolvingStrategy.cs" />
     <Compile Include="Plugin.cs" />
     <None Include="Properties\AssemblyInfo.cs.frame" />