Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2981_MRCPSP/HeuristicLab.Problem.Scheduling.MRCPSP/3.3/MultiModeResourceConstrainedProjectSchedulingProblem.cs

Last change on this file was 16598, checked in by ddorfmei, 6 years ago

#2981:

  • added problem definition
  • added improvers and crossover
  • added file importer
File size: 13.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2019 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.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Encodings.IntegerVectorEncoding;
28using HeuristicLab.Encodings.RealVectorEncoding;
29using HeuristicLab.Optimization;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32using SimSharp;
33using Environment = SimSharp.Environment;
34using IRandom = HeuristicLab.Core.IRandom;
35
36namespace HeuristicLab.Problems.Scheduling.MRCPSP {
37
38  [Item("Multi-mode Resource-Constrained Project Scheduling Problem (MRCPSP)", "")]
39  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
40  [StorableClass]
41  public sealed class MultiModeResourceConstrainedProjectSchedulingProblem : SingleObjectiveBasicProblem<MultiEncoding> {
42    //public MultiModeResourceConstrainedProjectSchedulingProblem()
43    //    : this() {
44    //}
45
46    [Storable] private readonly IValueParameter<ItemList<Activity>> activitiesParam;
47
48    [Storable] private readonly IValueParameter<ItemList<ResourceCapacity>> resourceCapacitiesParam;
49
50    public MultiModeResourceConstrainedProjectSchedulingProblem() {
51      Parameters.Add(activitiesParam =
52        new ValueParameter<ItemList<Activity>>(nameof(Activities), new ItemList<Activity>()));
53      Parameters.Add(resourceCapacitiesParam =
54        new ValueParameter<ItemList<ResourceCapacity>>(nameof(ResourceCapacities), new ItemList<ResourceCapacity>()));
55
56      Operators.Add(new MrcpspTwoPointCrossover {
57        RandomKeyParents = { ActualName = "RandomKey" },
58        ModeListParents = { ActualName = "ModeList" },
59        RandomKeyChild = { ActualName = "RandomKey" },
60        ModeListChild = { ActualName = "ModeList" }
61      });
62      Operators.Add(new MrcpspImprover());
63      Operators.Add(new FeasibilityImprover { Problem = this, EvaluateFunc = Evaluate });
64      Operators.Add(new WorkContentImprover { Problem = this, EvaluateFunc = Evaluate });
65      Operators.Add(new CriticalPathImprover { Problem = this, EvaluateFunc = Evaluate });
66    }
67
68    [StorableConstructor]
69    private MultiModeResourceConstrainedProjectSchedulingProblem(bool deserializing)
70      : base(deserializing) {
71    }
72
73    private MultiModeResourceConstrainedProjectSchedulingProblem(
74      MultiModeResourceConstrainedProjectSchedulingProblem original, Cloner cloner)
75      : base(original, cloner) {
76      activitiesParam = cloner.Clone(original.activitiesParam);
77      resourceCapacitiesParam = cloner.Clone(original.resourceCapacitiesParam);
78    }
79
80    public ItemList<Activity> Activities {
81      get => activitiesParam.Value;
82      set => activitiesParam.Value = value;
83    }
84
85    public override bool Maximization => false;
86
87    public ItemList<ResourceCapacity> ResourceCapacities {
88      get => resourceCapacitiesParam.Value;
89      set => resourceCapacitiesParam.Value = value;
90    }
91
92    public override IDeepCloneable Clone(Cloner cloner) =>
93      new MultiModeResourceConstrainedProjectSchedulingProblem(this, cloner);
94
95    public void InitEncoding() {
96      var activities = Activities.Skip(1).Reverse().Skip(1).Reverse().ToList();
97
98      Encoding = new MultiEncoding();
99      Encoding.Add(new RealVectorEncoding("RandomKey", activities.Count, 0.0, 1.0));
100      Encoding.Add(new IntegerVectorEncoding("ModeList", activities.Count,
101        Enumerable.Repeat(1, activities.Count).ToList(), activities.Select(a => a.Modes.Count + 1).ToList()));
102    }
103
104    // work content
105    public int CalculateWC(RealVector randomKey, IntegerVector modeList) {
106      ExtractSolution(randomKey, modeList, out var activities, out _);
107
108      var workContent = 0;
109
110      foreach (var activity in activities) {
111        var mode = activity.Item1.Modes.Single(m => m.Number == activity.Item3);
112        workContent += mode.ResourceDemands.Where(d => IsRenewable(d.Number)).Sum(demand => demand.Demand);
113      }
114
115      return workContent;
116    }
117
118    public class CpActivity {
119      public int Id { get; set; }
120      public int Duration { get; set; }
121      public List<CpActivity> Predecessors { get; set; } = new List<CpActivity>();
122      public List<CpActivity> Successors { get; set; } = new List<CpActivity>();
123      public bool IsStartNode { get; set; }
124      public bool IsEndNode { get; set; }
125      public int EarliestStart { get; set; }
126      public int EarliestEnd { get; set; }
127      public int LatestStart { get; set; }
128      public int LatestEnd { get; set; }
129    }
130
131    public int GetCriticalPathLength(ref List<CpActivity> activities) {
132      ForwardScheduling(activities.First(x => x.IsStartNode));
133      var endNode = activities.First(x => x.IsEndNode);
134      return endNode.EarliestEnd;
135    }
136
137    public List<CpActivity> GetCriticalActivities(ref List<CpActivity> activities) {
138      ForwardScheduling(activities.First(x => x.IsStartNode));
139      var endNode = activities.First(x => x.IsEndNode);
140      endNode.LatestEnd = endNode.EarliestEnd;
141      endNode.LatestStart = endNode.LatestEnd - endNode.Duration;
142      BackwardScheduling(endNode);
143      return activities
144        .Where(a => a.EarliestEnd - a.LatestEnd == 0 && a.EarliestStart - a.LatestStart == 0)
145        .ToList();
146    }
147
148    private static void ForwardScheduling(CpActivity position) {
149      foreach (var successor in position.Successors) {
150        foreach (var predecessor in successor.Predecessors) {
151          if (successor.EarliestStart < predecessor.EarliestEnd)
152            successor.EarliestStart = predecessor.EarliestEnd;
153        }
154
155        successor.EarliestEnd = successor.EarliestStart + successor.Duration;
156      }
157
158      foreach (var successor in position.Successors) {
159        ForwardScheduling(successor);
160      }
161    }
162
163    private static void BackwardScheduling(CpActivity cpActivity) {
164      foreach (var predecessor in cpActivity.Predecessors) {
165        foreach (var successor in predecessor.Successors) {
166          if (predecessor.LatestEnd == 0) {
167            predecessor.LatestEnd = successor.LatestStart;
168          } else if (predecessor.LatestEnd > successor.LatestStart) {
169            predecessor.LatestEnd = successor.LatestStart;
170          }
171        }
172
173        predecessor.LatestStart = predecessor.LatestEnd - predecessor.Duration;
174      }
175
176      foreach (var predecessor in cpActivity.Predecessors) {
177        BackwardScheduling(predecessor);
178      }
179    }
180
181    public int CalculateCP(RealVector randomKey, IntegerVector modeList) {
182      ExtractSolution(randomKey, modeList, out var activities, out _);
183
184      var successors = activities.SelectMany(a => a.Item1.Successors.Select(s => s.Value));
185      var startNode = activities.Single(a => successors.All(s => s != a.Item1.Number)).Item1.Number;
186
187      var act = new List<CpActivity>();
188      foreach (var activity in activities) {
189        var a = activity.Item1;
190        var m = activity.Item1.Modes.Single(x => x.Number == activity.Item3);
191
192        act.Add(new CpActivity {
193          Id = a.Number,
194          Duration = m.Duration,
195          IsStartNode = a.Number == startNode,
196          IsEndNode = !a.Successors.Any()
197        });
198      }
199
200      foreach (var activity in activities) {
201        var a = activity.Item1;
202        var ax = act.Single(x => x.Id == a.Number);
203        foreach (var s in a.Successors) {
204          var sx = act.Single(x => x.Id == s.Value);
205          ax.Successors.Add(sx);
206          sx.Predecessors.Add(ax);
207        }
208      }
209
210      return GetCriticalPathLength(ref act);
211    }
212
213    public int CalculateERR(Individual individual)
214      => CalculateERR(individual.RealVector("RandomKey"), individual.IntegerVector("ModeList"));
215
216    // excess of resource request
217    public int CalculateERR(RealVector randomKey, IntegerVector modeList) {
218      ExtractSolution(randomKey, modeList, out var activities, out _);
219
220      var totalDemands = ResourceCapacities.Where(c => !c.IsRenewable).ToDictionary(c => c.Number, c => 0);
221
222      foreach (var activity in activities) {
223        var mode = activity.Item1.Modes.Single(m => m.Number == activity.Item3);
224        foreach (var demand in mode.ResourceDemands) {
225          if (totalDemands.ContainsKey(demand.Number))
226            totalDemands[demand.Number] += demand.Demand;
227        }
228      }
229
230      return totalDemands.Sum(d => Math.Max(0, d.Value - ResourceCapacities.Single(c => c.Number == d.Key).Capacity));
231    }
232
233    private void ExtractSolution(Individual individual, out List<Tuple<Activity, double, int>> activities,
234      out Dictionary<int, List<int>> dependencies)
235      => ExtractSolution(individual.RealVector("RandomKey"), individual.IntegerVector("ModeList"), out activities,
236        out dependencies);
237
238    private void ExtractSolution(RealVector randomKey, IntegerVector modeList, out List<Tuple<Activity, double, int>> activities, out Dictionary<int, List<int>> dependencies) {
239      activities = new List<Tuple<Activity, double, int>>(Activities.Count);
240      dependencies = new Dictionary<int, List<int>>(Activities.Count);
241
242      var act = Activities[0];
243      activities.Add(Tuple.Create(act, double.MinValue, act.Modes.First().Number));
244      dependencies[act.Number] = new List<int>();
245
246      for (var i = 1; i < Activities.Count - 1; i++) {
247        activities.Add(Tuple.Create(Activities[i], randomKey[i - 1], modeList[i - 1]));
248        dependencies[Activities[i].Number] = new List<int>();
249      }
250
251      act = Activities[Activities.Count - 1];
252      activities.Add(Tuple.Create(act, double.MaxValue, act.Modes.First().Number));
253      dependencies[act.Number] = new List<int>();
254
255      foreach (var activity in Activities) {
256        foreach (var successor in activity.Successors) {
257          dependencies[successor.Value].Add(activity.Number);
258        }
259      }
260
261      activities = activities.OrderBy(a => a.Item2).ToList();
262    }
263
264    public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
265      var bestIndividual = GetBestIndividual(individuals, qualities, Maximization);
266      results.AddOrUpdateResult("BestSolution.RandomKey", bestIndividual.Item1.RealVector("RandomKey"));
267      results.AddOrUpdateResult("BestSolution.ModeList", bestIndividual.Item1.IntegerVector("ModeList"));
268      base.Analyze(individuals, qualities, results, random);
269    }
270
271    public override double Evaluate(Individual individual, IRandom random) {
272      ExtractSolution(individual, out var activities, out var dependencies);
273
274      var env = new Environment();
275      var procActivities = new Dictionary<int, Process>();
276
277      var resources = ResourceCapacities
278        .ToDictionary(resource => resource.Number, resource => new Container(env, resource.Capacity, resource.Capacity));
279
280      foreach (var activity in activities) {
281        procActivities[activity.Item1.Number] =
282          env.Process(Job(env, procActivities, activity, resources, dependencies[activity.Item1.Number]));
283      }
284
285      // fitness function by Hartmann (2001)
286      try {
287        env.Run();
288        return env.NowD;
289      } catch (InvalidOperationException) {
290        var T = Activities.Sum(a => a.Modes.Max(m => m.Duration));
291        return T + CalculateERR(individual);
292      }
293    }
294
295    private bool IsRenewable(int resourceNumber) => ResourceCapacities.Single(r => r.Number == resourceNumber).IsRenewable;
296
297    private IEnumerable<Event> Job(Environment env, IReadOnlyDictionary<int, Process> procActivities,
298      Tuple<Activity, double, int> activity, IReadOnlyDictionary<int, Container> resources, IEnumerable<int> deps) {
299      var mode = activity.Item1.Modes[activity.Item3 - 1];
300      var demands = mode.ResourceDemands.Where(d => d.Demand > 0).ToList();
301      var rres = demands.Where(d => IsRenewable(d.Number)).Select(d => Tuple.Create(resources[d.Number], d.Demand));
302      var nres = demands.Where(d => !IsRenewable(d.Number)).Select(d => Tuple.Create(resources[d.Number], d.Demand));
303
304      yield return new AllOf(env, deps.Select(d => procActivities[d]));
305
306      foreach (var nr in nres) {
307        if (nr.Item2 > nr.Item1.Level)
308          throw new InvalidOperationException();
309        yield return nr.Item1.Get(nr.Item2);
310      }
311
312      foreach (var rr in rres) {
313        yield return rr.Item1.Get(rr.Item2);
314        yield return env.TimeoutD(mode.Duration);
315        yield return rr.Item1.Put(rr.Item2);
316      }
317    }
318  }
319}
Note: See TracBrowser for help on using the repository browser.