source: branches/2864_PermutationProblems/HeuristicLab.Problems.PermutationProblems/3.3/PermutationFlowshopSchedulingProblem.cs @ 16773

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2018 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.PermutationProblems {
  [Item("Permutation Flowshop Scheduling Problem (PFSP)", "Represents a Permutation Flowshop Scheduling Problem")]
  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
  [StorableClass]
  public sealed class PermutationFlowshopSchedulingProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IProblemInstanceConsumer<FSSPData>, IProblemInstanceExporter<FSSPData> {
    #region Fields
    private static readonly FSSPData DefaultInstance = new FSSPData() {
      Name = "Permutation Flowshop Scheduling Problem (PFSP)",
      Description = "The default instance of the PFSP problem in HeuristicLab",
      Jobs = 4,
      Machines = 4,
      //BestKnownQuality = 328,
      ProcessingTimes = new double[,] {
                {5 ,3, 6 ,6 },
                {2 ,4, 8 ,4},
                {4 ,2, 7 ,4},
                {5 ,3, 8 ,6}
            }
    };
    public event EventHandler BestKnownSolutionChanged;
    #endregion

    #region Getter/Setter
    public OptionalValueParameter<Permutation> BestKnownSolutionParameter
    {
      get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
    }
    public OptionalValueParameter<DoubleMatrix> JobMatrixParameter
    {
      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["JobMatrix"]; }
    }
    public Permutation BestKnownSolution
    {
      get { return BestKnownSolutionParameter.Value; }
      set
      {
        BestKnownSolutionParameter.Value = value;
        if (BestKnownSolutionChanged != null) { OnBestKnownSolutionChanged(); }
      }
    }
    public DoubleMatrix JobMatrix
    {
      get { return JobMatrixParameter.Value; }
      set { JobMatrixParameter.Value = value; }
    }

    public override bool Maximization { get { return false; } }
    #endregion

    #region Ctor
    [StorableConstructor]
    private PermutationFlowshopSchedulingProblem(bool deserializing) : base(deserializing) { }
    private PermutationFlowshopSchedulingProblem(PermutationFlowshopSchedulingProblem original, Cloner cloner) : base(original, cloner) { }
    public PermutationFlowshopSchedulingProblem() {
      Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this FSSP instance."));
      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("JobMatrix", "The matrix which contains the jobs,machines and duration."));

      Load(DefaultInstance);
      EvaluatorParameter.GetsCollected = false;
      EvaluatorParameter.Hidden = true;

      Evaluator.QualityParameter.ActualName = "Makespan";
    }
    #endregion

    #region Methods
    public override IDeepCloneable Clone(Cloner cloner) {
      return new PermutationFlowshopSchedulingProblem(this, cloner);
    }

    public void Load(FSSPData data) {
      if (data.BestKnownQuality.HasValue) {
        BestKnownQuality = data.BestKnownQuality.Value;
      }
      Name = data.Name;
      Description = data.Description;
      JobMatrix = new DoubleMatrix(data.ProcessingTimes);
      Encoding.Length = JobMatrix.Columns;

      if (data.BestKnownSchedule != null) {
        int[] permut = data.BestKnownSchedule;
        //Clean up if the first index = 1
        if (!permut.Contains(0)) { permut = permut.Select(v => v - 1).ToArray(); }

        BestKnownSolution = new Permutation(PermutationTypes.Absolute, data.BestKnownSchedule);
        BestKnownQuality = Evaluate(permut, JobMatrix);
      }
    }
    public FSSPData Export() {
      var result = new FSSPData {
        Name = Name,
        Description = Description,
        ProcessingTimes = new double[JobMatrix.Rows, JobMatrix.Columns]
      };

      result.BestKnownQuality = BestKnownQuality;

      if (JobMatrix != null) {
        result.Jobs = JobMatrix.Rows;
        result.Machines = JobMatrix.Columns;
      }

      for (int i = 0; i < JobMatrix.Rows; i++) {
        for (int j = 0; j < JobMatrix.Columns; j++) {
          result.ProcessingTimes[i, j] = JobMatrix[i, j];
        }
      }

      result.BestKnownSchedule = BestKnownSolution != null ? (BestKnownSolution as IntArray).ToArray() : null;

      return result;
    }

    public override double Evaluate(Individual individual, IRandom random) {
      return Evaluate(individual.Permutation().ToArray(), JobMatrix);
    }
    #endregion

    #region Helper Methods
    private void OnBestKnownSolutionChanged() {
      BestKnownSolutionChanged?.Invoke(this, EventArgs.Empty);
    }

    /// <summary>
    /// Calculates the makespan (cMax), meaning the total time from start till the last job on the last machine is done
    /// </summary>
    /// <param name="permutation"></param>
    /// <param name="matrix"></param>
    /// <returns></returns>
    private double Evaluate(int[] permutation, DoubleMatrix matrix) {
      DoubleMatrix calculatedTime = new DoubleMatrix(matrix.Rows, matrix.Columns);
      double runtimePrev;

      double runtimePrevMachine;
      double runtimePrevJobOnThisMachine;

      for (var machineIdx = 0; machineIdx < matrix.Rows; machineIdx++) {
        for (var jobIdx = 0; jobIdx < matrix.Columns; jobIdx++) {
          runtimePrev = 0;

          if (jobIdx == 0 && machineIdx == 0) {  //Nothing to calculate
          } else if (machineIdx == 0) {
            runtimePrev = calculatedTime[machineIdx, jobIdx - 1];
          } else if (jobIdx == 0) {
            runtimePrev = calculatedTime[machineIdx - 1, jobIdx];
          } else {
            runtimePrevMachine = calculatedTime[machineIdx - 1, jobIdx];
            runtimePrevJobOnThisMachine = calculatedTime[machineIdx, jobIdx - 1];
            runtimePrev = runtimePrevMachine > runtimePrevJobOnThisMachine ? runtimePrevMachine : runtimePrevJobOnThisMachine;
          }
          calculatedTime[machineIdx, jobIdx] = matrix[machineIdx, permutation[jobIdx]] + runtimePrev;
        }
      }
      return calculatedTime[calculatedTime.Rows - 1, calculatedTime.Columns - 1];
    }
    #endregion
  }
}