1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  *


5  * This file is part of HeuristicLab.


6  *


7  * HeuristicLab is free software: you can redistribute it and/or modify


8  * it under the terms of the GNU General Public License as published by


9  * the Free Software Foundation, either version 3 of the License, or


10  * (at your option) any later version.


11  *


12  * HeuristicLab is distributed in the hope that it will be useful,


13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


15  * GNU General Public License for more details.


16  *


17  * You should have received a copy of the GNU General Public License


18  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


19  */


20  #endregion


21 


22  using System;


23  using System.Linq;


24  using HeuristicLab.Common;


25  using HeuristicLab.Core;


26  using HeuristicLab.Data;


27  using HeuristicLab.Encodings.PermutationEncoding;


28  using HeuristicLab.Optimization;


29  using HeuristicLab.Parameters;


30  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


31  using HeuristicLab.Problems.Instances;


32 


33 


34  namespace HeuristicLab.Problems.PermutationProblems {


35  [Item("Permutation Flowshop Scheduling Problem (PFSP)", "Represents a Permutation Flowshop Scheduling Problem")]


36  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]


37  [StorableClass]


38  public sealed class PermutationFlowshopSchedulingProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IProblemInstanceConsumer<FSSPData>, IProblemInstanceExporter<FSSPData> {


39  #region Fields


40  private static readonly FSSPData DefaultInstance = new FSSPData() {


41  Name = "Permutation Flowshop Scheduling Problem (PFSP)",


42  Description = "The default instance of the PFSP problem in HeuristicLab",


43  Jobs = 4,


44  Machines = 4,


45  //BestKnownQuality = 328,


46  ProcessingTimes = new double[,] {


47  {5 ,3, 6 ,6 },


48  {2 ,4, 8 ,4},


49  {4 ,2, 7 ,4},


50  {5 ,3, 8 ,6}


51  }


52  };


53  public event EventHandler BestKnownSolutionChanged;


54  #endregion


55 


56  #region Getter/Setter


57  public OptionalValueParameter<Permutation> BestKnownSolutionParameter


58  {


59  get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }


60  }


61  public OptionalValueParameter<DoubleMatrix> JobMatrixParameter


62  {


63  get { return (OptionalValueParameter<DoubleMatrix>)Parameters["JobMatrix"]; }


64  }


65  public Permutation BestKnownSolution


66  {


67  get { return BestKnownSolutionParameter.Value; }


68  set


69  {


70  BestKnownSolutionParameter.Value = value;


71  if (BestKnownSolutionChanged != null) { OnBestKnownSolutionChanged(); }


72  }


73  }


74  public DoubleMatrix JobMatrix


75  {


76  get { return JobMatrixParameter.Value; }


77  set { JobMatrixParameter.Value = value; }


78  }


79 


80  public override bool Maximization { get { return false; } }


81  #endregion


82 


83  #region Ctor


84  [StorableConstructor]


85  private PermutationFlowshopSchedulingProblem(bool deserializing) : base(deserializing) { }


86  private PermutationFlowshopSchedulingProblem(PermutationFlowshopSchedulingProblem original, Cloner cloner) : base(original, cloner) { }


87  public PermutationFlowshopSchedulingProblem() {


88  Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this FSSP instance."));


89  Parameters.Add(new OptionalValueParameter<DoubleMatrix>("JobMatrix", "The matrix which contains the jobs,machines and duration."));


90 


91  Load(DefaultInstance);


92  EvaluatorParameter.GetsCollected = false;


93  EvaluatorParameter.Hidden = true;


94 


95  Evaluator.QualityParameter.ActualName = "Makespan";


96  }


97  #endregion


98 


99  #region Methods


100  public override IDeepCloneable Clone(Cloner cloner) {


101  return new PermutationFlowshopSchedulingProblem(this, cloner);


102  }


103 


104  public void Load(FSSPData data) {


105  if (data.BestKnownQuality.HasValue) {


106  BestKnownQuality = data.BestKnownQuality.Value;


107  }


108  Name = data.Name;


109  Description = data.Description;


110  JobMatrix = new DoubleMatrix(data.ProcessingTimes);


111  Encoding.Length = JobMatrix.Columns;


112 


113  if (data.BestKnownSchedule != null) {


114  int[] permut = data.BestKnownSchedule;


115  //Clean up if the first index = 1


116  if (!permut.Contains(0)) { permut = permut.Select(v => v  1).ToArray(); }


117 


118  BestKnownSolution = new Permutation(PermutationTypes.Absolute, data.BestKnownSchedule);


119  BestKnownQuality = Evaluate(permut, JobMatrix);


120  }


121  }


122  public FSSPData Export() {


123  var result = new FSSPData {


124  Name = Name,


125  Description = Description,


126  ProcessingTimes = new double[JobMatrix.Rows, JobMatrix.Columns]


127  };


128 


129  result.BestKnownQuality = BestKnownQuality;


130 


131  if (JobMatrix != null) {


132  result.Jobs = JobMatrix.Rows;


133  result.Machines = JobMatrix.Columns;


134  }


135 


136  for (int i = 0; i < JobMatrix.Rows; i++) {


137  for (int j = 0; j < JobMatrix.Columns; j++) {


138  result.ProcessingTimes[i, j] = JobMatrix[i, j];


139  }


140  }


141 


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


143 


144  return result;


145  }


146 


147  public override double Evaluate(Individual individual, IRandom random) {


148  return Evaluate(individual.Permutation().ToArray(), JobMatrix);


149  }


150  #endregion


151 


152  #region Helper Methods


153  private void OnBestKnownSolutionChanged() {


154  BestKnownSolutionChanged?.Invoke(this, EventArgs.Empty);


155  }


156 


157  /// <summary>


158  /// Calculates the makespan (cMax), meaning the total time from start till the last job on the last machine is done


159  /// </summary>


160  /// <param name="permutation"></param>


161  /// <param name="matrix"></param>


162  /// <returns></returns>


163  private double Evaluate(int[] permutation, DoubleMatrix matrix) {


164  DoubleMatrix calculatedTime = new DoubleMatrix(matrix.Rows, matrix.Columns);


165  double runtimePrev;


166 


167  double runtimePrevMachine;


168  double runtimePrevJobOnThisMachine;


169 


170  for (var machineIdx = 0; machineIdx < matrix.Rows; machineIdx++) {


171  for (var jobIdx = 0; jobIdx < matrix.Columns; jobIdx++) {


172  runtimePrev = 0;


173 


174  if (jobIdx == 0 && machineIdx == 0) { //Nothing to calculate


175  } else if (machineIdx == 0) {


176  runtimePrev = calculatedTime[machineIdx, jobIdx  1];


177  } else if (jobIdx == 0) {


178  runtimePrev = calculatedTime[machineIdx  1, jobIdx];


179  } else {


180  runtimePrevMachine = calculatedTime[machineIdx  1, jobIdx];


181  runtimePrevJobOnThisMachine = calculatedTime[machineIdx, jobIdx  1];


182  runtimePrev = runtimePrevMachine > runtimePrevJobOnThisMachine ? runtimePrevMachine : runtimePrevJobOnThisMachine;


183  }


184  calculatedTime[machineIdx, jobIdx] = matrix[machineIdx, permutation[jobIdx]] + runtimePrev;


185  }


186  }


187  return calculatedTime[calculatedTime.Rows  1, calculatedTime.Columns  1];


188  }


189  #endregion


190  }


191  }

