source: branches/2747_CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/CFSAPSequenceOnly.cs @ 17639

#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;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.Instances;

namespace HeuristicLab.Problems.Scheduling.CFSAP {
  [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.")]
  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
  [StorableClass]
  public class CFSAPSequenceOnly : SingleObjectiveBasicProblem<PermutationEncoding>, IProblemInstanceConsumer<CFSAPData> {
    public override bool Maximization { get { return false; } }

    public IValueParameter<IntMatrix> ProcessingTimesParameter {
      get { return (IValueParameter<IntMatrix>)Parameters["ProcessingTimes"]; }
    }

    public IntMatrix ProcessingTimes {
      get { return ProcessingTimesParameter.Value; }
      set { ProcessingTimesParameter.Value = value; }
    }

    public IValueParameter<ItemList<IntMatrix>> SetupTimesParameter {
      get { return (IValueParameter<ItemList<IntMatrix>>)Parameters["SetupTimes"]; }
    }

    public ItemList<IntMatrix> SetupTimes {
      get { return SetupTimesParameter.Value; }
      set { SetupTimesParameter.Value = value; }
    }

    [StorableConstructor]
    protected CFSAPSequenceOnly(bool deserializing) : base(deserializing) {}
    protected CFSAPSequenceOnly(CFSAPSequenceOnly original, Cloner cloner)
      : base(original, cloner) {}
    public CFSAPSequenceOnly() {
      Parameters.Add(new ValueParameter<IntMatrix>("ProcessingTimes", "The processing times of each job for each machine nest."));
      Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("SetupTimes", "The sequence dependent set up times among all jobs for each machine nest."));

      ProcessingTimesParameter.Value = new IntMatrix(new int[,] {
        { 5, 4, 3, 2, 1 },
        { 1, 2, 3, 4, 5 }
      });

      SetupTimesParameter.Value = new ItemList<IntMatrix>(2);
      SetupTimesParameter.Value.Add(new IntMatrix(new int[,] {
        { 3, 4, 5, 4, 3 },
        { 3, 4, 5, 4, 3 },
        { 3, 4, 5, 4, 3 },
        { 3, 4, 5, 4, 3 },
        { 3, 4, 5, 4, 3 },
      }));
      SetupTimesParameter.Value.Add(new IntMatrix(new int[,] {
        { 5, 4, 3, 4, 5 },
        { 5, 4, 3, 4, 5 },
        { 5, 4, 3, 4, 5 },
        { 5, 4, 3, 4, 5 },
        { 5, 4, 3, 4, 5 },
      }));

      Encoding.Length = 5;

      Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);
      Operators.RemoveAll(x => x is SingleObjectiveMoveEvaluator);
      Operators.RemoveAll(x => x is SingleObjectiveMoveMaker);
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new CFSAPSequenceOnly(this, cloner);
    }

    public override double Evaluate(Individual individual, IRandom random) {
      var order = individual.Permutation(Encoding.Name);
      int T = EvaluateSequence(order);
      return T;
    }

    public int EvaluateSequence(Permutation order) {
      var N = order.Length;
      var processingTimes = ProcessingTimesParameter.Value;
      var setupTimes = SetupTimesParameter.Value;

      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
      int 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 = MakeAssignement(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 T;
    }

    private int[] MakeAssignement(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;
    }

    public void UpdateEncoding() {
      Encoding.Length = ProcessingTimes.Columns;
    }

    /// <summary>
    /// Imports the first nest (index 0) given in the CFSAPData.
    /// This is the same as calling Load(data, 0).
    /// </summary>
    /// <param name="data">The data of all nests.</param>
    public void Load(CFSAPData data) {
      Load(data, 0);
    }

    /// <summary>
    /// Imports a specific nest given in the CFSAPData.
    /// </summary>
    /// <param name="data">The data of all nests.</param>
    /// <param name="nest">The zero-based index of the nest that should be imported.</param>
    public void Load(CFSAPData data, int nest) {
      if (data.Machines[nest] != 2) throw new ArgumentException("Currently only two machines per nest are supported.");
      if (nest < 0 || nest >= data.Nests) throw new ArgumentException("Nest must be a zero-based index.");
      var pr = new int[data.Machines[nest], data.Jobs];
      for (var i = 0; i < data.Machines[nest]; i++)
        for (var j = 0; j < data.Jobs; j++)
          pr[i, j] = data.ProcessingTimes[nest][i][j];
      ProcessingTimesParameter.Value = new IntMatrix(pr);
      var setups = new ItemList<IntMatrix>(data.Machines[nest]);
      for (var m = 0; m < data.SetupTimes[nest].GetLength(0); m++) {
        var setupTimes = new int[data.Jobs, data.Jobs];
        for (var i = 0; i < data.Jobs; i++)
          for (var j = 0; j < data.Jobs; j++)
            setupTimes[i, j] = data.SetupTimes[nest][m][i][j];
        setups.Add(new IntMatrix(setupTimes));
      }
      SetupTimesParameter.Value = setups;
      UpdateEncoding();
      Name = data.Name + "-nest" + nest;
      Description = data.Description;
      if (data.BestKnownCycleTime.HasValue)
        BestKnownQuality = data.BestKnownCycleTime.Value;
      else BestKnownQualityParameter.Value = null;
    }
  }
}