source: branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/CFSAP.cs @ 15533

Last change on this file since 15533 was 15533, checked in by ddorfmei, 5 years ago

#2747: Improved hard-coded genetic algorithm

  • implemented restart strategy
  • implemented 1-Opt algorithm
  • added parameters to control restart strategy and optimal assignment strategy
  • additional results: best solution found after number of generations, jobs/nests (for evaluation only)
File size: 8.6 KB
Line 
1#region License Information
2
3/* HeuristicLab
4 * Copyright (C) 2002-2017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
5 *
6 * This file is part of HeuristicLab.
7 *
8 * HeuristicLab is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * HeuristicLab is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#endregion
23
24using System;
25using System.Linq;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.BinaryVectorEncoding;
30using HeuristicLab.Encodings.PermutationEncoding;
31using HeuristicLab.Optimization;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.Problems.Instances;
35
36namespace HeuristicLab.Problems.Scheduling.CFSAP {
37  [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.")]
38  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
39  [StorableClass]
40  public class CFSAP : SingleObjectiveBasicProblem<MultiEncoding>, ICFSAP, IProblemInstanceConsumer<CFSAPData> {
41    public override bool Maximization { get { return false; } }
42
43    public IValueParameter<IntMatrix> ProcessingTimesParameter {
44      get { return (IValueParameter<IntMatrix>)Parameters["ProcessingTimes"]; }
45    }
46
47    public IntMatrix ProcessingTimes {
48      get { return ProcessingTimesParameter.Value; }
49      set { ProcessingTimesParameter.Value = value; }
50    }
51
52    public IValueParameter<ItemList<IntMatrix>> SetupTimesParameter {
53      get { return (IValueParameter<ItemList<IntMatrix>>)Parameters["SetupTimes"]; }
54    }
55
56    public ItemList<IntMatrix> SetupTimes {
57      get { return SetupTimesParameter.Value; }
58      set { SetupTimesParameter.Value = value; }
59    }
60
61    [StorableConstructor]
62    protected CFSAP(bool deserializing) : base(deserializing) {}
63    protected CFSAP(CFSAP original, Cloner cloner)
64      : base(original, cloner) {}
65    public CFSAP() {
66      Parameters.Add(new ValueParameter<IntMatrix>("ProcessingTimes", "The processing times of each machine and each job.") { GetsCollected = false });
67      Parameters.Add(new ValueParameter<ItemList<IntMatrix>>("SetupTimes", "The sequence dependent set up times of each machine and between all jobs.") { GetsCollected = false });
68
69      ProcessingTimesParameter.Value = new IntMatrix(new int[,] {
70        { 5, 4, 3, 2, 1 },
71        { 1, 2, 3, 4, 5 }
72      });
73
74      SetupTimesParameter.Value = new ItemList<IntMatrix>(2);
75      SetupTimesParameter.Value.Add(new IntMatrix(new int[,] {
76        { 3, 4, 5, 4, 3 },
77        { 3, 4, 5, 4, 3 },
78        { 3, 4, 5, 4, 3 },
79        { 3, 4, 5, 4, 3 },
80        { 3, 4, 5, 4, 3 },
81      }));
82      SetupTimesParameter.Value.Add(new IntMatrix(new int[,] {
83        { 5, 4, 3, 4, 5 },
84        { 5, 4, 3, 4, 5 },
85        { 5, 4, 3, 4, 5 },
86        { 5, 4, 3, 4, 5 },
87        { 5, 4, 3, 4, 5 },
88      }));
89
90      Encoding.Add(new PermutationEncoding("sequence", 5, PermutationTypes.RelativeDirected));
91      Encoding.Add(new BinaryVectorEncoding("assignment", 5));
92
93      EncodingParameter.GetsCollected = false;
94      foreach (var param in ((IEncoding)Encoding).Parameters.OfType<IValueParameter>().ToList()) {
95        param.GetsCollected = false;
96      }
97
98      Operators.RemoveAll(x => x is SingleObjectiveMoveGenerator);
99      Operators.RemoveAll(x => x is SingleObjectiveMoveEvaluator);
100      Operators.RemoveAll(x => x is SingleObjectiveMoveMaker);
101    }
102
103    public override IDeepCloneable Clone(Cloner cloner) {
104      return new CFSAP(this, cloner);
105    }
106
107    public override double Evaluate(Individual individual, IRandom random) {
108      var order = individual.Permutation("sequence");
109      var assignment = individual.BinaryVector("assignment");
110      return Evaluate(order, assignment);
111    }
112
113    public int Evaluate(Permutation order, BinaryVector assignment) {
114      return EvaluateAssignment(order, assignment, ProcessingTimes, SetupTimes);
115    }
116
117    //Function to evaluate individual with the specified assignment
118    public static int EvaluateAssignement(Permutation order, int[] assignment, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes) {
119      var N = order.Length;
120      int T = 0;
121
122      for (int i = 0; i < N; i++) {
123        int operation = order[i];
124        int machine = assignment[operation];
125        T += processingTimes[machine, operation];
126      }
127
128      for (int machine = 0; machine < 2; machine++) {
129        int first = -1;
130        int last = -1;
131        for (int i = 0; i < N; i++) {
132          int operation = order[i];
133          if (assignment[operation] == machine) {
134            if (first == -1)
135              first = operation;
136            else
137              T += setupTimes[machine][last, operation];
138            last = operation;
139          }
140        }
141        if (last != -1 && first != -1)
142          T += setupTimes[machine][last, first];
143      }
144
145      return T;
146    }
147
148    //Function to evaluate individual with the specified assignment
149    public static int EvaluateAssignment(Permutation order, BinaryVector assignment, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes) {
150      if (processingTimes.Rows != 2) throw new ArgumentException("Method can only be used when there are two machines.", "assignment");
151      var N = order.Length;
152      int T = 0;
153
154      for (int i = 0; i < N; i++) {
155        int operation = order[i];
156        int machine = assignment[operation] ? 1 : 0;
157        T += processingTimes[machine, operation];
158      }
159
160      for (int machine = 0; machine < 2; machine++) {
161        int first = -1;
162        int last = -1;
163        for (int i = 0; i < N; i++) {
164          int operation = order[i];
165          if ((assignment[operation] ? 1 : 0) == machine) {
166            if (first == -1)
167              first = operation;
168            else
169              T += setupTimes[machine][last, operation];
170            last = operation;
171          }
172        }
173        if (last != -1 && first != -1)
174          T += setupTimes[machine][last, first];
175      }
176
177      return T;
178    }
179
180    public void UpdateEncoding() {
181      Encoding.Encodings.OfType<PermutationEncoding>().Single().Length = ProcessingTimes.Columns;
182      Encoding.Encodings.OfType<BinaryVectorEncoding>().Single().Length = ProcessingTimes.Columns;
183    }
184
185    /// <summary>
186    /// Imports the first nest (index 0) given in the CFSAPData.
187    /// This is the same as calling Load(data, 0).
188    /// </summary>
189    /// <param name="data">The data of all nests.</param>
190    public void Load(CFSAPData data) {
191      Load(data, 0);
192    }
193
194    /// <summary>
195    /// Imports a specific nest given in the CFSAPData.
196    /// </summary>
197    /// <param name="data">The data of all nests.</param>
198    /// <param name="nest">The zero-based index of the nest that should be imported.</param>
199    public void Load(CFSAPData data, int nest) {
200      if (data.Machines[nest] != 2) throw new ArgumentException("Currently only two machines per nest are supported.");
201      if (nest < 0 || nest >= data.Nests) throw new ArgumentException("Nest must be a zero-based index.");
202      var pr = new int[data.Machines[nest], data.Jobs];
203      for (var i = 0; i < data.Machines[nest]; i++)
204        for (var j = 0; j < data.Jobs; j++)
205          pr[i, j] = data.ProcessingTimes[nest][i][j];
206      ProcessingTimesParameter.Value = new IntMatrix(pr);
207      var setups = new ItemList<IntMatrix>(data.Machines[nest]);
208      for (var m = 0; m < data.SetupTimes[nest].GetLength(0); m++) {
209        var setupTimes = new int[data.Jobs, data.Jobs];
210        for (var i = 0; i < data.Jobs; i++)
211          for (var j = 0; j < data.Jobs; j++)
212            setupTimes[i, j] = data.SetupTimes[nest][m][i][j];
213        setups.Add(new IntMatrix(setupTimes));
214      }
215      SetupTimesParameter.Value = setups;
216      UpdateEncoding();
217      Name = data.Name + "-nest" + nest;
218      Description = data.Description;
219      if (data.BestKnownCycleTime.HasValue)
220        BestKnownQuality = data.BestKnownCycleTime.Value;
221      else BestKnownQualityParameter.Value = null;
222    }
223  }
224}
Note: See TracBrowser for help on using the repository browser.