source: branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/CFSAPSequenceOnly.cs @ 15330

#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 machine nests (CFSAP) sequence only", "Non-permutational cyclic flow shop scheduling problem with two machine nests 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 IValueParameter<ItemList<IntMatrix>> SetupTimesParameter {
      get { return (IValueParameter<ItemList<IntMatrix>>)Parameters["SetupTimes"]; }
    }

    [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);
      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 = EvaluateAssignement(order, assignment, processingTimes, setupTimes);
        if (newT < T) { //New best solution has been found
          T = newT;
          assignment.CopyTo(optimalAssignment, N);
        }
      }

      return T;
    }

    //Function to evaluate individual with the specified assignment
    public static int EvaluateAssignement(Permutation order, int[] assignment, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes) {
      var N = order.Length;
      int T = 0;

      for (int i = 0; i < N; i++) {
        int operation = order[i];
        int machine = assignment[operation];
        T += processingTimes[machine, operation];
      }

      for (int machine = 0; machine < 2; machine++) {
        int first = -1;
        int last = -1;
        for (int i = 0; i < N; i++) {
          int operation = order[i];
          if (assignment[operation] == machine) {
            if (first == -1)
              first = operation;
            else
              T += setupTimes[machine][last, operation];
            last = operation;
          }
        }
        if (last != -1 && first != -1)
          T += setupTimes[machine][last, first];
      }

      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 Load(CFSAPData data) {
      if (data.MachineNests != 2) throw new ArgumentException("Currently only two machine nests are supported.");
      ProcessingTimesParameter.Value = new IntMatrix(data.ProcessingTimes);
      var setups = new ItemList<IntMatrix>(data.MachineNests);
      for (var m = 0; m < data.SetupTimes.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[m, i, j];
        setups.Add(new IntMatrix(setupTimes));
      }
      SetupTimesParameter.Value = setups;
      Encoding.Length = data.Jobs;
      Name = data.Name;
      Description = data.Description;
    }
  }
}