source: branches/Scheduling/HeuristicLab.Problems.Scheduling/3.3/Encodings/JobSequenceMatrix/JSMDecoder.cs @ 6177

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2011 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 System.Text;
using HeuristicLab.Core;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Common;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;

namespace HeuristicLab.Problems.Scheduling.Encodings.JobSequenceMatrix {
  [Item("Job Sequencing Matrix Decoder", "Applies the GifflerThompson algorithm to create an active schedule from a JobSequencing Matrix.")]
  [StorableClass]
  public class JSMDecoder : JSSPDecoder<JSMEncoding>, IStochasticOperator {
    [StorableConstructor]
    protected JSMDecoder(bool deserializing) : base(deserializing) { }
    protected JSMDecoder(JSMDecoder original, Cloner cloner)
      : base(original, cloner) {
        this.resultingSchedule = cloner.Clone(original.resultingSchedule);
        this.decodingErrorPolicy = original.decodingErrorPolicy;
        this.forcingStrategy = original.forcingStrategy;
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new JSMDecoder(this, cloner);
    }

    public ILookupParameter<IRandom> RandomParameter {
      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
    }

    [Storable]
    private Schedule resultingSchedule;

    [Storable]
    private JSMDecodingErrorPolicyTypes decodingErrorPolicy = JSMDecodingErrorPolicyTypes.GuidedPolicy;

    [Storable]
    private JSMForcingStrategyTypes forcingStrategy = JSMForcingStrategyTypes.ShiftForcing;

    public JSMDecoder()
      : base() {
      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic manipulation operators."));
    }

    private ItemList<JSSPTask> GetEarliestNotScheduledTasks(ItemList<JSSPJob> jobs) {
      ItemList<JSSPTask> result = new ItemList<JSSPTask>();
      foreach (JSSPJob j in jobs) {
        foreach (JSSPTask t in j.Tasks) {
          if (!t.IsScheduled.Value) {
            result.Add(t);
            break;
          }
        }
      }
      return result;
    }
    private JSSPTask GetTaskWithMinimalEC(ItemList<JSSPTask> earliestTasksList) {
      DoubleValue minEct = new DoubleValue(Double.MaxValue);
      JSSPTask result = null;
      foreach (JSSPTask t in earliestTasksList) {
        DoubleValue ect = ComputeEarliestCompletionTime(t);
        if (ect.Value < minEct.Value) {
          result = t;
          minEct = ect;
        }
      }
      return result;
    }
    private ItemList<JSSPTask> GetConflictSetForTask(JSSPTask conflictedTask, ItemList<JSSPTask> earliestTasksList) {
      ItemList<JSSPTask> result = new ItemList<JSSPTask>();
      DoubleValue conflictedCompletionTime = ComputeEarliestCompletionTime(conflictedTask);
      result.Add(conflictedTask);
      foreach (JSSPTask t in earliestTasksList) {
        if (t.ResourceNr.Value == conflictedTask.ResourceNr.Value) {
          if (ComputeEarliestStartTime(t).Value < conflictedCompletionTime.Value)
            result.Add(t);
        }
      }
      return result;
    }
    private JSSPTask SelectTaskFromConflictSet(IntValue conflictedResource, ItemList<JSSPTask> conflictSet, ItemList<Permutation> jsm) {
      JSSPTask result = null;
      IntValue progressOnResource = new IntValue (resultingSchedule.Resources[conflictedResource.Value].Tasks.Count);

      if (progressOnResource.Value < jsm[conflictedResource.Value].Length) {
        IntValue solutionCandidateJobNr = new IntValue(jsm[conflictedResource.Value][progressOnResource.Value]);
        foreach (JSSPTask t in conflictSet) {
          if (t.Job.Index.Value == solutionCandidateJobNr.Value)
            result = t;
        }
      } else {
        return null;
      }

      //Repairing happens here
      if (result == null) {
        //Decoding Error Policy BEGIN
        //CHOOSE OTHER RESOLUTION FOR CONFLICT SET
        result = ApplyDecodingErrorPolicy(conflictSet);
        //result = conflictSet[RandomParameter.ActualValue.Next(conflictSet.Count - 1)];
        //Decoding Error Policy END


        //Determine index of new resolution
        int index = 0;
        while (index < jsm[conflictedResource.Value].Length && 
          jsm[conflictedResource.Value][index] != result.Job.Index.Value)
          index++;


        //Forcing Strategy BEGIN
        ApplyForcingStrategy(jsm, conflictedResource.Value, index, progressOnResource.Value, result.Job.Index.Value);
        
        //ForcingStrategy END
      }
      return result;
    }

    private void ApplyForcingStrategy(ItemList<Permutation> jsm, int conflictedResource, int newResolutionIndex, int progressOnResource, int newResolution) {
      //if (forcingStrategy == JSMForcingStrategyTypes.SwapForcing) {
        //SwapForcing
        jsm[conflictedResource][newResolutionIndex] = jsm[conflictedResource][progressOnResource];
        jsm[conflictedResource][progressOnResource] = newResolution;
      /*} else {
        //ShiftForcing

      } */
    }

    private JSSPTask ApplyDecodingErrorPolicy(ItemList<JSSPTask> conflictSet) {
      //if (decodingErrorPolicy == JSMDecodingErrorPolicyTypes.RandomPolicy) { 
        //Random
        return conflictSet[RandomParameter.ActualValue.Next(conflictSet.Count - 1)];
      /*} else {
        //Guided

      }    */
    }
    private DoubleValue ComputeEarliestStartTime(JSSPTask t) {
      Resource affectedResource = resultingSchedule.Resources[t.ResourceNr.Value];

      DoubleValue lastMachineEndTime = affectedResource.TotalDuration;
      DoubleValue previousJoboperationEndTime = new DoubleValue(double.MinValue);
      if (t.PreviousTask != null)
        previousJoboperationEndTime = t.PreviousTask.EndTime;

      return new DoubleValue(Math.Max(previousJoboperationEndTime.Value, lastMachineEndTime.Value));
    }
    private DoubleValue ComputeEarliestCompletionTime(JSSPTask t) {
      return new DoubleValue(ComputeEarliestStartTime(t).Value + t.Duration.Value);
    }
    private void AddTaskToSchedule(JSSPTask selectedTask) {
      Resource affectedResource = resultingSchedule.Resources[selectedTask.ResourceNr.Value];
      selectedTask.StartTime = ComputeEarliestStartTime(selectedTask);
      selectedTask.IsScheduled.Value = true;
      affectedResource.Tasks.Add(selectedTask);
    }

    public override Schedule CreateScheduleFromEncoding(JSMEncoding solution) {
      ItemList<Permutation> jobSequenceMatrix = solution.JobSequenceMatrix;

      resultingSchedule = new Schedule(new IntValue(Jobs[0].Tasks.Count));

      //Reset scheduled tasks in result
      foreach (JSSPJob j in Jobs) {
        foreach (JSSPTask t in j.Tasks) {
          t.IsScheduled.Value = false;
        }
      }

      //GT-Algorithm
      //STEP 0 - Compute a list of "earliest operations"
      ItemList<JSSPTask> earliestTasksList = GetEarliestNotScheduledTasks(Jobs);
      while (earliestTasksList.Count > 0) {
        //STEP 1 - Get earliest not scheduled operation with minimal earliest completing time
        JSSPTask minimal = GetTaskWithMinimalEC(earliestTasksList);

        //STEP 2 - Compute a conflict set of all operations that can be scheduled on the machine the previously selected operation runs on
        ItemList<JSSPTask> conflictSet = GetConflictSetForTask(minimal, earliestTasksList);

        //STEP 3 - Select an operation from the conflict set (various methods depending on how the algorithm should work..)
        JSSPTask selectedTask = SelectTaskFromConflictSet(minimal.ResourceNr, conflictSet, jobSequenceMatrix);

        //STEP 4 - Adding the selected operation to the current schedule
        AddTaskToSchedule(selectedTask);

        //STEP 5 - Back to STEP 1
        earliestTasksList = GetEarliestNotScheduledTasks(Jobs);
      }

      return resultingSchedule;
    }

    public override IOperation Apply() {
      return base.Apply();
    } 
  }
}