Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
05/24/11 09:47:24 (14 years ago)
Author:
jhelm
Message:

#1329: Implemented PermutationWithRepetition Encoding. Implemented new operators for JSM Encoding.

Location:
branches/Scheduling/HeuristicLab.Problems.Scheduling/3.3/Encodings/JobSequenceMatrix
Files:
2 added
2 deleted
6 edited

Legend:

Unmodified
Added
Removed

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

    r6177 r6260  
    3030  [Item("JSMCrossover", "An operator which crosses two JSM representations.")]
    3131  [StorableClass]
    32   public abstract class JSMCrossover : JSSPCrossover, IJSMOperator {
     32  public abstract class JSMCrossover : JSSPCrossover<JSMEncoding>, IJSMOperator {
    3333
    3434    [StorableConstructor]
    … …  
    3939    }
    4040
    41     public abstract IJSSPEncoding Crossover(IRandom random, JSMEncoding parent1, JSMEncoding parent2);
     41    public abstract JSMEncoding Crossover(IRandom random, JSMEncoding parent1, JSMEncoding parent2);
    4242
    4343    public override IOperation Apply() {
    44       ItemArray<IJSSPEncoding> parents = ParentsParameter.ActualValue;
     44      ItemArray<JSMEncoding> parents = ParentsParameter.ActualValue;
    4545
    4646      ChildParameter.ActualValue =

  • branches/Scheduling/HeuristicLab.Problems.Scheduling/3.3/Encodings/JobSequenceMatrix/Crossovers/JSMJOXCrossover.cs

    r6177 r6260  
    4646    public JSMJOXCrossover() : base() { }
    4747
    48     public static IJSSPEncoding Cross(IRandom random, JSMEncoding parent1, JSMEncoding parent2) {
     48    public static JSMEncoding Cross(IRandom random, JSMEncoding p1, JSMEncoding p2) {
    4949      JSMEncoding result = new JSMEncoding();
    5050
    51       int nrOfResources = parent1.JobSequenceMatrix.Count;
    52       int nrOfJobs = parent1.JobSequenceMatrix[0].Length;
     51      int nrOfResources = p1.JobSequenceMatrix.Count;
     52      int nrOfJobs = p1.JobSequenceMatrix[0].Length;
    5353
    5454      //Determine randomly which jobindexes persist
    … …  
    5656      for (int i = 0; i < persist.Length; i++) {
    5757        persist[i] = random.Next(2) == 1;
    58       }
     58      }   
     59
     60      bool dominantParent = random.Next(2) == 1;
     61      JSMEncoding parent1 = dominantParent ? p1 : p2;
     62      JSMEncoding parent2 = dominantParent ? p2 : p1;
    5963
    6064      //Fill childmatrix with values
    … …  
    7781    }
    7882
    79     public override IJSSPEncoding Crossover(IRandom random, JSMEncoding parent1, JSMEncoding parent2) {
     83    public override JSMEncoding Crossover(IRandom random, JSMEncoding parent1, JSMEncoding parent2) {
    8084      return Cross(random, parent1, parent2);
    8185    }

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

    r6177 r6260  
    4545    public JSMSXXCrossover () : base () {}
    4646
    47     public static IJSSPEncoding Cross(IRandom random, JSMEncoding parent1, JSMEncoding parent2) {
     47    public static JSMEncoding Cross(IRandom random, JSMEncoding parent1, JSMEncoding parent2) {
    4848      JSMEncoding result = new JSMEncoding();
    4949
    50       int subSequenceLength = 3;
     50      int subSequenceLength = random.Next (parent1.JobSequenceMatrix[0].Length);
    5151
    5252      for (int i = 0; i < parent1.JobSequenceMatrix.Count; i++) {
    … …  
    102102
    103103
    104     public override IJSSPEncoding Crossover(IRandom random, JSMEncoding parent1, JSMEncoding parent2) {
     104    public override JSMEncoding Crossover(IRandom random, JSMEncoding parent1, JSMEncoding parent2) {
    105105      return Cross(random, parent1, parent2);
    106106    }

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

    r6177 r6260  
    4141      : base(original, cloner) {
    4242        this.resultingSchedule = cloner.Clone(original.resultingSchedule);
     43        this.jobs = cloner.Clone(original.jobs);
    4344        this.decodingErrorPolicy = original.decodingErrorPolicy;
    4445        this.forcingStrategy = original.forcingStrategy;
    … …  
    5253    }
    5354
     55    #region Private Members
    5456    [Storable]
    5557    private Schedule resultingSchedule;
    5658
    5759    [Storable]
     60    private ItemList<JSSPJob> jobs;
     61
     62    [Storable]
    5863    private JSMDecodingErrorPolicyTypes decodingErrorPolicy = JSMDecodingErrorPolicyTypes.GuidedPolicy;
    5964
    6065    [Storable]
    61     private JSMForcingStrategyTypes forcingStrategy = JSMForcingStrategyTypes.ShiftForcing;
     66    private JSMForcingStrategyTypes forcingStrategy = JSMForcingStrategyTypes.ShiftForcing;
     67    #endregion
    6268
    6369    public JSMDecoder()
    … …  
    6672    }
    6773
    68     private ItemList<JSSPTask> GetEarliestNotScheduledTasks(ItemList<JSSPJob> jobs) {
     74    private ItemList<JSSPTask> GetEarliestNotScheduledTasks() {
    6975      ItemList<JSSPTask> result = new ItemList<JSSPTask>();
    7076      foreach (JSSPJob j in jobs) {
    … …  
    7985    }
    8086    private JSSPTask GetTaskWithMinimalEC(ItemList<JSSPTask> earliestTasksList) {
    81       DoubleValue minEct = new DoubleValue(Double.MaxValue);
     87      double minEct = double.MaxValue;
    8288      JSSPTask result = null;
    8389      foreach (JSSPTask t in earliestTasksList) {
    84         DoubleValue ect = ComputeEarliestCompletionTime(t);
    85         if (ect.Value < minEct.Value) {
     90        double ect = resultingSchedule.ComputeEarliestCompletionTime(t, jobs[t.JobNr.Value]);
     91        if (ect < minEct) {
    8692          result = t;
    8793          minEct = ect;
    … …  
    9298    private ItemList<JSSPTask> GetConflictSetForTask(JSSPTask conflictedTask, ItemList<JSSPTask> earliestTasksList) {
    9399      ItemList<JSSPTask> result = new ItemList<JSSPTask>();
    94       DoubleValue conflictedCompletionTime = ComputeEarliestCompletionTime(conflictedTask);
     100      double conflictedCompletionTime = resultingSchedule.ComputeEarliestCompletionTime(conflictedTask, jobs[conflictedTask.JobNr.Value]);
    95101      result.Add(conflictedTask);
    96102      foreach (JSSPTask t in earliestTasksList) {
    97103        if (t.ResourceNr.Value == conflictedTask.ResourceNr.Value) {
    98           if (ComputeEarliestStartTime(t).Value < conflictedCompletionTime.Value)
     104          if (resultingSchedule.ComputeEarliestStartTime(t, jobs[t.JobNr.Value]) < conflictedCompletionTime)
    99105            result.Add(t);
    100106        }
    … …  
    102108      return result;
    103109    }
    104     private JSSPTask SelectTaskFromConflictSet(IntValue conflictedResource, ItemList<JSSPTask> conflictSet, ItemList<Permutation> jsm) {
    105       JSSPTask result = null;
    106       IntValue progressOnResource = new IntValue (resultingSchedule.Resources[conflictedResource.Value].Tasks.Count);
    107 
    108       if (progressOnResource.Value < jsm[conflictedResource.Value].Length) {
    109         IntValue solutionCandidateJobNr = new IntValue(jsm[conflictedResource.Value][progressOnResource.Value]);
    110         foreach (JSSPTask t in conflictSet) {
    111           if (t.Job.Index.Value == solutionCandidateJobNr.Value)
    112             result = t;
    113         }
     110    private JSSPTask SelectTaskFromConflictSet(int conflictedResourceNr, int progressOnConflictedResource, ItemList<JSSPTask> conflictSet, ItemList<Permutation> jsm) {
     111      if (conflictSet.Count == 1)
     112        return conflictSet[0];
     113     
     114      //get solutionCandidate from jobSequencingMatrix
     115      int solutionCandidateJobNr = jsm[conflictedResourceNr][progressOnConflictedResource];
     116
     117      //scan conflictSet for given solutionCandidate, and return if found
     118      foreach (JSSPTask t in conflictSet) {
     119        if (t.JobNr.Value == solutionCandidateJobNr)
     120          return t;
     121      }
     122
     123      //if solutionCandidate wasn't found in conflictSet apply DecodingErrorPolicy and ForcingPolicy
     124      JSSPTask result = ApplyDecodingErrorPolicy(conflictSet, jsm[conflictedResourceNr], progressOnConflictedResource);
     125      int newResolutionIndex = 0;
     126
     127      while (newResolutionIndex < jsm[conflictedResourceNr].Length && jsm[conflictedResourceNr][newResolutionIndex] != result.JobNr.Value)
     128        newResolutionIndex++;
     129      ApplyForcingStrategy(jsm, conflictedResourceNr, newResolutionIndex, progressOnConflictedResource, result.JobNr.Value);
     130
     131      return result;
     132    }
     133    private JSSPTask ApplyDecodingErrorPolicy(ItemList<JSSPTask> conflictSet, Permutation resource, int progress) {
     134      if (decodingErrorPolicy == JSMDecodingErrorPolicyTypes.RandomPolicy) {
     135        //Random
     136        return conflictSet[RandomParameter.ActualValue.Next(conflictSet.Count - 1)];
    114137      } else {
    115         return null;
    116       }
    117 
    118       //Repairing happens here
    119       if (result == null) {
    120         //Decoding Error Policy BEGIN
    121         //CHOOSE OTHER RESOLUTION FOR CONFLICT SET
    122         result = ApplyDecodingErrorPolicy(conflictSet);
    123         //result = conflictSet[RandomParameter.ActualValue.Next(conflictSet.Count - 1)];
    124         //Decoding Error Policy END
    125 
    126 
    127         //Determine index of new resolution
    128         int index = 0;
    129         while (index < jsm[conflictedResource.Value].Length &&
    130           jsm[conflictedResource.Value][index] != result.Job.Index.Value)
    131           index++;
    132 
    133 
    134         //Forcing Strategy BEGIN
    135         ApplyForcingStrategy(jsm, conflictedResource.Value, index, progressOnResource.Value, result.Job.Index.Value);
    136        
    137         //ForcingStrategy END
    138       }
    139       return result;
    140     }
    141 
     138        //Guided
     139        for (int i = progress; i < resource.Length; i++) {
     140          int j = 0;
     141          while (j < conflictSet.Count && conflictSet[j].JobNr.Value != resource[i])
     142            j++;
     143
     144          if (j < conflictSet.Count)
     145            return (conflictSet[j]);
     146        }
     147        return conflictSet[RandomParameter.ActualValue.Next(conflictSet.Count - 1)];
     148      }   
     149    }
    142150    private void ApplyForcingStrategy(ItemList<Permutation> jsm, int conflictedResource, int newResolutionIndex, int progressOnResource, int newResolution) {
    143       //if (forcingStrategy == JSMForcingStrategyTypes.SwapForcing) {
     151      if (forcingStrategy == JSMForcingStrategyTypes.SwapForcing) {
    144152        //SwapForcing
    145153        jsm[conflictedResource][newResolutionIndex] = jsm[conflictedResource][progressOnResource];
    146154        jsm[conflictedResource][progressOnResource] = newResolution;
    147       /*} else {
     155      } else {
    148156        //ShiftForcing
    149 
    150       } */
    151     }
    152 
    153     private JSSPTask ApplyDecodingErrorPolicy(ItemList<JSSPTask> conflictSet) {
    154       //if (decodingErrorPolicy == JSMDecodingErrorPolicyTypes.RandomPolicy) {
    155         //Random
    156         return conflictSet[RandomParameter.ActualValue.Next(conflictSet.Count - 1)];
    157       /*} else {
    158         //Guided
    159 
    160       }    */
    161     }
    162     private DoubleValue ComputeEarliestStartTime(JSSPTask t) {
    163       Resource affectedResource = resultingSchedule.Resources[t.ResourceNr.Value];
    164 
    165       DoubleValue lastMachineEndTime = affectedResource.TotalDuration;
    166       DoubleValue previousJoboperationEndTime = new DoubleValue(double.MinValue);
    167       if (t.PreviousTask != null)
    168         previousJoboperationEndTime = t.PreviousTask.EndTime;
    169 
    170       return new DoubleValue(Math.Max(previousJoboperationEndTime.Value, lastMachineEndTime.Value));
    171     }
    172     private DoubleValue ComputeEarliestCompletionTime(JSSPTask t) {
    173       return new DoubleValue(ComputeEarliestStartTime(t).Value + t.Duration.Value);
    174     }
    175     private void AddTaskToSchedule(JSSPTask selectedTask) {
    176       Resource affectedResource = resultingSchedule.Resources[selectedTask.ResourceNr.Value];
    177       selectedTask.StartTime = ComputeEarliestStartTime(selectedTask);
    178       selectedTask.IsScheduled.Value = true;
    179       affectedResource.Tasks.Add(selectedTask);
    180     }
    181 
    182     public override Schedule CreateScheduleFromEncoding(JSMEncoding solution) {
     157        List<int> asList = jsm[conflictedResource].ToList<int>();
     158        if (newResolutionIndex > progressOnResource) {
     159          asList.RemoveAt(newResolutionIndex);
     160          asList.Insert(progressOnResource, newResolution);
     161        } else {
     162          asList.Insert(progressOnResource, newResolution);
     163          asList.RemoveAt(newResolutionIndex);
     164        }
     165        jsm[conflictedResource] = new Permutation (PermutationTypes.Absolute, asList.ToArray<int>());
     166      }
     167    }
     168
     169    public Schedule CreateScheduleFromEncoding(JSMEncoding solution, ItemList<JSSPJob> jobData) {
    183170      ItemList<Permutation> jobSequenceMatrix = solution.JobSequenceMatrix;
    184171
    185       resultingSchedule = new Schedule(new IntValue(Jobs[0].Tasks.Count));
     172      jobs = (ItemList<JSSPJob>)jobData.Clone();
     173      resultingSchedule = new Schedule(new IntValue(jobs[0].Tasks.Count));
    186174
    187175      //Reset scheduled tasks in result
    188       foreach (JSSPJob j in Jobs) {
     176      foreach (JSSPJob j in jobs) {
    189177        foreach (JSSPTask t in j.Tasks) {
    190178          t.IsScheduled.Value = false;
    … …  
    194182      //GT-Algorithm
    195183      //STEP 0 - Compute a list of "earliest operations"
    196       ItemList<JSSPTask> earliestTasksList = GetEarliestNotScheduledTasks(Jobs);
     184      ItemList<JSSPTask> earliestTasksList = GetEarliestNotScheduledTasks();
    197185      while (earliestTasksList.Count > 0) {
    198186        //STEP 1 - Get earliest not scheduled operation with minimal earliest completing time
    199187        JSSPTask minimal = GetTaskWithMinimalEC(earliestTasksList);
    200 
    201         //STEP 2 - Compute a conflict set of all operations that can be scheduled on the machine the previously selected operation runs on
     188        int conflictedResourceNr = minimal.ResourceNr.Value;
     189        Resource conflictedResource = resultingSchedule.Resources[conflictedResourceNr];
     190
     191        //STEP 2 - Compute a conflict set of all operations that can be scheduled on the conflicted resource
    202192        ItemList<JSSPTask> conflictSet = GetConflictSetForTask(minimal, earliestTasksList);
    203193
    204         //STEP 3 - Select an operation from the conflict set (various methods depending on how the algorithm should work..)
    205         JSSPTask selectedTask = SelectTaskFromConflictSet(minimal.ResourceNr, conflictSet, jobSequenceMatrix);
    206 
    207         //STEP 4 - Adding the selected operation to the current schedule
    208         AddTaskToSchedule(selectedTask);
     194        //STEP 3 - Select a task from the conflict set
     195        int progressOnResource = conflictedResource.Tasks.Count;
     196        JSSPTask selectedTask = SelectTaskFromConflictSet(conflictedResourceNr, progressOnResource, conflictSet, jobSequenceMatrix);
     197
     198        //STEP 4 - Add the selected task to the current schedule
     199        selectedTask.IsScheduled.Value = true;
     200        resultingSchedule.AddTask(selectedTask, jobs[selectedTask.JobNr.Value]);
    209201
    210202        //STEP 5 - Back to STEP 1
    211         earliestTasksList = GetEarliestNotScheduledTasks(Jobs);
     203        earliestTasksList = GetEarliestNotScheduledTasks();
    212204      }
    213205
    214206      return resultingSchedule;
     207    }
     208
     209    public override Schedule CreateScheduleFromEncoding(JSMEncoding solution) {
     210      return CreateScheduleFromEncoding(solution, Jobs);
    215211    }
    216212

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

    r6177 r6260  
    3636  [Item("Job Sequencing Matrix Encoding", "Represents a solution for a standard JobShop Scheduling Problem.")]
    3737  [StorableClass]
    38   public class JSMEncoding : ParameterizedNamedItem, IJSSPEncoding{
     38  public class JSMEncoding : ParameterizedNamedItem, ISchedulingEncoding{
    3939    [StorableConstructor]
    4040    protected JSMEncoding(bool deserializing) : base(deserializing) { }

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

    r6177 r6260  
    3232  [Item("AlbaManipulator", "An operator which manipulates a VRP representation.")]
    3333  [StorableClass]
    34   public abstract class JSMManipulator : JSSPManipulator, IJSMOperator {
     34  public abstract class JSMManipulator : JSSPManipulator<JSMEncoding>, IJSMOperator {
    3535    [StorableConstructor]
    3636    protected JSMManipulator(bool deserializing) : base(deserializing) { }
    … …  
    4444
    4545    public override IOperation Apply() {
    46       IJSSPEncoding solution = SchedulingSolutionParameter.ActualValue;
     46      JSMEncoding solution = SchedulingSolutionParameter.ActualValue;
    4747
    48       SchedulingSolutionParameter.ActualValue = Manipulate(RandomParameter.ActualValue, solution as JSMEncoding);
     48      int nrOfMutations = RandomParameter.ActualValue.Next(5) + 1;
     49
     50      for (int i = 0; i < nrOfMutations; i++ )
     51        SchedulingSolutionParameter.ActualValue = Manipulate(RandomParameter.ActualValue, solution as JSMEncoding);
    4952
    5053      return base.Apply();
Note: See TracChangeset for help on using the changeset viewer.