Changeset 15460 for branches/CFSAP
- Timestamp:
- 11/08/17 07:34:46 (7 years ago)
- Location:
- branches/CFSAP
- Files:
-
- 3 added
- 6 edited
- 1 copied
Legend:
- Unmodified
- Added
- Removed
-
branches/CFSAP/CFSAP.sln
r14757 r15460 1 1 2 2 Microsoft Visual Studio Solution File, Format Version 12.00 3 # Visual Studio 1 44 VisualStudioVersion = 1 4.0.25420.13 # Visual Studio 15 4 VisualStudioVersion = 15.0.27004.2002 5 5 MinimumVisualStudioVersion = 10.0.40219.1 6 6 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.Scheduling.CFSAP-3.3", "HeuristicLab.Problems.Scheduling.CFSAP\3.3\HeuristicLab.Problems.Scheduling.CFSAP-3.3.csproj", "{93609034-D1EE-4DC6-A381-E4CDB55E4261}" … … 60 60 HideSolutionNode = FALSE 61 61 EndGlobalSection 62 GlobalSection(ExtensibilityGlobals) = postSolution 63 SolutionGuid = {1DA298F0-1917-4ED1-8495-507A39302C34} 64 EndGlobalSection 62 65 EndGlobal -
branches/CFSAP/HeuristicLab.Problems.Instances.CFSAP/3.3/BozejkoCFSAPInstanceProvider.cs
r15456 r15460 89 89 instance.Name = id.Name; 90 90 instance.Description = id.Description; 91 int bkct; 92 if (bestKnownCycleTimes.TryGetValue(id.Name, out bkct)) 93 instance.BestKnownCycleTime = bkct; 91 94 return instance; 92 95 } … … 103 106 } 104 107 108 private static readonly Dictionary<string, int> bestKnownCycleTimes = new Dictionary<string, int>() { 109 { "gi_001", 608 }, 110 { "gi_002", 623 }, 111 { "gi_003", 500 }, 112 { "gi_004", 585 }, 113 { "gi_005", 549 }, 114 { "gi_006", 629 }, 115 { "gi_007", 603 }, 116 { "gi_008", 506 }, 117 { "gi_009", 588 }, 118 { "gi_010", 493 }, 119 { "gi_011", 597 }, 120 { "gi_012", 554 }, 121 { "gi_013", 594 }, 122 { "gi_014", 505 }, 123 { "gi_015", 631 }, 124 { "gi_016", 626 }, 125 { "gi_017", 585 }, 126 { "gi_018", 529 }, 127 { "gi_019", 649 }, 128 { "gi_020", 561 }, 129 { "gi_021", 535 }, 130 { "gi_022", 586 }, 131 { "gi_023", 602 }, 132 { "gi_024", 607 }, 133 { "gi_025", 598 }, 134 { "gi_026", 572 }, 135 { "gi_027", 605 }, 136 { "gi_028", 619 }, 137 { "gi_029", 646 }, 138 { "gi_030", 591 }, 139 { "gi_031", 958 }, 140 { "gi_032", 838 }, 141 { "gi_033", 974 }, 142 { "gi_034", 904 }, 143 { "gi_035", 1002 }, 144 { "gi_036", 998 }, 145 { "gi_037", 988 }, 146 { "gi_038", 872 }, 147 { "gi_039", 1009 }, 148 { "gi_040", 1000 }, 149 { "gi_041", 992 }, 150 { "gi_042", 1097 }, 151 { "gi_043", 989 }, 152 { "gi_044", 1038 }, 153 { "gi_045", 998 }, 154 { "gi_046", 1077 }, 155 { "gi_047", 997 }, 156 { "gi_048", 921 }, 157 { "gi_049", 902 }, 158 { "gi_050", 1035 }, 159 { "gi_051", 914 }, 160 { "gi_052", 1019 }, 161 { "gi_053", 997 }, 162 { "gi_054", 928 }, 163 { "gi_055", 973 }, 164 { "gi_056", 1011 }, 165 { "gi_057", 943 }, 166 { "gi_058", 959 }, 167 { "gi_059", 1079 }, 168 { "gi_060", 940 }, 169 { "gi_061", 2176 }, 170 { "gi_062", 2100 }, 171 { "gi_063", 2147 }, 172 { "gi_064", 2289 }, 173 { "gi_065", 2171 }, 174 { "gi_066", 2185 }, 175 { "gi_067", 2152 }, 176 { "gi_068", 2321 }, 177 { "gi_069", 2173 }, 178 { "gi_070", 2242 }, 179 { "gi_071", 2222 }, 180 { "gi_072", 2403 }, 181 { "gi_073", 2305 }, 182 { "gi_074", 2279 }, 183 { "gi_075", 2283 }, 184 { "gi_076", 2014 }, 185 { "gi_077", 2185 }, 186 { "gi_078", 2236 }, 187 { "gi_079", 2223 }, 188 { "gi_080", 2136 }, 189 { "gi_081", 2147 }, 190 { "gi_082", 2285 }, 191 { "gi_083", 2270 }, 192 { "gi_084", 2264 }, 193 { "gi_085", 2192 }, 194 { "gi_086", 2052 }, 195 { "gi_087", 2130 }, 196 { "gi_088", 2172 }, 197 { "gi_089", 2530 }, 198 { "gi_090", 2498 }, 199 { "gi_091", 4465 }, 200 { "gi_092", 4269 }, 201 { "gi_093", 4201 }, 202 { "gi_094", 4330 }, 203 { "gi_095", 4158 }, 204 { "gi_096", 4355 }, 205 { "gi_097", 4363 }, 206 { "gi_098", 4268 }, 207 { "gi_099", 4143 }, 208 { "gi_100", 4313 }, 209 { "gi_101", 4285 }, 210 { "gi_102", 4421 }, 211 { "gi_103", 4288 }, 212 { "gi_104", 4295 }, 213 { "gi_105", 4295 }, 214 { "gi_106", 4257 }, 215 { "gi_107", 4610 }, 216 { "gi_108", 4579 }, 217 { "gi_109", 4578 }, 218 { "gi_110", 4219 }, 219 { "gi_111", 4472 }, 220 { "gi_112", 4460 }, 221 { "gi_113", 4446 }, 222 { "gi_114", 4504 }, 223 { "gi_115", 4417 }, 224 { "gi_116", 4503 }, 225 { "gi_117", 4442 }, 226 { "gi_118", 4411 }, 227 { "gi_119", 4506 }, 228 { "gi_120", 4556 } 229 }; 105 230 } 106 231 } -
branches/CFSAP/HeuristicLab.Problems.Instances.CFSAP/3.3/BozejkoCFSAPParser.cs
r15456 r15460 64 64 } 65 65 } 66 SetupTimes.Add(sp);67 66 } 67 SetupTimes.Add(sp); 68 68 } 69 69 reader.Close(); -
branches/CFSAP/HeuristicLab.Problems.Instances/3.3/Types/CFSAPData.cs
r15456 r15460 33 33 public string Description { get; set; } 34 34 /// <summary> 35 /// Optional! The best known cycle time. 36 /// </summary> 37 public int? BestKnownCycleTime { get; set; } 38 /// <summary> 35 39 /// The number of jobs. 36 40 /// </summary> -
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.