source: trunk/sources/HeuristicLab.Problems.Scheduling/3.3/Decoders/JSMDecoder.cs @ 12012

Last change on this file since 12012 was 12012, checked in by ascheibe, 6 years ago

#2212 merged r12008, r12009, r12010 back into trunk

File size: 8.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
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
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Encodings.PermutationEncoding;
28using HeuristicLab.Encodings.ScheduleEncoding;
29using HeuristicLab.Encodings.ScheduleEncoding.JobSequenceMatrix;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33
34namespace HeuristicLab.Problems.Scheduling {
35  [Item("JobSequenceMatrixDecoder", "Applies the GifflerThompson algorithm to create an active schedule from a JobSequence Matrix.")]
36  [StorableClass]
37  public class JSMDecoder : ScheduleDecoder, IStochasticOperator, IJSSPOperator {
38
39    public ILookupParameter<IRandom> RandomParameter {
40      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
41    }
42    public ILookupParameter<ItemList<Job>> JobDataParameter {
43      get { return (LookupParameter<ItemList<Job>>)Parameters["JobData"]; }
44    }
45    public IValueParameter<JSMDecodingErrorPolicy> DecodingErrorPolicyParameter {
46      get { return (IValueParameter<JSMDecodingErrorPolicy>)Parameters["DecodingErrorPolicy"]; }
47    }
48    public IValueParameter<JSMForcingStrategy> ForcingStrategyParameter {
49      get { return (IValueParameter<JSMForcingStrategy>)Parameters["ForcingStrategy"]; }
50    }
51
52    private JSMDecodingErrorPolicyTypes DecodingErrorPolicy {
53      get { return DecodingErrorPolicyParameter.Value.Value; }
54    }
55
56    private JSMForcingStrategyTypes ForcingStrategy {
57      get { return ForcingStrategyParameter.Value.Value; }
58    }
59
60    [StorableConstructor]
61    protected JSMDecoder(bool deserializing) : base(deserializing) { }
62    protected JSMDecoder(JSMDecoder original, Cloner cloner) : base(original, cloner) { }
63    public override IDeepCloneable Clone(Cloner cloner) {
64      return new JSMDecoder(this, cloner);
65    }
66
67    public JSMDecoder()
68      : base() {
69      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
70      Parameters.Add(new LookupParameter<ItemList<Job>>("JobData", "Job data taken from the Schedulingproblem - Instance."));
71      Parameters.Add(new ValueParameter<JSMDecodingErrorPolicy>("DecodingErrorPolicy", "Specify the policy that should be used to handle decoding errors.", new JSMDecodingErrorPolicy(JSMDecodingErrorPolicyTypes.RandomPolicy)));
72      Parameters.Add(new ValueParameter<JSMForcingStrategy>("ForcingStrategy", "Specifies a forcing strategy.", new JSMForcingStrategy(JSMForcingStrategyTypes.SwapForcing)));
73
74      ScheduleEncodingParameter.ActualName = "JobSequenceMatrix";
75    }
76
77    private Task SelectTaskFromConflictSet(int conflictedResourceNr, int progressOnConflictedResource, ItemList<Task> conflictSet, ItemList<Permutation> jsm) {
78      if (conflictSet.Count == 1)
79        return conflictSet[0];
80
81      //get solutionCandidate from jobSequencingMatrix
82      int solutionCandidateJobNr = jsm[conflictedResourceNr][progressOnConflictedResource];
83
84      //scan conflictSet for given solutionCandidate, and return if found
85      foreach (Task t in conflictSet) {
86        if (t.JobNr == solutionCandidateJobNr)
87          return t;
88      }
89
90      //if solutionCandidate wasn't found in conflictSet apply DecodingErrorPolicy and ForcingPolicy
91      Task result = ApplyDecodingErrorPolicy(conflictSet, jsm[conflictedResourceNr], progressOnConflictedResource);
92      int newResolutionIndex = 0;
93
94      while (newResolutionIndex < jsm[conflictedResourceNr].Length && jsm[conflictedResourceNr][newResolutionIndex] != result.JobNr)
95        newResolutionIndex++;
96      ApplyForcingStrategy(jsm, conflictedResourceNr, newResolutionIndex, progressOnConflictedResource, result.JobNr);
97
98      return result;
99    }
100
101    private Task ApplyDecodingErrorPolicy(ItemList<Task> conflictSet, Permutation resource, int progress) {
102      if (DecodingErrorPolicy == JSMDecodingErrorPolicyTypes.RandomPolicy) {
103        //Random
104        return conflictSet[RandomParameter.ActualValue.Next(conflictSet.Count - 1)];
105      } else {
106        //Guided
107        for (int i = progress; i < resource.Length; i++) {
108          int j = 0;
109          while (j < conflictSet.Count && conflictSet[j].JobNr != resource[i])
110            j++;
111
112          if (j < conflictSet.Count)
113            return (conflictSet[j]);
114        }
115        return conflictSet[RandomParameter.ActualValue.Next(conflictSet.Count - 1)];
116      }
117    }
118
119    private void ApplyForcingStrategy(ItemList<Permutation> jsm, int conflictedResource, int newResolutionIndex, int progressOnResource, int newResolution) {
120      if (ForcingStrategy == JSMForcingStrategyTypes.SwapForcing) {
121        //SwapForcing
122        jsm[conflictedResource][newResolutionIndex] = jsm[conflictedResource][progressOnResource];
123        jsm[conflictedResource][progressOnResource] = newResolution;
124      } else {
125        //ShiftForcing
126        List<int> asList = jsm[conflictedResource].ToList<int>();
127        if (newResolutionIndex > progressOnResource) {
128          asList.RemoveAt(newResolutionIndex);
129          asList.Insert(progressOnResource, newResolution);
130        } else {
131          asList.Insert(progressOnResource, newResolution);
132          asList.RemoveAt(newResolutionIndex);
133        }
134        jsm[conflictedResource] = new Permutation(PermutationTypes.Absolute, asList.ToArray<int>());
135      }
136    }
137
138    public Schedule CreateScheduleFromEncoding(JSMEncoding solution, ItemList<Job> jobData) {
139      ItemList<Permutation> jobSequenceMatrix = solution.JobSequenceMatrix;
140
141      var jobs = (ItemList<Job>)jobData.Clone();
142      var resultingSchedule = new Schedule(jobs[0].Tasks.Count);
143
144      //Reset scheduled tasks in result
145      foreach (Job j in jobs) {
146        foreach (Task t in j.Tasks) {
147          t.IsScheduled = false;
148        }
149      }
150
151      //GT-Algorithm
152      //STEP 0 - Compute a list of "earliest operations"
153      ItemList<Task> earliestTasksList = GTAlgorithmUtils.GetEarliestNotScheduledTasks(jobs);
154      while (earliestTasksList.Count > 0) {
155        //STEP 1 - Get earliest not scheduled operation with minimal earliest completing time
156        Task minimal = GTAlgorithmUtils.GetTaskWithMinimalEC(earliestTasksList, resultingSchedule);
157        int conflictedResourceNr = minimal.ResourceNr;
158        Resource conflictedResource = resultingSchedule.Resources[conflictedResourceNr];
159
160        //STEP 2 - Compute a conflict set of all operations that can be scheduled on the conflicted resource
161        ItemList<Task> conflictSet = GTAlgorithmUtils.GetConflictSetForTask(minimal, earliestTasksList, jobs, resultingSchedule);
162
163        //STEP 3 - Select a task from the conflict set
164        int progressOnResource = conflictedResource.Tasks.Count;
165        Task selectedTask = SelectTaskFromConflictSet(conflictedResourceNr, progressOnResource, conflictSet, jobSequenceMatrix);
166
167        //STEP 4 - Add the selected task to the current schedule
168        selectedTask.IsScheduled = true;
169        double startTime = GTAlgorithmUtils.ComputeEarliestStartTime(selectedTask, resultingSchedule);
170        resultingSchedule.ScheduleTask(selectedTask.ResourceNr, startTime, selectedTask.Duration, selectedTask.JobNr);
171
172        //STEP 5 - Back to STEP 1
173        earliestTasksList = GTAlgorithmUtils.GetEarliestNotScheduledTasks(jobs);
174      }
175
176      return resultingSchedule;
177    }
178
179    public override Schedule CreateScheduleFromEncoding(IScheduleEncoding encoding) {
180      var solution = encoding as JSMEncoding;
181      if (solution == null) throw new InvalidOperationException("Encoding is not of type JSMEncoding");
182      return CreateScheduleFromEncoding(solution, JobDataParameter.ActualValue);
183    }
184  }
185}
Note: See TracBrowser for help on using the repository browser.