Changeset 6177 for branches/Scheduling/HeuristicLab.Problems.Scheduling/3.3/Encodings/JobSequenceMatrix

Timestamp:

05/10/11 17:25:35 (14 years ago)

Author:

jhelm

Message:

#1329: Implemented PriorityRulesVector based encoding and added new operators to the JSMEncoding. Added Gantt-Charts for visualization of schedules and problems.

Location:

branches/Scheduling/HeuristicLab.Problems.Scheduling/3.3/Encodings/JobSequenceMatrix

Files:

• Crossovers/JSMCrossover.cs (modified) (2 diffs)
• Crossovers/JSMJOXCrossover.cs (added)
• Crossovers/JSMOrderCrossover.cs (added)
• Crossovers/JSMSXXCrossover.cs (modified) (2 diffs)
• JSMDecoder.cs (modified) (6 diffs)
• JSMDecodingErrorPolicyTypes.cs (added)
• JSMEncoding.cs (modified) (2 diffs)
• JSMForcingStrategyTypes.cs (added)
• JSMRandomCreator.cs (modified) (1 diff)
• Manipulators/JSMInsertionManipulator.cs (added)
• Manipulators/JSMManipulator.cs (modified) (3 diffs)
• Manipulators/JSMShiftChangeManipulator.cs (added)
• Manipulators/JSMSwapManipulator.cs (deleted)

branches/Scheduling/HeuristicLab.Problems.Scheduling/3.3/Encodings/JobSequenceMatrix/Crossovers/JSMCrossover.cs

@@ -30 +30 @@
   [Item("JSMCrossover", "An operator which crosses two JSM representations.")]
   [StorableClass]
-  public abstract class JSMCrossover : JSSPCrossover, IStochasticOperator, IJSMOperator {
-    public ILookupParameter<IRandom> RandomParameter {
-      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
-    }
+  public abstract class JSMCrossover : JSSPCrossover, IJSMOperator {
 
     [StorableConstructor]
@@ -40 +37 @@
     public JSMCrossover()
       : base() {
-      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
     }
 
-    protected abstract JSSPEncoding Crossover(IRandom random, JSMEncoding parent1, JSMEncoding parent2);
+    public abstract IJSSPEncoding Crossover(IRandom random, JSMEncoding parent1, JSMEncoding parent2);
 
     public override IOperation Apply() {
-      ItemArray<JSSPEncoding> parents = ParentsParameter.ActualValue;
+      ItemArray<IJSSPEncoding> parents = ParentsParameter.ActualValue;
 
       ChildParameter.ActualValue =

branches/Scheduling/HeuristicLab.Problems.Scheduling/3.3/Encodings/JobSequenceMatrix/Crossovers/JSMSXXCrossover.cs

@@ -27 +27 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Core;
+using HeuristicLab.Problems.Scheduling.Interfaces;
+using HeuristicLab.Encodings.PermutationEncoding;
 
 namespace HeuristicLab.Problems.Scheduling.Encodings.JobSequenceMatrix.Crossovers {
-  [Item("JSM Subsequence Exchange Crossover", "Represents a crossover operation swapping subsequences of the parents to generate offspring.")]
+  [Item("JSM Subsequence Exchange Crossover", "Represents a crossover operation identifiying and exchanging equal subsequences of the parents to generate offspring.")]
   [StorableClass]
   public class JSMSXXCrossover : JSMCrossover {
@@ -43 +45 @@
     public JSMSXXCrossover () : base () {}
 
-    protected override JSSPEncoding Crossover(IRandom random, JSMEncoding parent1, JSMEncoding parent2) {
-      JSSPEncoding result = parent1;
+    public static IJSSPEncoding Cross(IRandom random, JSMEncoding parent1, JSMEncoding parent2) {
+      JSMEncoding result = new JSMEncoding();
 
+      int subSequenceLength = 3;
+
+      for (int i = 0; i < parent1.JobSequenceMatrix.Count; i++) {
+        Permutation p1 = (Permutation)parent1.JobSequenceMatrix[i].Clone();
+        Permutation p2 = (Permutation)parent2.JobSequenceMatrix[i].Clone();
+        FindAndExchangeSubsequences(p1, p2, subSequenceLength);
+        //parent1.JobSequenceMatrix[i] = p1;
+        //parent2.JobSequenceMatrix[i] = p2;
+
+        result.JobSequenceMatrix.Add(p1);
+      }
 
       return result;
     }
+
+    private static void FindAndExchangeSubsequences(Permutation p1, Permutation p2, int subSequenceLength) {
+      for (int i = 0; i <= p1.Length - subSequenceLength; i++) {
+        for (int j = 0; j <= p2.Length - subSequenceLength; j++) {
+          int[] ss1 = GetSubSequenceAtPosition(p1, i, subSequenceLength);
+          int[] ss2 = GetSubSequenceAtPosition(p2, j, subSequenceLength);
+          if (AreEqualSubsequences(ss1, ss2)) {
+            ExchangeSubsequences(p1, i, p2, j, subSequenceLength);
+            break;
+          }
+        }
+      }
+    }
+    private static void ExchangeSubsequences(Permutation p1, int index1, Permutation p2, int index2, int subSequenceLength) {
+      Permutation aux = (Permutation)p1.Clone();
+      for (int i = 0; i < subSequenceLength; i++) {
+        p1[i + index1] = p2[i + index2];
+        p2[i + index2] = aux[i + index1];
+      }
+    }
+    private static bool AreEqualSubsequences(int[] ss1, int[] ss2) {
+      int counter = 0;
+      for (int i = 0; i < ss1.Length; i++) {
+        for (int j = 0; j < ss2.Length; j++) {
+          if (ss1[i] == ss2[j])
+            counter++;
+        }
+      }
+      return counter == ss1.Length;
+    }
+    private static int[] GetSubSequenceAtPosition(Permutation p1, int index, int subSequenceLength) {
+      int[] result = new int[subSequenceLength];
+      for (int i = 0; i < subSequenceLength; i++)
+        result[i] = p1[i + index];
+
+      return result;
+    }
+
+
+
+    public override IJSSPEncoding Crossover(IRandom random, JSMEncoding parent1, JSMEncoding parent2) {
+      return Cross(random, parent1, parent2);
+    } 
   }
 }

branches/Scheduling/HeuristicLab.Problems.Scheduling/3.3/Encodings/JobSequenceMatrix/JSMDecoder.cs

@@ -35 +35 @@
   [Item("Job Sequencing Matrix Decoder", "Applies the GifflerThompson algorithm to create an active schedule from a JobSequencing Matrix.")]
   [StorableClass]
-  public class JSMDecoder : NamedItem {
+  public class JSMDecoder : JSSPDecoder<JSMEncoding>, IStochasticOperator {
     [StorableConstructor]
     protected JSMDecoder(bool deserializing) : base(deserializing) { }
@@ -41 +41 @@
       : base(original, cloner) {
         this.resultingSchedule = cloner.Clone(original.resultingSchedule);
+        this.decodingErrorPolicy = original.decodingErrorPolicy;
+        this.forcingStrategy = original.forcingStrategy;
     }
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -46 +48 @@
     }
 
+    public ILookupParameter<IRandom> RandomParameter {
+      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
+    }
+
     [Storable]
     private Schedule resultingSchedule;
 
     [Storable]
-    private IRandom random;
-
-    public JSMDecoder(IntValue nrOfResources, IRandom r)
+    private JSMDecodingErrorPolicyTypes decodingErrorPolicy = JSMDecodingErrorPolicyTypes.GuidedPolicy;
+
+    [Storable]
+    private JSMForcingStrategyTypes forcingStrategy = JSMForcingStrategyTypes.ShiftForcing;
+
+    public JSMDecoder()
       : base() {
-      resultingSchedule = new Schedule(nrOfResources);
-      random = r;
-    }
-
-
-    public Schedule CreateScheduleFromJSM(ItemList<JSSPJob> jobs, ItemList<Permutation> jobSequenceMatrix) {
-      //Reset scheduled tasks in result
-      foreach (JSSPJob j in jobs) {
-        foreach (JSSPTask t in j.Tasks) {
-          t.IsScheduled.Value = false;
-        }
-      }
-
-      //GT-Algorithm
-      //STEP 0 - Compute a list of "earliest operations"
-      ItemList<JSSPTask> earliestTasksList = GetEarliestNotScheduledTasks(jobs);
-      while (earliestTasksList.Count > 0) {
-        //STEP 1 - Get earliest not scheduled operation with minimal earliest completing time
-        JSSPTask minimal = GetTaskWithMinimalEC(earliestTasksList);
-
-        //STEP 2 - Compute a conflict set of all operations that can be scheduled on the machine the previously selected operation runs on
-        ItemList<JSSPTask> conflictSet = GetConflictSetForTask(minimal, earliestTasksList);
-
-        //STEP 3 - Select an operation from the conflict set (various methods depending on how the algorithm should work..)
-        JSSPTask selectedTask = SelectTaskFromConflictSet(minimal.ResourceNr, conflictSet, jobSequenceMatrix);
-
-        //STEP 4 - Adding the selected operation to the current schedule
-        AddTaskToSchedule(selectedTask);
-
-        //STEP 5 - Back to STEP 1
-        earliestTasksList = GetEarliestNotScheduledTasks(jobs);
-      }
-
-      return resultingSchedule;
-    }
+      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
+    }
+
     private ItemList<JSSPTask> GetEarliestNotScheduledTasks(ItemList<JSSPJob> jobs) {
       ItemList<JSSPTask> result = new ItemList<JSSPTask>();
@@ -132 +109 @@
         IntValue solutionCandidateJobNr = new IntValue(jsm[conflictedResource.Value][progressOnResource.Value]);
         foreach (JSSPTask t in conflictSet) {
-          if (t.Job.JobIndex == solutionCandidateJobNr)
+          if (t.Job.Index.Value == solutionCandidateJobNr.Value)
             result = t;
         }
@@ -141 +118 @@
       //Repairing happens here
       if (result == null) {
-        result = conflictSet[random.Next(conflictSet.Count - 1)];
+        //Decoding Error Policy BEGIN
+        //CHOOSE OTHER RESOLUTION FOR CONFLICT SET
+        result = ApplyDecodingErrorPolicy(conflictSet);
+        //result = conflictSet[RandomParameter.ActualValue.Next(conflictSet.Count - 1)];
+        //Decoding Error Policy END
+
+
+        //Determine index of new resolution
         int index = 0;
-        foreach (int jobAssignment in jsm[conflictedResource.Value]) {
-          if (jobAssignment == result.Job.JobIndex.Value)
-            break;
+        while (index < jsm[conflictedResource.Value].Length && 
+          jsm[conflictedResource.Value][index] != result.Job.Index.Value)
           index++;
-        }
-        jsm[conflictedResource.Value][index] = jsm[conflictedResource.Value][progressOnResource.Value];
-        jsm[conflictedResource.Value][progressOnResource.Value] = result.Job.JobIndex.Value;
-      }
-       
-
-      return result;
+
+
+        //Forcing Strategy BEGIN
+        ApplyForcingStrategy(jsm, conflictedResource.Value, index, progressOnResource.Value, result.Job.Index.Value);
+        
+        //ForcingStrategy END
+      }
+      return result;
+    }
+
+    private void ApplyForcingStrategy(ItemList<Permutation> jsm, int conflictedResource, int newResolutionIndex, int progressOnResource, int newResolution) {
+      //if (forcingStrategy == JSMForcingStrategyTypes.SwapForcing) {
+        //SwapForcing
+        jsm[conflictedResource][newResolutionIndex] = jsm[conflictedResource][progressOnResource];
+        jsm[conflictedResource][progressOnResource] = newResolution;
+      /*} else {
+        //ShiftForcing
+
+      } */
+    }
+
+    private JSSPTask ApplyDecodingErrorPolicy(ItemList<JSSPTask> conflictSet) {
+      //if (decodingErrorPolicy == JSMDecodingErrorPolicyTypes.RandomPolicy) { 
+        //Random
+        return conflictSet[RandomParameter.ActualValue.Next(conflictSet.Count - 1)];
+      /*} else {
+        //Guided
+
+      }    */
     }
     private DoubleValue ComputeEarliestStartTime(JSSPTask t) {
@@ -174 +179 @@
       affectedResource.Tasks.Add(selectedTask);
     }
+
+    public override Schedule CreateScheduleFromEncoding(JSMEncoding solution) {
+      ItemList<Permutation> jobSequenceMatrix = solution.JobSequenceMatrix;
+
+      resultingSchedule = new Schedule(new IntValue(Jobs[0].Tasks.Count));
+
+      //Reset scheduled tasks in result
+      foreach (JSSPJob j in Jobs) {
+        foreach (JSSPTask t in j.Tasks) {
+          t.IsScheduled.Value = false;
+        }
+      }
+
+      //GT-Algorithm
+      //STEP 0 - Compute a list of "earliest operations"
+      ItemList<JSSPTask> earliestTasksList = GetEarliestNotScheduledTasks(Jobs);
+      while (earliestTasksList.Count > 0) {
+        //STEP 1 - Get earliest not scheduled operation with minimal earliest completing time
+        JSSPTask minimal = GetTaskWithMinimalEC(earliestTasksList);
+
+        //STEP 2 - Compute a conflict set of all operations that can be scheduled on the machine the previously selected operation runs on
+        ItemList<JSSPTask> conflictSet = GetConflictSetForTask(minimal, earliestTasksList);
+
+        //STEP 3 - Select an operation from the conflict set (various methods depending on how the algorithm should work..)
+        JSSPTask selectedTask = SelectTaskFromConflictSet(minimal.ResourceNr, conflictSet, jobSequenceMatrix);
+
+        //STEP 4 - Adding the selected operation to the current schedule
+        AddTaskToSchedule(selectedTask);
+
+        //STEP 5 - Back to STEP 1
+        earliestTasksList = GetEarliestNotScheduledTasks(Jobs);
+      }
+
+      return resultingSchedule;
+    }
+
+    public override IOperation Apply() {
+      return base.Apply();
+    } 
   }
 }

branches/Scheduling/HeuristicLab.Problems.Scheduling/3.3/Encodings/JobSequenceMatrix/JSMEncoding.cs

@@ -29 +29 @@
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Data;
-using HeuristicLab.Problems.Scheduling.Encodings;
+using HeuristicLab.Problems.Scheduling.Interfaces;
+using HeuristicLab.Problems.Scheduling.Encodings.JobSequenceMatrix.Crossovers;
+using HeuristicLab.Problems.Scheduling.Encodings.JobSequenceMatrix.Manipulators;
 
 namespace HeuristicLab.Problems.Scheduling.Encodings.JobSequenceMatrix {
   [Item("Job Sequencing Matrix Encoding", "Represents a solution for a standard JobShop Scheduling Problem.")]
   [StorableClass]
-  public class JSMEncoding : JSSPEncoding{
+  public class JSMEncoding : ParameterizedNamedItem, IJSSPEncoding{
     [StorableConstructor]
     protected JSMEncoding(bool deserializing) : base(deserializing) { }
@@ -52 +54 @@
     }
 
-    public override Schedule ToSchedule(IntValue nrOfResources, ItemList<JSSPJob> jobs, IRandom random) {
-      JSMDecoder decoder = new JSMDecoder(nrOfResources, random);
-      return decoder.CreateScheduleFromJSM (jobs, JobSequenceMatrix);
-    }
-
     public override string ToString() {
       StringBuilder sb = new StringBuilder();

branches/Scheduling/HeuristicLab.Problems.Scheduling/3.3/Encodings/JobSequenceMatrix/JSMRandomCreator.cs

@@ -64 +64 @@
       JSMEncoding solution = new JSMEncoding();
       IntValue nrOfJobs = new IntValue (Jobs.Count);
-      IntValue nrOfResources = NrOfResources;
+      IntValue nrOfResources = new IntValue (Jobs[0].Tasks.Count);
 
       for (int i = 0; i < nrOfResources.Value; i++) {

branches/Scheduling/HeuristicLab.Problems.Scheduling/3.3/Encodings/JobSequenceMatrix/Manipulators/JSMManipulator.cs

@@ -32 +32 @@
   [Item("AlbaManipulator", "An operator which manipulates a VRP representation.")]
   [StorableClass]
-  public abstract class JSMManipulator : JSSPManipulator, IStochasticOperator, IJSMOperator {
-    public ILookupParameter<IRandom> RandomParameter {
-      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
-    }
-
+  public abstract class JSMManipulator : JSSPManipulator, IJSMOperator {
     [StorableConstructor]
     protected JSMManipulator(bool deserializing) : base(deserializing) { }
@@ -42 +38 @@
     public JSMManipulator()
       : base() {
-      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
     }
 
@@ -49 +44 @@
 
     public override IOperation Apply() {
-      JSSPEncoding solution = SchedulingSolutionParameter.ActualValue;
+      IJSSPEncoding solution = SchedulingSolutionParameter.ActualValue;
 
       SchedulingSolutionParameter.ActualValue = Manipulate(RandomParameter.ActualValue, solution as JSMEncoding);