#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 . */ #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, IProblemInstanceConsumer, IProblemInstanceExporter { #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 BestKnownSolutionParameter { get { return (OptionalValueParameter)Parameters["BestKnownSolution"]; } } public OptionalValueParameter JobMatrixParameter { get { return (OptionalValueParameter)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("BestKnownSolution", "The best known solution of this FSSP instance.")); Parameters.Add(new OptionalValueParameter("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); } /// /// Calculates the makespan (cMax), meaning the total time from start till the last job on the last machine is done /// /// /// /// 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 } }