- Timestamp:
- 11/08/17 07:34:46 (7 years ago)
- Location:
- branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3
- Files:
-
- 3 added
- 2 edited
- 1 copied
Legend:
- Unmodified
- Added
- Removed
-
branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/CFSAP.cs
r15456 r15460 27 27 using HeuristicLab.Core; 28 28 using HeuristicLab.Data; 29 using HeuristicLab.Encodings.BinaryVectorEncoding; 29 30 using HeuristicLab.Encodings.PermutationEncoding; 30 31 using HeuristicLab.Optimization; … … 34 35 35 36 namespace HeuristicLab.Problems.Scheduling.CFSAP { 36 [Item("Cyclic flow shop with two machines and a single nest (CFSAP) sequencing problem", "Non-permutational cyclic flow shop scheduling problem with a single nest of two machine from W. Bozejko.")]37 [Item("Cyclic flow shop with two machines and a single nest (CFSAP)", "Non-permutational cyclic flow shop scheduling problem with a single nest of two machine from W. Bozejko.")] 37 38 [Creatable(CreatableAttribute.Categories.CombinatorialProblems)] 38 39 [StorableClass] 39 public class CFSAP SequenceOnly : SingleObjectiveBasicProblem<PermutationEncoding>, IProblemInstanceConsumer<CFSAPData> {40 public class CFSAP : SingleObjectiveBasicProblem<MultiEncoding>, ICFSAP, IProblemInstanceConsumer<CFSAPData> { 40 41 public override bool Maximization { get { return false; } } 41 42 … … 44 45 } 45 46 47 public IntMatrix ProcessingTimes { 48 get { return ProcessingTimesParameter.Value; } 49 set { ProcessingTimesParameter.Value = value; } 50 } 51 46 52 public IValueParameter<ItemList<IntMatrix>> SetupTimesParameter { 47 53 get { return (IValueParameter<ItemList<IntMatrix>>)Parameters["SetupTimes"]; } 48 54 } 49 55 56 public ItemList<IntMatrix> SetupTimes { 57 get { return SetupTimesParameter.Value; } 58 set { SetupTimesParameter.Value = value; } 59 } 60 50 61 [StorableConstructor] 51 protected CFSAP SequenceOnly(bool deserializing) : base(deserializing) {}52 protected CFSAP SequenceOnly(CFSAPSequenceOnlyoriginal, Cloner cloner)62 protected CFSAP(bool deserializing) : base(deserializing) {} 63 protected CFSAP(CFSAP original, Cloner cloner) 53 64 : base(original, cloner) {} 54 public CFSAP SequenceOnly() {55 Parameters.Add(new ValueParameter<IntMatrix>("ProcessingTimes", "The processing times of each job for each machine nest."));56 Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("SetupTimes", "The sequence dependent set up times among all jobs for each machine nest."));65 public CFSAP() { 66 Parameters.Add(new ValueParameter<IntMatrix>("ProcessingTimes", "The processing times of each machine and each job.")); 67 Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("SetupTimes", "The sequence dependent set up times of each machine and between all jobs.")); 57 68 58 69 ProcessingTimesParameter.Value = new IntMatrix(new int[,] { … … 77 88 })); 78 89 79 Encoding.Length = 5; 90 Encoding.Add(new PermutationEncoding("sequence", 5, PermutationTypes.RelativeDirected)); 91 Encoding.Add(new BinaryVectorEncoding("assignment", 5)); 80 92 81 93 Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator); … … 85 97 86 98 public override IDeepCloneable Clone(Cloner cloner) { 87 return new CFSAP SequenceOnly(this, cloner);99 return new CFSAP(this, cloner); 88 100 } 89 101 90 102 public override double Evaluate(Individual individual, IRandom random) { 91 var order = individual.Permutation(Encoding.Name); 92 int T = EvaluateSequence(order); 93 return T; 94 } 95 96 public int EvaluateSequence(Permutation order) { 97 var N = order.Length; 98 var processingTimes = ProcessingTimesParameter.Value; 99 var setupTimes = SetupTimesParameter.Value; 100 101 int[,,] weights = new int[2, 2 * N, 2 * N]; 102 int[,] graph = new int[2, N]; 103 int[,] prevPath = new int[2, N + 1]; //Only for optimal assignment evaluation 104 int[] optimalAssignment = new int[N]; //Only for optimal assignment evaluation 105 106 //Calculate weights in the graph 107 for (int S = 0; S < N; S++) { //Starting point of the arc 108 for (int sM = 0; sM < 2; sM++) { //Starting point machine 109 int eM = sM == 0 ? 1 : 0; 110 weights[sM, S, S + 1] = 0; 111 112 for (int E = S + 2; E < S + N; E++) 113 weights[sM, S, E] = 114 weights[sM, S, E - 1] + 115 processingTimes[eM, order[(E - 1) % N]] + 116 setupTimes[eM][order[(E - 1) % N], order[E % N]]; 117 118 for (int E = S + 1; E < S + N; E++) 119 weights[sM, S, E] += ( 120 processingTimes[sM, order[S % N]] + 121 setupTimes[sM][order[S % N], order[(E + 1) % N]] 122 ); 123 } 124 } 125 126 //Determine the shortest path in the graph 127 int T = int.MaxValue / 2; 128 for (int S = 0; S < N - 1; S++) //Start node in graph O(N) 129 for (int SM = 0; SM < 2; SM++) { //Start node machine in graph O(1) 130 graph[SM, S] = 0; 131 graph[SM == 0 ? 1 : 0, S] = int.MaxValue / 2; 132 prevPath[SM, 0] = -1; 133 for (int E = S + 1; E < N; E++) //Currently calculated node O(N) 134 for (int EM = 0; EM < 2; EM++) { //Currently calculated node machine O(1) 135 graph[EM, E] = int.MaxValue / 2; 136 for (int EC = S; EC < E; EC++) { //Nodes connected to node E O(N) 137 int newWeight = graph[EM == 0 ? 1 : 0, EC] + weights[EM == 0 ? 1 : 0, EC, E]; 138 if (newWeight < graph[EM, E]) { 139 graph[EM, E] = newWeight; 140 prevPath[EM, E] = EC; 141 } 142 } 143 } 144 145 int EP = S + N; //End point. 146 int newT = int.MaxValue / 2; 147 for (int EC = S + 1; EC < N; EC++) { //Nodes connected to EP O(N) 148 int newWeight = graph[SM == 0 ? 1 : 0, EC] + weights[SM == 0 ? 1 : 0, EC, EP]; 149 if (newWeight < newT) { 150 newT = newWeight; 151 prevPath[SM, S] = EC; 152 } 153 } 154 155 if (newT < T) { 156 T = newT; 157 optimalAssignment = MakeAssignement(S, SM, prevPath, order); 158 } 159 } 160 161 //Omitted solutions 162 for (int machine = 0; machine < 2; machine++) { 163 int[] assignment = Enumerable.Repeat(machine, N).ToArray(); 164 int newT = EvaluateAssignement(order, assignment, processingTimes, setupTimes); 165 if (newT < T) { //New best solution has been found 166 T = newT; 167 assignment.CopyTo(optimalAssignment, N); 168 } 169 } 170 103 var order = individual.Permutation("sequence"); 104 var assignment = individual.BinaryVector("assignment"); 105 int T = EvaluateAssignement(order, assignment.Select(x => x ? 1 : 0).ToArray(), 106 ProcessingTimesParameter.Value, SetupTimesParameter.Value); 171 107 return T; 172 108 } … … 203 139 } 204 140 205 private int[] MakeAssignement(int start, int startMach, int[,] prevPath, Permutation order) { 206 var N = order.Length; 207 int[] assignment = Enumerable.Repeat(-1, N).ToArray(); 208 var inverseOrder = new int[N]; 209 210 for (int i = 0; i < N; i++) 211 inverseOrder[order[i]] = i; 212 213 int end = start + N; 214 215 int currMach = startMach; 216 int currNode = start; 217 while (true) { 218 assignment[inverseOrder[currNode]] = currMach; 219 currNode = prevPath[currMach, currNode]; 220 currMach = currMach == 0 ? 1 : 0; 221 if (currNode == start) 222 break; 223 } 224 225 currMach = startMach; 226 for (int i = 0; i < N; i++) { 227 if (assignment[inverseOrder[i]] != -1) 228 currMach = currMach == 0 ? 1 : 0; 229 else 230 assignment[inverseOrder[i]] = currMach; 231 } 232 233 return assignment; 141 public void UpdateEncoding() { 142 Encoding.Encodings.OfType<PermutationEncoding>().Single().Length = ProcessingTimes.Columns; 143 Encoding.Encodings.OfType<BinaryVectorEncoding>().Single().Length = ProcessingTimes.Columns; 234 144 } 235 145 … … 265 175 } 266 176 SetupTimesParameter.Value = setups; 267 Encoding.Length = data.Jobs;177 UpdateEncoding(); 268 178 Name = data.Name + "-nest" + nest; 269 179 Description = data.Description; 180 if (data.BestKnownCycleTime.HasValue) 181 BestKnownQuality = data.BestKnownCycleTime.Value; 182 else BestKnownQualityParameter.Value = null; 270 183 } 271 184 } -
branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/CFSAPSequenceOnly.cs
r15456 r15460 44 44 } 45 45 46 public IntMatrix ProcessingTimes { 47 get { return ProcessingTimesParameter.Value; } 48 set { ProcessingTimesParameter.Value = value; } 49 } 50 46 51 public IValueParameter<ItemList<IntMatrix>> SetupTimesParameter { 47 52 get { return (IValueParameter<ItemList<IntMatrix>>)Parameters["SetupTimes"]; } 53 } 54 55 public ItemList<IntMatrix> SetupTimes { 56 get { return SetupTimesParameter.Value; } 57 set { SetupTimesParameter.Value = value; } 48 58 } 49 59 … … 162 172 for (int machine = 0; machine < 2; machine++) { 163 173 int[] assignment = Enumerable.Repeat(machine, N).ToArray(); 164 int newT = EvaluateAssignement(order, assignment, processingTimes, setupTimes);174 int newT = CFSAP.EvaluateAssignement(order, assignment, processingTimes, setupTimes); 165 175 if (newT < T) { //New best solution has been found 166 176 T = newT; 167 assignment.CopyTo(optimalAssignment, N);177 optimalAssignment = assignment; 168 178 } 169 }170 171 return T;172 }173 174 //Function to evaluate individual with the specified assignment175 public static int EvaluateAssignement(Permutation order, int[] assignment, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes) {176 var N = order.Length;177 int T = 0;178 179 for (int i = 0; i < N; i++) {180 int operation = order[i];181 int machine = assignment[operation];182 T += processingTimes[machine, operation];183 }184 185 for (int machine = 0; machine < 2; machine++) {186 int first = -1;187 int last = -1;188 for (int i = 0; i < N; i++) {189 int operation = order[i];190 if (assignment[operation] == machine) {191 if (first == -1)192 first = operation;193 else194 T += setupTimes[machine][last, operation];195 last = operation;196 }197 }198 if (last != -1 && first != -1)199 T += setupTimes[machine][last, first];200 179 } 201 180 … … 232 211 233 212 return assignment; 213 } 214 215 public void UpdateEncoding() { 216 Encoding.Length = ProcessingTimes.Columns; 234 217 } 235 218 … … 265 248 } 266 249 SetupTimesParameter.Value = setups; 267 Encoding.Length = data.Jobs;250 UpdateEncoding(); 268 251 Name = data.Name + "-nest" + nest; 269 252 Description = data.Description; 253 if (data.BestKnownCycleTime.HasValue) 254 BestKnownQuality = data.BestKnownCycleTime.Value; 255 else BestKnownQualityParameter.Value = null; 270 256 } 271 257 } -
branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/HeuristicLab.Problems.Scheduling.CFSAP-3.3.csproj
r14757 r15460 114 114 <ItemGroup> 115 115 <None Include="Plugin.cs.frame" /> 116 <Compile Include="CFSAP.cs" /> 116 117 <Compile Include="CFSAPSequenceOnly.cs" /> 118 <Compile Include="ICFSAP.cs" /> 119 <Compile Include="MultiNestCFSAP.cs" /> 120 <Compile Include="MultiNestCFSAPSolvingStrategy.cs" /> 117 121 <Compile Include="Plugin.cs" /> 118 122 <None Include="Properties\AssemblyInfo.cs.frame" />
Note: See TracChangeset
for help on using the changeset viewer.