Free cookie consent management tool by TermsFeed Policy Generator

source: branches/ProblemRefactoring/HeuristicLab.Encodings.ScheduleEncoding/3.3/JobSequenceMatrix/Decoder/JSMDecoder.cs @ 15071

Last change on this file since 15071 was 13469, checked in by mkommend, 9 years ago

#2521: Refactored problem base classes and adapted scheduling encoding, scheduling problem and unit tests.

File size: 8.3 KB
RevLine 
[6293]1#region License Information
2/* HeuristicLab
[12012]3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[6293]4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
[8887]22using System;
[6293]23using System.Collections.Generic;
24using System.Linq;
[6406]25using HeuristicLab.Common;
[6293]26using HeuristicLab.Core;
[13449]27using HeuristicLab.Data;
[6293]28using HeuristicLab.Encodings.PermutationEncoding;
29using HeuristicLab.Parameters;
[6406]30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
[13443]31using HeuristicLab.Random;
[6293]32
[13443]33namespace HeuristicLab.Encodings.ScheduleEncoding {
[6406]34  [Item("JobSequenceMatrixDecoder", "Applies the GifflerThompson algorithm to create an active schedule from a JobSequence Matrix.")]
[6293]35  [StorableClass]
[13469]36  public class JSMDecoder : ScheduleDecoder<JSMEncoding> {
[8887]37
[13449]38    public IFixedValueParameter<EnumValue<JSMDecodingErrorPolicy>> DecodingErrorPolicyParameter {
39      get { return (IFixedValueParameter<EnumValue<JSMDecodingErrorPolicy>>)Parameters["DecodingErrorPolicy"]; }
[8887]40    }
[13449]41    public IFixedValueParameter<EnumValue<JSMForcingStrategy>> ForcingStrategyParameter {
42      get { return (IFixedValueParameter<EnumValue<JSMForcingStrategy>>)Parameters["ForcingStrategy"]; }
[8887]43    }
[6293]44
[13449]45    private JSMDecodingErrorPolicy DecodingErrorPolicy {
[8887]46      get { return DecodingErrorPolicyParameter.Value.Value; }
47    }
[6293]48
[13449]49    private JSMForcingStrategy ForcingStrategy {
[8887]50      get { return ForcingStrategyParameter.Value.Value; }
51    }
[6293]52
[6406]53    [StorableConstructor]
54    protected JSMDecoder(bool deserializing) : base(deserializing) { }
[8887]55    protected JSMDecoder(JSMDecoder original, Cloner cloner) : base(original, cloner) { }
[6406]56    public override IDeepCloneable Clone(Cloner cloner) {
57      return new JSMDecoder(this, cloner);
58    }
59
[6293]60    public JSMDecoder()
61      : base() {
[13449]62      Parameters.Add(new FixedValueParameter<EnumValue<JSMDecodingErrorPolicy>>("DecodingErrorPolicy", "Specify the policy that should be used to handle decoding errors.", new EnumValue<JSMDecodingErrorPolicy>(JSMDecodingErrorPolicy.RandomPolicy)));
63      Parameters.Add(new FixedValueParameter<EnumValue<JSMForcingStrategy>>("ForcingStrategy", "Specifies a forcing strategy.", new EnumValue<JSMForcingStrategy>(JSMForcingStrategy.SwapForcing)));
[6293]64    }
65
[13449]66    private static Task SelectTaskFromConflictSet(JSMEncoding solution, JSMDecodingErrorPolicy decodingErrorPolicy, JSMForcingStrategy forcingStrategy, int conflictedResourceNr, int progressOnConflictedResource, ItemList<Task> conflictSet, IRandom random) {
[6293]67      if (conflictSet.Count == 1)
68        return conflictSet[0];
[6406]69
[13443]70      var jsm = solution.JobSequenceMatrix;
71
[6293]72      //get solutionCandidate from jobSequencingMatrix
73      int solutionCandidateJobNr = jsm[conflictedResourceNr][progressOnConflictedResource];
74
75      //scan conflictSet for given solutionCandidate, and return if found
76      foreach (Task t in conflictSet) {
[6412]77        if (t.JobNr == solutionCandidateJobNr)
[6293]78          return t;
79      }
80
81      //if solutionCandidate wasn't found in conflictSet apply DecodingErrorPolicy and ForcingPolicy
[13443]82      Task result = ApplyDecodingErrorPolicy(decodingErrorPolicy, conflictSet, jsm[conflictedResourceNr], progressOnConflictedResource, random);
[6293]83      int newResolutionIndex = 0;
84
[6412]85      while (newResolutionIndex < jsm[conflictedResourceNr].Length && jsm[conflictedResourceNr][newResolutionIndex] != result.JobNr)
[6293]86        newResolutionIndex++;
[13443]87      ApplyForcingStrategy(forcingStrategy, solution, conflictedResourceNr, newResolutionIndex, progressOnConflictedResource, result.JobNr);
[6293]88
89      return result;
90    }
[8887]91
[13449]92    private static Task ApplyDecodingErrorPolicy(JSMDecodingErrorPolicy decodingErrorPolicy, ItemList<Task> conflictSet, Permutation resource, int progress, IRandom random) {
93      if (decodingErrorPolicy == JSMDecodingErrorPolicy.RandomPolicy) {
[6293]94        //Random
[13443]95        return conflictSet[random.Next(conflictSet.Count - 1)];
[6293]96      } else {
97        //Guided
98        for (int i = progress; i < resource.Length; i++) {
99          int j = 0;
[6412]100          while (j < conflictSet.Count && conflictSet[j].JobNr != resource[i])
[6293]101            j++;
102
103          if (j < conflictSet.Count)
104            return (conflictSet[j]);
105        }
[13443]106        return conflictSet[random.Next(conflictSet.Count - 1)];
[6406]107      }
[6293]108    }
[8887]109
[13449]110    private static void ApplyForcingStrategy(JSMForcingStrategy forcingStrategy, JSMEncoding solution, int conflictedResource, int newResolutionIndex, int progressOnResource, int newResolution) {
[13443]111      var jsm = solution.JobSequenceMatrix;
[13449]112      if (forcingStrategy == JSMForcingStrategy.SwapForcing) {
[6293]113        //SwapForcing
114        jsm[conflictedResource][newResolutionIndex] = jsm[conflictedResource][progressOnResource];
115        jsm[conflictedResource][progressOnResource] = newResolution;
[13449]116      } else if (forcingStrategy == JSMForcingStrategy.ShiftForcing) {
[6293]117        //ShiftForcing
118        List<int> asList = jsm[conflictedResource].ToList<int>();
119        if (newResolutionIndex > progressOnResource) {
120          asList.RemoveAt(newResolutionIndex);
121          asList.Insert(progressOnResource, newResolution);
122        } else {
[6406]123          asList.Insert(progressOnResource, newResolution);
[6293]124          asList.RemoveAt(newResolutionIndex);
125        }
[6406]126        jsm[conflictedResource] = new Permutation(PermutationTypes.Absolute, asList.ToArray<int>());
[13443]127      } else {
128        throw new InvalidOperationException(string.Format("JSMDecoder encountered unknown forcing strategy {0}", forcingStrategy));
[6406]129      }
[6293]130    }
131
[13469]132    public override Schedule DecodeSchedule(JSMEncoding encoding, ItemList<Job> jobData) {
133      return Decode(encoding, jobData, DecodingErrorPolicy, ForcingStrategy);
[13443]134    }
[6293]135
[13469]136    public static Schedule Decode(JSMEncoding solution, ItemList<Job> jobData, JSMDecodingErrorPolicy decodingErrorPolicy, JSMForcingStrategy forcingStrategy) {
[13443]137      var random = new FastRandom(solution.RandomSeed);
[8887]138      var jobs = (ItemList<Job>)jobData.Clone();
139      var resultingSchedule = new Schedule(jobs[0].Tasks.Count);
[6293]140
141      //Reset scheduled tasks in result
142      foreach (Job j in jobs) {
143        foreach (Task t in j.Tasks) {
[6412]144          t.IsScheduled = false;
[6293]145        }
146      }
147
148      //GT-Algorithm
149      //STEP 0 - Compute a list of "earliest operations"
150      ItemList<Task> earliestTasksList = GTAlgorithmUtils.GetEarliestNotScheduledTasks(jobs);
151      while (earliestTasksList.Count > 0) {
152        //STEP 1 - Get earliest not scheduled operation with minimal earliest completing time
153        Task minimal = GTAlgorithmUtils.GetTaskWithMinimalEC(earliestTasksList, resultingSchedule);
[6412]154        int conflictedResourceNr = minimal.ResourceNr;
[6293]155        Resource conflictedResource = resultingSchedule.Resources[conflictedResourceNr];
156
157        //STEP 2 - Compute a conflict set of all operations that can be scheduled on the conflicted resource
[13437]158        ItemList<Task> conflictSet = GTAlgorithmUtils.GetConflictSetForTask(minimal, earliestTasksList, resultingSchedule);
[6293]159
160        //STEP 3 - Select a task from the conflict set
161        int progressOnResource = conflictedResource.Tasks.Count;
[13443]162        Task selectedTask = SelectTaskFromConflictSet(solution, decodingErrorPolicy, forcingStrategy, conflictedResourceNr, progressOnResource, conflictSet, random);
[6293]163
164        //STEP 4 - Add the selected task to the current schedule
[6412]165        selectedTask.IsScheduled = true;
[6293]166        double startTime = GTAlgorithmUtils.ComputeEarliestStartTime(selectedTask, resultingSchedule);
[6412]167        resultingSchedule.ScheduleTask(selectedTask.ResourceNr, startTime, selectedTask.Duration, selectedTask.JobNr);
[6293]168
169        //STEP 5 - Back to STEP 1
170        earliestTasksList = GTAlgorithmUtils.GetEarliestNotScheduledTasks(jobs);
171      }
172
173      return resultingSchedule;
174    }
175  }
176}
Note: See TracBrowser for help on using the repository browser.