Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 15661 was 15661, checked in by fholzing, 6 years ago

#2864: Simplified Project-Structure

File size: 7.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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
22using System;
23using System.Linq;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.PermutationEncoding;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Problems.Instances;
31using HeuristicLab.Optimization;
32
33
34namespace 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}
Note: See TracBrowser for help on using the repository browser.