source: branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/OptimalPolynomialAssignment.cs @ 15533

Last change on this file since 15533 was 15533, checked in by ddorfmei, 5 years ago

#2747: Improved hard-coded genetic algorithm

  • implemented restart strategy
  • implemented 1-Opt algorithm
  • added parameters to control restart strategy and optimal assignment strategy
  • additional results: best solution found after number of generations, jobs/nests (for evaluation only)
File size: 5.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2017 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.Linq;
23using HeuristicLab.Core;
24using HeuristicLab.Data;
25using HeuristicLab.Encodings.PermutationEncoding;
26
27namespace HeuristicLab.Problems.Scheduling.CFSAP {
28  public static class OptimalPolynomialAssignment {
29
30    public static int[] MakeAssignment(Permutation order, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes, out int T) {
31      var N = order.Length;
32
33      int[,,] weights = new int[2, 2 * N, 2 * N];
34      int[,] graph = new int[2, N];
35      int[,] prevPath = new int[2, N + 1];    //Only for optimal assignment evaluation
36      int[] optimalAssignment = new int[N];   //Only for optimal assignment evaluation
37
38      //Calculate weights in the graph
39      for (int S = 0; S < N; S++) {        //Starting point of the arc
40        for (int sM = 0; sM < 2; sM++) {   //Starting point machine
41          int eM = sM == 0 ? 1 : 0;
42          weights[sM, S, S + 1] = 0;
43
44          for (int E = S + 2; E < S + N; E++)
45            weights[sM, S, E] =
46              weights[sM, S, E - 1] +
47              processingTimes[eM, order[(E - 1) % N]] +
48              setupTimes[eM][order[(E - 1) % N], order[E % N]];
49
50          for (int E = S + 1; E < S + N; E++)
51            weights[sM, S, E] += (
52              processingTimes[sM, order[S % N]] +
53              setupTimes[sM][order[S % N], order[(E + 1) % N]]
54            );
55        }
56      }
57
58      //Determine the shortest path in the graph
59      T = int.MaxValue / 2;
60      for (int S = 0; S < N - 1; S++)      //Start node in graph          O(N)
61        for (int SM = 0; SM < 2; SM++) {   //Start node machine in graph  O(1)
62          graph[SM, S] = 0;
63          graph[SM == 0 ? 1 : 0, S] = int.MaxValue / 2;
64          prevPath[SM, 0] = -1;
65          for (int E = S + 1; E < N; E++)      //Currently calculated node          O(N)
66            for (int EM = 0; EM < 2; EM++) {   //Currently calculated node machine  O(1)
67              graph[EM, E] = int.MaxValue / 2;
68              for (int EC = S; EC < E; EC++) { //Nodes connected to node E          O(N)
69                int newWeight = graph[EM == 0 ? 1 : 0, EC] + weights[EM == 0 ? 1 : 0, EC, E];
70                if (newWeight < graph[EM, E]) {
71                  graph[EM, E] = newWeight;
72                  prevPath[EM, E] = EC;
73                }
74              }
75            }
76
77          int EP = S + N; //End point.
78          int newT = int.MaxValue / 2;
79          for (int EC = S + 1; EC < N; EC++) { //Nodes connected to EP O(N)
80            int newWeight = graph[SM == 0 ? 1 : 0, EC] + weights[SM == 0 ? 1 : 0, EC, EP];
81            if (newWeight < newT) {
82              newT = newWeight;
83              prevPath[SM, S] = EC;
84            }
85          }
86
87          if (newT < T) {
88            T = newT;
89            optimalAssignment = MakeAssignment(S, SM, prevPath, order);
90          }
91        }
92
93      //Omitted solutions
94      for (int machine = 0; machine < 2; machine++) {
95        int[] assignment = Enumerable.Repeat(machine, N).ToArray();
96        int newT = CFSAP.EvaluateAssignement(order, assignment, processingTimes, setupTimes);
97        if (newT < T) { //New best solution has been found
98          T = newT;
99          optimalAssignment = assignment;
100        }
101      }
102
103      return optimalAssignment;
104    }
105
106    private static int[] MakeAssignment(int start, int startMach, int[,] prevPath, Permutation order) {
107      var N = order.Length;
108      int[] assignment = Enumerable.Repeat(-1, N).ToArray();
109      var inverseOrder = new int[N];
110
111      for (int i = 0; i < N; i++)
112        inverseOrder[order[i]] = i;
113
114      int end = start + N;
115
116      int currMach = startMach;
117      int currNode = start;
118      while (true) {
119        assignment[inverseOrder[currNode]] = currMach;
120        currNode = prevPath[currMach, currNode];
121        currMach = currMach == 0 ? 1 : 0;
122        if (currNode == start)
123          break;
124      }
125
126      currMach = startMach;
127      for (int i = 0; i < N; i++) {
128        if (assignment[inverseOrder[i]] != -1)
129          currMach = currMach == 0 ? 1 : 0;
130        else
131          assignment[inverseOrder[i]] = currMach;
132      }
133
134      return assignment;
135    }
136  }
137}
Note: See TracBrowser for help on using the repository browser.