[6293] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[11185] | 3 | * Copyright (C) 2002-2014 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] | 22 | using System;
|
---|
[6406] | 23 | using HeuristicLab.Common;
|
---|
[6293] | 24 | using HeuristicLab.Core;
|
---|
[6406] | 25 | using HeuristicLab.Encodings.ScheduleEncoding;
|
---|
| 26 | using HeuristicLab.Encodings.ScheduleEncoding.PriorityRulesVector;
|
---|
[6293] | 27 | using HeuristicLab.Optimization;
|
---|
| 28 | using HeuristicLab.Parameters;
|
---|
[6406] | 29 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
[6293] | 30 |
|
---|
[6406] | 31 | namespace 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 | }
|
---|