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

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System.Linq;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;

namespace HeuristicLab.Problems.Scheduling.CFSAP {
  public static class OptimalPolynomialAssignment {

    public static int[] MakeAssignment(Permutation order, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes, out int T) {
      var N = order.Length;

      int[,,] weights = new int[2, 2 * N, 2 * N];
      int[,] graph = new int[2, N];
      int[,] prevPath = new int[2, N + 1];    //Only for optimal assignment evaluation
      int[] optimalAssignment = new int[N];   //Only for optimal assignment evaluation

      //Calculate weights in the graph
      for (int S = 0; S < N; S++) {        //Starting point of the arc
        for (int sM = 0; sM < 2; sM++) {   //Starting point machine
          int eM = sM == 0 ? 1 : 0;
          weights[sM, S, S + 1] = 0;

          for (int E = S + 2; E < S + N; E++)
            weights[sM, S, E] =
              weights[sM, S, E - 1] +
              processingTimes[eM, order[(E - 1) % N]] +
              setupTimes[eM][order[(E - 1) % N], order[E % N]];

          for (int E = S + 1; E < S + N; E++)
            weights[sM, S, E] += (
              processingTimes[sM, order[S % N]] +
              setupTimes[sM][order[S % N], order[(E + 1) % N]]
            );
        }
      }

      //Determine the shortest path in the graph
      T = int.MaxValue / 2;
      for (int S = 0; S < N - 1; S++)      //Start node in graph          O(N)
        for (int SM = 0; SM < 2; SM++) {   //Start node machine in graph  O(1)
          graph[SM, S] = 0;
          graph[SM == 0 ? 1 : 0, S] = int.MaxValue / 2;
          prevPath[SM, 0] = -1;
          for (int E = S + 1; E < N; E++)      //Currently calculated node          O(N)
            for (int EM = 0; EM < 2; EM++) {   //Currently calculated node machine  O(1)
              graph[EM, E] = int.MaxValue / 2;
              for (int EC = S; EC < E; EC++) { //Nodes connected to node E          O(N)
                int newWeight = graph[EM == 0 ? 1 : 0, EC] + weights[EM == 0 ? 1 : 0, EC, E];
                if (newWeight < graph[EM, E]) {
                  graph[EM, E] = newWeight;
                  prevPath[EM, E] = EC;
                }
              }
            }

          int EP = S + N; //End point.
          int newT = int.MaxValue / 2;
          for (int EC = S + 1; EC < N; EC++) { //Nodes connected to EP O(N)
            int newWeight = graph[SM == 0 ? 1 : 0, EC] + weights[SM == 0 ? 1 : 0, EC, EP];
            if (newWeight < newT) {
              newT = newWeight;
              prevPath[SM, S] = EC;
            }
          }

          if (newT < T) {
            T = newT;
            optimalAssignment = MakeAssignment(S, SM, prevPath, order);
          }
        }

      //Omitted solutions
      for (int machine = 0; machine < 2; machine++) {
        int[] assignment = Enumerable.Repeat(machine, N).ToArray();
        int newT = CFSAP.EvaluateAssignement(order, assignment, processingTimes, setupTimes);
        if (newT < T) { //New best solution has been found
          T = newT;
          optimalAssignment = assignment;
        }
      }

      return optimalAssignment;
    }

    private static int[] MakeAssignment(int start, int startMach, int[,] prevPath, Permutation order) {
      var N = order.Length;
      int[] assignment = Enumerable.Repeat(-1, N).ToArray();
      var inverseOrder = new int[N];

      for (int i = 0; i < N; i++)
        inverseOrder[order[i]] = i;

      int end = start + N;

      int currMach = startMach;
      int currNode = start;
      while (true) {
        assignment[inverseOrder[currNode]] = currMach;
        currNode = prevPath[currMach, currNode];
        currMach = currMach == 0 ? 1 : 0;
        if (currNode == start)
          break;
      }

      currMach = startMach;
      for (int i = 0; i < N; i++) {
        if (assignment[inverseOrder[i]] != -1)
          currMach = currMach == 0 ? 1 : 0;
        else
          assignment[inverseOrder[i]] = currMach;
      }

      return assignment;
    }
  }
}