Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.Scheduling/3.3/Decoders/PRVDecoder.cs @ 14185

Last change on this file since 14185 was 14185, checked in by swagner, 8 years ago

#2526: Updated year of copyrights in license headers

File size: 9.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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 HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Encodings.ScheduleEncoding;
26using HeuristicLab.Encodings.ScheduleEncoding.PriorityRulesVector;
27using HeuristicLab.Optimization;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30
31namespace HeuristicLab.Problems.Scheduling {
32  [Item("JobSequencingMatrixDecoder", "Applies the GifflerThompson algorithm to create an active schedule from a JobSequencing Matrix.")]
33  [StorableClass]
34  public class PRVDecoder : ScheduleDecoder, IStochasticOperator, IJSSPOperator {
35
36    public ILookupParameter<IRandom> RandomParameter {
37      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
38    }
39    public ILookupParameter<ItemList<Job>> JobDataParameter {
40      get { return (LookupParameter<ItemList<Job>>)Parameters["JobData"]; }
41    }
42
43    #region Priority Rules
44    //smallest number of remaining tasks
45    private Task FILORule(ItemList<Task> tasks) {
46      Task currentResult = tasks[tasks.Count - 1];
47      return currentResult;
48    }
49
50    //earliest start time
51    private Task ESTRule(ItemList<Task> tasks, Schedule schedule) {
52      Task currentResult = RandomRule(tasks);
53      double currentEST = double.MaxValue;
54      foreach (Task t in tasks) {
55        double est = GTAlgorithmUtils.ComputeEarliestStartTime(t, schedule);
56        if (est < currentEST) {
57          currentEST = est;
58          currentResult = t;
59        }
60      }
61      return currentResult;
62    }
63
64    //shortest processingtime
65    private Task SPTRule(ItemList<Task> tasks) {
66      Task currentResult = RandomRule(tasks);
67      foreach (Task t in tasks) {
68        if (t.Duration < currentResult.Duration)
69          currentResult = t;
70      }
71      return currentResult;
72    }
73
74    //longest processing time   
75    private Task LPTRule(ItemList<Task> tasks) {
76      Task currentResult = RandomRule(tasks);
77      foreach (Task t in tasks) {
78        if (t.Duration > currentResult.Duration)
79          currentResult = t;
80      }
81      return currentResult;
82    }
83
84    //most work remaining
85    private Task MWRRule(ItemList<Task> tasks, ItemList<Job> jobs) {
86      Task currentResult = RandomRule(tasks);
87      double currentLargestRemainingProcessingTime = 0;
88      foreach (Task t in tasks) {
89        double remainingProcessingTime = 0;
90        foreach (Task jt in jobs[t.JobNr].Tasks) {
91          if (!jt.IsScheduled)
92            remainingProcessingTime += jt.Duration;
93        }
94        if (remainingProcessingTime > currentLargestRemainingProcessingTime) {
95          currentLargestRemainingProcessingTime = remainingProcessingTime;
96          currentResult = t;
97        }
98      }
99      return currentResult;
100    }
101
102    //least work remaining
103    private Task LWRRule(ItemList<Task> tasks, ItemList<Job> jobs) {
104      Task currentResult = RandomRule(tasks);
105      double currentSmallestRemainingProcessingTime = double.MaxValue;
106      foreach (Task t in tasks) {
107        double remainingProcessingTime = 0;
108        foreach (Task jt in jobs[t.JobNr].Tasks) {
109          if (!jt.IsScheduled)
110            remainingProcessingTime += jt.Duration;
111        }
112        if (remainingProcessingTime < currentSmallestRemainingProcessingTime) {
113          currentSmallestRemainingProcessingTime = remainingProcessingTime;
114          currentResult = t;
115        }
116      }
117      return currentResult;
118    }
119
120    //most operations remaining
121    private Task MORRule(ItemList<Task> tasks, ItemList<Job> jobs) {
122      Task currentResult = RandomRule(tasks);
123      int currentLargestNrOfRemainingTasks = 0;
124      foreach (Task t in tasks) {
125        int nrOfRemainingTasks = 0;
126        foreach (Task jt in jobs[t.JobNr].Tasks) {
127          if (!jt.IsScheduled)
128            nrOfRemainingTasks++;
129        }
130        if (currentLargestNrOfRemainingTasks < nrOfRemainingTasks) {
131          currentLargestNrOfRemainingTasks = nrOfRemainingTasks;
132          currentResult = t;
133        }
134      }
135      return currentResult;
136    }
137
138    //least operationsremaining
139    private Task LORRule(ItemList<Task> tasks, ItemList<Job> jobs) {
140      Task currentResult = RandomRule(tasks);
141      int currentSmallestNrOfRemainingTasks = int.MaxValue;
142      foreach (Task t in tasks) {
143        int nrOfRemainingTasks = 0;
144        foreach (Task jt in jobs[t.JobNr].Tasks) {
145          if (!jt.IsScheduled)
146            nrOfRemainingTasks++;
147        }
148        if (currentSmallestNrOfRemainingTasks > nrOfRemainingTasks) {
149          currentSmallestNrOfRemainingTasks = nrOfRemainingTasks;
150          currentResult = t;
151        }
152      }
153      return currentResult;
154    }
155
156    //first operation in Queue
157    private Task FIFORule(ItemList<Task> tasks) {
158      Task currentResult = tasks[0];
159      return currentResult;
160    }
161
162    //random
163    private Task RandomRule(ItemList<Task> tasks) {
164      Task currentResult = tasks[RandomParameter.ActualValue.Next(tasks.Count)];
165      return currentResult;
166    }
167
168    #endregion
169
170    [StorableConstructor]
171    protected PRVDecoder(bool deserializing) : base(deserializing) { }
172    protected PRVDecoder(PRVDecoder original, Cloner cloner) : base(original, cloner) { }
173    public PRVDecoder()
174      : base() {
175      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
176      Parameters.Add(new LookupParameter<ItemList<Job>>("JobData", "Job data taken from the SchedulingProblem - Instance."));
177      ScheduleEncodingParameter.ActualName = "PriorityRulesVector";
178    }
179
180    public override IDeepCloneable Clone(Cloner cloner) {
181      return new PRVDecoder(this, cloner);
182    }
183
184    private Task SelectTaskFromConflictSet(ItemList<Task> conflictSet, int ruleIndex, int nrOfRules, Schedule schedule, ItemList<Job> jobs) {
185      if (conflictSet.Count == 1)
186        return conflictSet[0];
187
188      ruleIndex = ruleIndex % nrOfRules;
189      switch (ruleIndex) {
190        case 0: return FILORule(conflictSet);
191        case 1: return ESTRule(conflictSet, schedule);
192        case 2: return SPTRule(conflictSet);
193        case 3: return LPTRule(conflictSet);
194        case 4: return MWRRule(conflictSet, jobs);
195        case 5: return LWRRule(conflictSet, jobs);
196        case 6: return MORRule(conflictSet, jobs);
197        case 7: return LORRule(conflictSet, jobs);
198        case 8: return FIFORule(conflictSet);
199        case 9: return RandomRule(conflictSet);
200        default: return RandomRule(conflictSet);
201      }
202    }
203
204    public override Schedule CreateScheduleFromEncoding(IScheduleEncoding encoding) {
205      var solution = encoding as PRVEncoding;
206      if (solution == null) throw new InvalidOperationException("Encoding is not of type PWREncoding");
207
208      var jobs = (ItemList<Job>)JobDataParameter.ActualValue.Clone();
209      var resultingSchedule = new Schedule(jobs[0].Tasks.Count);
210
211      //Reset scheduled tasks in result
212      foreach (Job j in jobs) {
213        foreach (Task t in j.Tasks) {
214          t.IsScheduled = false;
215        }
216      }
217
218      //GT-Algorithm
219      //STEP 0 - Compute a list of "earliest operations"
220      ItemList<Task> earliestTasksList = GTAlgorithmUtils.GetEarliestNotScheduledTasks(jobs);
221      //int currentDecisionIndex = 0;
222      while (earliestTasksList.Count > 0) {
223        //STEP 1 - Get earliest not scheduled operation with minimal earliest completing time
224        Task minimal = GTAlgorithmUtils.GetTaskWithMinimalEC(earliestTasksList, resultingSchedule);
225
226        //STEP 2 - Compute a conflict set of all operations that can be scheduled on the machine the previously selected operation runs on
227        ItemList<Task> conflictSet = GTAlgorithmUtils.GetConflictSetForTask(minimal, earliestTasksList, jobs, resultingSchedule);
228
229        //STEP 3 - Select an operation from the conflict set (various methods depending on how the algorithm should work..)
230        //Task selectedTask = SelectTaskFromConflictSet(conflictSet, solution.PriorityRulesVector [currentDecisionIndex++], solution.NrOfRules.Value);
231        Task selectedTask = SelectTaskFromConflictSet(conflictSet, solution.PriorityRulesVector[minimal.JobNr], solution.NrOfRules.Value, resultingSchedule, jobs);
232
233        //STEP 4 - Adding the selected operation to the current schedule
234        selectedTask.IsScheduled = true;
235        double startTime = GTAlgorithmUtils.ComputeEarliestStartTime(selectedTask, resultingSchedule);
236        resultingSchedule.ScheduleTask(selectedTask.ResourceNr, startTime, selectedTask.Duration, selectedTask.JobNr);
237
238        //STEP 5 - Back to STEP 1
239        earliestTasksList = GTAlgorithmUtils.GetEarliestNotScheduledTasks(jobs);
240      }
241
242      return resultingSchedule;
243    }
244  }
245}
Note: See TracBrowser for help on using the repository browser.