source: branches/Scheduling/HeuristicLab.Problems.Scheduling/3.3/Encodings/PriorityRulesVector/PRVDecoder.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.PriorityRulesVector {
  [Item("Job Sequencing Matrix Decoder", "Applies the GifflerThompson algorithm to create an active schedule from a JobSequencing Matrix.")]
  [StorableClass]
  public class PRVDecoder : JSSPDecoder<PRVEncoding>, IStochasticOperator {
    [StorableConstructor]
    protected PRVDecoder(bool deserializing) : base(deserializing) { }
    protected PRVDecoder(PRVDecoder original, Cloner cloner)
      : base(original, cloner) {
        this.resultingSchedule = cloner.Clone(original.resultingSchedule);
    }
    public override IDeepCloneable Clone(Cloner cloner) {
      return new PRVDecoder(this, cloner);
    }

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

    [Storable]
    private Schedule resultingSchedule;

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

    #region Priority Rules
    //smallest number of remaining tasks
    private JSSPTask FILORule(ItemList<JSSPTask> tasks) {
      JSSPTask currentResult = tasks[tasks.Count-1];
      return currentResult;
    }

    //earliest start time
    private JSSPTask ESTRule(ItemList<JSSPTask> tasks) {
      JSSPTask currentResult = tasks[0];
      double currentEST = double.MaxValue;
      foreach (JSSPTask t in tasks) {
        double est = ComputeEarliestStartTime(t).Value;
        if (est < currentEST) {
          currentEST = est;
          currentResult = t;
        }
      }
      return currentResult;
    }
   
    //shortest processingtime
    private JSSPTask SPTRule(ItemList<JSSPTask> tasks) {
      JSSPTask currentResult = tasks[0];
      foreach (JSSPTask t in tasks) {
        if (t.Duration.Value < currentResult.Duration.Value)
          currentResult = t;
      }
      return currentResult;
    }

    //longest processing time    
    private JSSPTask LPTRule(ItemList<JSSPTask> tasks) {
      JSSPTask currentResult = tasks[0];
      foreach (JSSPTask t in tasks) {
        if (t.Duration.Value > currentResult.Duration.Value)
          currentResult = t;
      }
      return currentResult;
    } 

    //most work remaining
    private JSSPTask MWRRule(ItemList<JSSPTask> tasks) {
      JSSPTask currentResult = tasks[0];
      double currentLargestRemainingProcessingTime = 0;
      foreach (JSSPTask t in tasks) {
        double remainingProcessingTime = 0;
        foreach (JSSPTask jt in t.Job.Tasks) {
          if (!jt.IsScheduled.Value)
            remainingProcessingTime += jt.Duration.Value;
        }
        if (remainingProcessingTime > currentLargestRemainingProcessingTime) {
          currentLargestRemainingProcessingTime = remainingProcessingTime;
          currentResult = t;
        }
      }
      return currentResult;
    }
   
    //least work remaining
    private JSSPTask LWRRule(ItemList<JSSPTask> tasks) {
      JSSPTask currentResult = tasks[0];
      double currentSmallestRemainingProcessingTime = double.MaxValue;
      foreach (JSSPTask t in tasks) {
        double remainingProcessingTime = 0;
        foreach (JSSPTask jt in t.Job.Tasks) {
          if (!jt.IsScheduled.Value)
            remainingProcessingTime += jt.Duration.Value;
        }
        if (remainingProcessingTime < currentSmallestRemainingProcessingTime) {
          currentSmallestRemainingProcessingTime = remainingProcessingTime;
          currentResult = t;
        }
      }
      return currentResult;
    }

    //most operations remaining
    private JSSPTask MORRule(ItemList<JSSPTask> tasks) {
      JSSPTask currentResult = tasks[0];
      int currentLargestNrOfRemainingTasks = 0;
      foreach (JSSPTask t in tasks) {
        int nrOfRemainingTasks = 0;
        foreach (JSSPTask jt in t.Job.Tasks) {
          if (!jt.IsScheduled.Value)
            nrOfRemainingTasks++;
        }
        if (currentLargestNrOfRemainingTasks < nrOfRemainingTasks) {
          currentLargestNrOfRemainingTasks = nrOfRemainingTasks;
          currentResult = t;
        }
      }
      return currentResult;
    }
    
    //least operationsremaining
    private JSSPTask LORRule(ItemList<JSSPTask> tasks) {
      JSSPTask currentResult = tasks[0];
      int currentSmallestNrOfRemainingTasks = int.MaxValue;
      foreach (JSSPTask t in tasks) {
        int nrOfRemainingTasks = 0;
        foreach (JSSPTask jt in t.Job.Tasks) {
          if (!jt.IsScheduled.Value)
            nrOfRemainingTasks++;
        }
        if (currentSmallestNrOfRemainingTasks > nrOfRemainingTasks) {
          currentSmallestNrOfRemainingTasks = nrOfRemainingTasks;
          currentResult = t;
        }
      }
      return currentResult;
    }
                
    //first operation in Queue
    private JSSPTask FIFORule(ItemList<JSSPTask> tasks) {
      JSSPTask currentResult = tasks[0];
      return currentResult;
    }
                  
    //random
    private JSSPTask RandomRule(ItemList<JSSPTask> tasks) {
      JSSPTask currentResult = tasks[RandomParameter.ActualValue.Next(tasks.Count)];
      return currentResult;
    }

    #endregion

    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(ItemList<JSSPTask> conflictSet, int ruleIndex, int nrOfRules) {
      if (conflictSet.Count == 1)
        return conflictSet[0];
      
      ruleIndex = ruleIndex % nrOfRules;
      switch (ruleIndex) {
        case 0: return FILORule(conflictSet);
        case 1: return ESTRule(conflictSet);
        case 2: return SPTRule(conflictSet);
        case 3: return LPTRule(conflictSet);
        case 4: return MWRRule(conflictSet);
        case 5: return LWRRule(conflictSet);
        case 6: return MORRule(conflictSet);
        case 7: return LORRule(conflictSet);
        case 8: return FIFORule(conflictSet);
        case 9: return RandomRule(conflictSet);
        default: return RandomRule(conflictSet);
      }  
    }
    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(PRVEncoding solution) {
      PRVEncoding priorityRulesVector = solution;

      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);
      int currentDecisionIndex = 0;
      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(conflictSet, priorityRulesVector [currentDecisionIndex++], solution.NrOfRules.Value);

        //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();
    } 
  }
}