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

#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.BinaryVectorEncoding;
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)", "Non-permutational cyclic flow shop scheduling problem with a single nest of two machine from W. Bozejko.")]
  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
  [StorableClass]
  public class CFSAP : SingleObjectiveBasicProblem<MultiEncoding>, ICFSAP, 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 CFSAP(bool deserializing) : base(deserializing) {}
    protected CFSAP(CFSAP original, Cloner cloner)
      : base(original, cloner) {}
    public CFSAP() {
      Parameters.Add(new ValueParameter<IntMatrix>("ProcessingTimes", "The processing times of each machine and each job.") { GetsCollected = false });
      Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("SetupTimes", "The sequence dependent set up times of each machine and between all jobs.") { GetsCollected = false });

      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.Add(new PermutationEncoding("sequence", 5, PermutationTypes.RelativeDirected));
      Encoding.Add(new BinaryVectorEncoding("assignment", 5));

      EncodingParameter.GetsCollected = false;
      foreach (var param in ((IEncoding)Encoding).Parameters.OfType<IValueParameter>().ToList()) {
        param.GetsCollected = false;
      }

      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 CFSAP(this, cloner);
    }

    public override double Evaluate(Individual individual, IRandom random) {
      var order = individual.Permutation("sequence");
      var assignment = individual.BinaryVector("assignment");
      return Evaluate(order, assignment);
    }

    public int Evaluate(Permutation order, BinaryVector assignment) {
      return EvaluateAssignment(order, assignment, ProcessingTimes, SetupTimes);
    }

    //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;
    }

    //Function to evaluate individual with the specified assignment
    public static int EvaluateAssignment(Permutation order, BinaryVector assignment, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes) {
      if (processingTimes.Rows != 2) throw new ArgumentException("Method can only be used when there are two machines.", "assignment");
      var N = order.Length;
      int T = 0;

      for (int i = 0; i < N; i++) {
        int operation = order[i];
        int machine = assignment[operation] ? 1 : 0;
        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] ? 1 : 0) == 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;
    }

    public void UpdateEncoding() {
      Encoding.Encodings.OfType<PermutationEncoding>().Single().Length = ProcessingTimes.Columns;
      Encoding.Encodings.OfType<BinaryVectorEncoding>().Single().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;
    }
  }
}