Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2212 merged r12008, r12009, r12010 back into trunk

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