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

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2019 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 <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Encodings.RealVectorEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using SimSharp;
using Environment = SimSharp.Environment;
using IRandom = HeuristicLab.Core.IRandom;

namespace HeuristicLab.Problems.Scheduling.MRCPSP {

  [Item("Multi-mode Resource-Constrained Project Scheduling Problem (MRCPSP)", "")]
  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
  [StorableClass]
  public sealed class MultiModeResourceConstrainedProjectSchedulingProblem : SingleObjectiveBasicProblem<MultiEncoding> {
    //public MultiModeResourceConstrainedProjectSchedulingProblem()
    //    : this() {
    //}

    [Storable] private readonly IValueParameter<ItemList<Activity>> activitiesParam;

    [Storable] private readonly IValueParameter<ItemList<ResourceCapacity>> resourceCapacitiesParam;

    public MultiModeResourceConstrainedProjectSchedulingProblem() {
      Parameters.Add(activitiesParam =
        new ValueParameter<ItemList<Activity>>(nameof(Activities), new ItemList<Activity>()));
      Parameters.Add(resourceCapacitiesParam =
        new ValueParameter<ItemList<ResourceCapacity>>(nameof(ResourceCapacities), new ItemList<ResourceCapacity>()));

      Operators.Add(new MrcpspTwoPointCrossover {
        RandomKeyParents = { ActualName = "RandomKey" },
        ModeListParents = { ActualName = "ModeList" },
        RandomKeyChild = { ActualName = "RandomKey" },
        ModeListChild = { ActualName = "ModeList" }
      });
      Operators.Add(new MrcpspImprover());
      Operators.Add(new FeasibilityImprover { Problem = this, EvaluateFunc = Evaluate });
      Operators.Add(new WorkContentImprover { Problem = this, EvaluateFunc = Evaluate });
      Operators.Add(new CriticalPathImprover { Problem = this, EvaluateFunc = Evaluate });
    }

    [StorableConstructor]
    private MultiModeResourceConstrainedProjectSchedulingProblem(bool deserializing)
      : base(deserializing) {
    }

    private MultiModeResourceConstrainedProjectSchedulingProblem(
      MultiModeResourceConstrainedProjectSchedulingProblem original, Cloner cloner)
      : base(original, cloner) {
      activitiesParam = cloner.Clone(original.activitiesParam);
      resourceCapacitiesParam = cloner.Clone(original.resourceCapacitiesParam);
    }

    public ItemList<Activity> Activities {
      get => activitiesParam.Value;
      set => activitiesParam.Value = value;
    }

    public override bool Maximization => false;

    public ItemList<ResourceCapacity> ResourceCapacities {
      get => resourceCapacitiesParam.Value;
      set => resourceCapacitiesParam.Value = value;
    }

    public override IDeepCloneable Clone(Cloner cloner) =>
      new MultiModeResourceConstrainedProjectSchedulingProblem(this, cloner);

    public void InitEncoding() {
      var activities = Activities.Skip(1).Reverse().Skip(1).Reverse().ToList();

      Encoding = new MultiEncoding();
      Encoding.Add(new RealVectorEncoding("RandomKey", activities.Count, 0.0, 1.0));
      Encoding.Add(new IntegerVectorEncoding("ModeList", activities.Count,
        Enumerable.Repeat(1, activities.Count).ToList(), activities.Select(a => a.Modes.Count + 1).ToList()));
    }

    // work content
    public int CalculateWC(RealVector randomKey, IntegerVector modeList) {
      ExtractSolution(randomKey, modeList, out var activities, out _);

      var workContent = 0;

      foreach (var activity in activities) {
        var mode = activity.Item1.Modes.Single(m => m.Number == activity.Item3);
        workContent += mode.ResourceDemands.Where(d => IsRenewable(d.Number)).Sum(demand => demand.Demand);
      }

      return workContent;
    }

    public class CpActivity {
      public int Id { get; set; }
      public int Duration { get; set; }
      public List<CpActivity> Predecessors { get; set; } = new List<CpActivity>();
      public List<CpActivity> Successors { get; set; } = new List<CpActivity>();
      public bool IsStartNode { get; set; }
      public bool IsEndNode { get; set; }
      public int EarliestStart { get; set; }
      public int EarliestEnd { get; set; }
      public int LatestStart { get; set; }
      public int LatestEnd { get; set; }
    }

    public int GetCriticalPathLength(ref List<CpActivity> activities) {
      ForwardScheduling(activities.First(x => x.IsStartNode));
      var endNode = activities.First(x => x.IsEndNode);
      return endNode.EarliestEnd;
    }

    public List<CpActivity> GetCriticalActivities(ref List<CpActivity> activities) {
      ForwardScheduling(activities.First(x => x.IsStartNode));
      var endNode = activities.First(x => x.IsEndNode);
      endNode.LatestEnd = endNode.EarliestEnd;
      endNode.LatestStart = endNode.LatestEnd - endNode.Duration;
      BackwardScheduling(endNode);
      return activities
        .Where(a => a.EarliestEnd - a.LatestEnd == 0 && a.EarliestStart - a.LatestStart == 0)
        .ToList();
    }

    private static void ForwardScheduling(CpActivity position) {
      foreach (var successor in position.Successors) {
        foreach (var predecessor in successor.Predecessors) {
          if (successor.EarliestStart < predecessor.EarliestEnd)
            successor.EarliestStart = predecessor.EarliestEnd;
        }

        successor.EarliestEnd = successor.EarliestStart + successor.Duration;
      }

      foreach (var successor in position.Successors) {
        ForwardScheduling(successor);
      }
    }

    private static void BackwardScheduling(CpActivity cpActivity) {
      foreach (var predecessor in cpActivity.Predecessors) {
        foreach (var successor in predecessor.Successors) {
          if (predecessor.LatestEnd == 0) {
            predecessor.LatestEnd = successor.LatestStart;
          } else if (predecessor.LatestEnd > successor.LatestStart) {
            predecessor.LatestEnd = successor.LatestStart;
          }
        }

        predecessor.LatestStart = predecessor.LatestEnd - predecessor.Duration;
      }

      foreach (var predecessor in cpActivity.Predecessors) {
        BackwardScheduling(predecessor);
      }
    }

    public int CalculateCP(RealVector randomKey, IntegerVector modeList) {
      ExtractSolution(randomKey, modeList, out var activities, out _);

      var successors = activities.SelectMany(a => a.Item1.Successors.Select(s => s.Value));
      var startNode = activities.Single(a => successors.All(s => s != a.Item1.Number)).Item1.Number;

      var act = new List<CpActivity>();
      foreach (var activity in activities) {
        var a = activity.Item1;
        var m = activity.Item1.Modes.Single(x => x.Number == activity.Item3);

        act.Add(new CpActivity {
          Id = a.Number,
          Duration = m.Duration,
          IsStartNode = a.Number == startNode,
          IsEndNode = !a.Successors.Any()
        });
      }

      foreach (var activity in activities) {
        var a = activity.Item1;
        var ax = act.Single(x => x.Id == a.Number);
        foreach (var s in a.Successors) {
          var sx = act.Single(x => x.Id == s.Value);
          ax.Successors.Add(sx);
          sx.Predecessors.Add(ax);
        }
      }

      return GetCriticalPathLength(ref act);
    }

    public int CalculateERR(Individual individual)
      => CalculateERR(individual.RealVector("RandomKey"), individual.IntegerVector("ModeList"));

    // excess of resource request
    public int CalculateERR(RealVector randomKey, IntegerVector modeList) {
      ExtractSolution(randomKey, modeList, out var activities, out _);

      var totalDemands = ResourceCapacities.Where(c => !c.IsRenewable).ToDictionary(c => c.Number, c => 0);

      foreach (var activity in activities) {
        var mode = activity.Item1.Modes.Single(m => m.Number == activity.Item3);
        foreach (var demand in mode.ResourceDemands) {
          if (totalDemands.ContainsKey(demand.Number))
            totalDemands[demand.Number] += demand.Demand;
        }
      }

      return totalDemands.Sum(d => Math.Max(0, d.Value - ResourceCapacities.Single(c => c.Number == d.Key).Capacity));
    }

    private void ExtractSolution(Individual individual, out List<Tuple<Activity, double, int>> activities,
      out Dictionary<int, List<int>> dependencies)
      => ExtractSolution(individual.RealVector("RandomKey"), individual.IntegerVector("ModeList"), out activities,
        out dependencies);

    private void ExtractSolution(RealVector randomKey, IntegerVector modeList, out List<Tuple<Activity, double, int>> activities, out Dictionary<int, List<int>> dependencies) {
      activities = new List<Tuple<Activity, double, int>>(Activities.Count);
      dependencies = new Dictionary<int, List<int>>(Activities.Count);

      var act = Activities[0];
      activities.Add(Tuple.Create(act, double.MinValue, act.Modes.First().Number));
      dependencies[act.Number] = new List<int>();

      for (var i = 1; i < Activities.Count - 1; i++) {
        activities.Add(Tuple.Create(Activities[i], randomKey[i - 1], modeList[i - 1]));
        dependencies[Activities[i].Number] = new List<int>();
      }

      act = Activities[Activities.Count - 1];
      activities.Add(Tuple.Create(act, double.MaxValue, act.Modes.First().Number));
      dependencies[act.Number] = new List<int>();

      foreach (var activity in Activities) {
        foreach (var successor in activity.Successors) {
          dependencies[successor.Value].Add(activity.Number);
        }
      }

      activities = activities.OrderBy(a => a.Item2).ToList();
    }

    public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
      var bestIndividual = GetBestIndividual(individuals, qualities, Maximization);
      results.AddOrUpdateResult("BestSolution.RandomKey", bestIndividual.Item1.RealVector("RandomKey"));
      results.AddOrUpdateResult("BestSolution.ModeList", bestIndividual.Item1.IntegerVector("ModeList"));
      base.Analyze(individuals, qualities, results, random);
    }

    public override double Evaluate(Individual individual, IRandom random) {
      ExtractSolution(individual, out var activities, out var dependencies);

      var env = new Environment();
      var procActivities = new Dictionary<int, Process>();

      var resources = ResourceCapacities
        .ToDictionary(resource => resource.Number, resource => new Container(env, resource.Capacity, resource.Capacity));

      foreach (var activity in activities) {
        procActivities[activity.Item1.Number] =
          env.Process(Job(env, procActivities, activity, resources, dependencies[activity.Item1.Number]));
      }

      // fitness function by Hartmann (2001)
      try {
        env.Run();
        return env.NowD;
      } catch (InvalidOperationException) {
        var T = Activities.Sum(a => a.Modes.Max(m => m.Duration));
        return T + CalculateERR(individual);
      }
    }

    private bool IsRenewable(int resourceNumber) => ResourceCapacities.Single(r => r.Number == resourceNumber).IsRenewable;

    private IEnumerable<Event> Job(Environment env, IReadOnlyDictionary<int, Process> procActivities,
      Tuple<Activity, double, int> activity, IReadOnlyDictionary<int, Container> resources, IEnumerable<int> deps) {
      var mode = activity.Item1.Modes[activity.Item3 - 1];
      var demands = mode.ResourceDemands.Where(d => d.Demand > 0).ToList();
      var rres = demands.Where(d => IsRenewable(d.Number)).Select(d => Tuple.Create(resources[d.Number], d.Demand));
      var nres = demands.Where(d => !IsRenewable(d.Number)).Select(d => Tuple.Create(resources[d.Number], d.Demand));

      yield return new AllOf(env, deps.Select(d => procActivities[d]));

      foreach (var nr in nres) {
        if (nr.Item2 > nr.Item1.Level)
          throw new InvalidOperationException();
        yield return nr.Item1.Get(nr.Item2);
      }

      foreach (var rr in rres) {
        yield return rr.Item1.Get(rr.Item2);
        yield return env.TimeoutD(mode.Duration);
        yield return rr.Item1.Put(rr.Item2);
      }
    }
  }
}