issue33.cs

// Authors: Johan Wessén
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

using Google.OrTools.ConstraintSolver;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System;

namespace FactoryProject {
public class Task {
  public int Id { get; private set; }
  public int TaskType { get; private set; }
  public int LocationId { get; private set; }
  public Dictionary<int,int> Durations { get; private set; }
  public int TaskPosition { get; private set; }

  public Task(int id, int taskType, int locationIndex, int taskPosition,
              Dictionary<int,int> durations) {
    Id = id;
    TaskType = taskType;
    LocationId = locationIndex;
    Durations = durations;
    TaskPosition = taskPosition;
  }

  public Task(int id, int taskType, int locationIndex, int taskPosition) {
    Id = id;
    TaskType = taskType;
    LocationId = locationIndex;
    TaskPosition = taskPosition;
    Durations = new Dictionary<int,int>();
  }
}

public class WorkLocation {
  public int Id { get; private set; }
  public int NbTasks {
    get { Debug.Assert(Tasks != null); return Tasks.Length; }
    set { Debug.Assert(Tasks == null); Tasks = new Task[value]; }
  }
  public Task[] Tasks { get; private set; }

  public WorkLocation(int index)
  {
    Id = index;
  }
}

public class Tool {
  public int Id { get; private set; }
  public HashSet<int> TaskTypes { get; set; }
  public int[,] TravellingTime { get; set; }
  public int InitialLocationId { get; set; }

  public Tool(int index, int initialLocation = 0) {
    Id = index;
    InitialLocationId = initialLocation;
    TaskTypes = new HashSet<int>();
  }

  public void AddTaskType(int t) {
    TaskTypes.Add(t);
  }

  public bool CanPerformTaskType(int taskType) {
    return TaskTypes.Contains(taskType);
  }
}

public class FactoryDescription {
  public Tool[] Tools { get; private set; }
  public WorkLocation[] Locations { get; private set; }

  public int NbWorkLocations { get { return Locations.Length; } }
  public int NbTools { get { return Tools.Length; } }

  public int NbTaskPerCycle { get; private set; }
  // TaskType go typically from 0 to 6. InspectionType indicates which
  // is the TaskType that correspond to Inspection.
  public int Inspection { get; private set; }
  // All the time within the schedule horizon in which the blast can start.
  public long[] InspectionStarts { get; private set; }

  public int Horizon { get; private set; }

  // horizon equal to 2 weeks (in minutes).
  public FactoryDescription(int nbTools, int nbLocations, int nbTaskPerCycle,
                            int horizon = 14*24*60) {
    Debug.Assert(nbTools > 0);
    Debug.Assert(nbLocations > 0);
    Debug.Assert(nbTaskPerCycle > 0);
    Debug.Assert(horizon > 0);
    NbTaskPerCycle = nbTaskPerCycle;
    Inspection = NbTaskPerCycle - 1;
    Tools = new Tool[nbTools];
    Horizon = horizon;
    for (int i = 0; i < nbTools; i++)
      Tools[i] = new Tool(i);
    Locations = new WorkLocation[nbLocations];
    for (int i = 0; i < nbLocations; i++)
      Locations[i] = new WorkLocation(i);

    InspectionStarts = new long[] { -1, 600, 1200, 1800, 2400, 2800 };
  }

  public Tool[] getToolPerTaskType(int taskType) {
    var elements = from tool in Tools
        where tool.CanPerformTaskType(taskType)
        select tool;
    return elements.ToArray();
  }

  public Task[] getFlatTaskList() {
    return (from location in Locations
            from task in location.Tasks
            orderby task.Id
            select task).ToArray();
  }

  public int[] getTaskTypes() {
    return (from location in Locations
            from task in location.Tasks
            select task.TaskType).Distinct().ToArray();
  }


  // TODO: This should be enhanced
  public void SanityCheck() {
    foreach (Tool tool in Tools) {
      Debug.Assert(tool.TravellingTime.GetLength(0) == NbWorkLocations);
      Debug.Assert(tool.TravellingTime.GetLength(1) == NbWorkLocations);
      for (int i = 0; i < NbWorkLocations; i++)
        Debug.Assert(tool.TravellingTime[i, i] == 0);
    }
  }
}

interface DataReader {
  FactoryDescription FetchData();
}

public class SmallSyntheticData : DataReader {

  public SmallSyntheticData() {}

  public FactoryDescription FetchData() {
    // deterministic seed for result reproducibility
    Random randomDuration = new Random(2);

    // FactoryDescription(nbTools, nblocations, nbTasks per cycle)
    FactoryDescription factoryDescription = new FactoryDescription(5, 4, 3);

    // Travelling time and distance are temporarily identical and they
    // are no different for different tools
    int[,] travellingTime = new int[factoryDescription.NbWorkLocations,
                                    factoryDescription.NbWorkLocations];
    for (int i = 0; i < travellingTime.GetLength(0); i++) {
      for (int j = 0; j < travellingTime.GetLength(1); j++) {
        if (i == j)
          travellingTime[i, j] = 0;
        else
            travellingTime[i, j] = (5 * Math.Abs(i - j)) * 10;
      }
    }

    factoryDescription.Tools[0].AddTaskType(0);
    factoryDescription.Tools[1].AddTaskType(0);
    factoryDescription.Tools[2].AddTaskType(1);
    factoryDescription.Tools[3].AddTaskType(1);
    factoryDescription.Tools[4].AddTaskType(2);
    factoryDescription.Tools[1].AddTaskType(1);

    foreach (Tool tool in factoryDescription.Tools)
      tool.TravellingTime = travellingTime;

    int c = 0;
    int nbCyclePerWorkLocation = 2;
    int[] boll = new int[100];
    for (int i = 0; i < factoryDescription.NbWorkLocations; i++) {
      factoryDescription.Locations[i].NbTasks =
          nbCyclePerWorkLocation * factoryDescription.NbTaskPerCycle;
      for (int j = 0; j < nbCyclePerWorkLocation; j++) {
        for (int k = 0; k < factoryDescription.NbTaskPerCycle; k++) {
          Task t = new Task(c, k, i, k + j * factoryDescription.NbTaskPerCycle);

          // Filling in tool-dependent durations
          Tool[] compatibleTools = factoryDescription.getToolPerTaskType(k);
          foreach (Tool tool in compatibleTools) {
            boll[c] = randomDuration.Next(13, 17) * 10; ;
            t.Durations[tool.Id] = boll[c];
          }
          factoryDescription.Locations[i].Tasks[t.TaskPosition] = t;
          c++;
        }
      }
    }

    factoryDescription.SanityCheck();
    return factoryDescription;
  }
}

public class RandomSelectToolHeuristic : NetDecisionBuilder {

  private FactoryScheduling factoryScheduling;
  private Random rnd;

  public RandomSelectToolHeuristic(FactoryScheduling factoryScheduling,
                                   int seed) {
    this.factoryScheduling = factoryScheduling;
    // deterministic seed for result reproducibility
    this.rnd = new Random(seed);
  }

  public override Decision Next(Solver solver) {
    foreach (IntVar var in factoryScheduling.SelectedTool) {
      if (!var.Bound()) {
        int min = (int) var.Min();
        int max = (int) var.Max();
        int rndVal = rnd.Next(min, max + 1);
        while (!var.Contains(rndVal))
          rndVal = rnd.Next(min, max + 1);
        return solver.MakeAssignVariableValue(var, rndVal);
      }
    }
    return null;
  }
}

class TaskAlternative {
  public Task Task { get; private set; }
  public IntVar ToolVar { get; set; }
  public List<IntervalVar> Intervals { get; private set; }

  public TaskAlternative(Task t) {
    Task = t;
    Intervals = new List<IntervalVar>();
  }
}

public class FactoryScheduling {
  private FactoryDescription factoryData;
  private Solver solver;

  private Task[] tasks;
  private int[] taskTypes;

  /* Flat list of all the tasks */
  private TaskAlternative[] taskStructures;

  /* Task per WorkLocation: location2Task[d][i]: the i-th task of the
   * d-th location */
  private TaskAlternative[][] location2Task;

  /* Task per Tool: tool2Task[t][i]: the i-th task of the t-th tool.
     Note that it does NOT imply that the it will be the i-th
     executed. In other words, it should be considered as an unordered
     set.  Furthermore, tool2Task[t][i] can also be *unperformed* */
  private List<IntervalVar>[] tool2Task;

  /* All the transition times for the tools.
     tool2TransitionTimes[t][i]: the transition time of the t-th tool
     from the i-th task to the next */
  private List<IntVar>[] tool2TransitionTimes;

  /* Map between the interval var of a tool to its related task id.
     toolIntervalVar2TaskId[t][k] = i: in the t-th tool, the k-th
     interval var correspond to tasks[i] */
  private List<int>[] toolIntervalVar2TaskId;

  /* Tools per task type: taskType2Tool[tt][t]: the t-th tool capable
   * of doing the tt-th task type */
  private List<Tool>[] taskType2Tool;

  /* For each task which tools is performed upon */
  private List<IntVar> selectedTool;
  public List<IntVar> SelectedTool { get { return selectedTool; } }

  /* Sequence of task for each tool */
  private SequenceVar[] allToolSequences;
  public SequenceVar[] AllToolSequences { get { return allToolSequences; } }


  /* Makespan var */
  private IntVar makespan;

  /* Objective */
  private OptimizeVar objective;

  /* maximum horizon */
  private int horizon;

  /* Start & End times of IntervalVars*/
  IntVar[][] startingTimes;
  IntVar[][] endTimes;


  public FactoryScheduling(FactoryDescription data) {
    factoryData = data;
  }

  private void Init() {
    horizon = factoryData.Horizon;
    solver = new Solver("Factory Scheduling");
    tasks = factoryData.getFlatTaskList();
    taskTypes = factoryData.getTaskTypes();
    taskStructures = new TaskAlternative[tasks.Length];
    location2Task = new TaskAlternative[factoryData.NbWorkLocations][];
    tool2Task = new List<IntervalVar>[factoryData.NbTools];
    toolIntervalVar2TaskId = new List<int>[factoryData.NbTools];
    tool2TransitionTimes = new List<IntVar>[factoryData.NbTools];

    taskType2Tool = new List<Tool>[taskTypes.Length];
    selectedTool = new List<IntVar>();
    for (int tt = 0; tt < taskTypes.Length; tt++)
      taskType2Tool[tt] = new List<Tool>();

    foreach (Tool tool in factoryData.Tools)
      foreach (int taskType in tool.TaskTypes)
        taskType2Tool[taskType].Add(tool);
    for (int d = 0; d < factoryData.NbWorkLocations; d++)
      location2Task[d] = new TaskAlternative[factoryData.Locations[d].NbTasks];
    for (int t = 0; t < factoryData.NbTools; t++) {
      tool2Task[t] = new List<IntervalVar>();
      toolIntervalVar2TaskId[t] = new List<int>();
      tool2TransitionTimes[t] = new List<IntVar>();
    }

    allToolSequences = new SequenceVar[factoryData.NbTools - 1];

    startingTimes = new IntVar[factoryData.NbTools - 1][];
    endTimes = new IntVar[factoryData.NbTools - 1][];


  }

  private void PostTransitionTimeConstraints(
      int t, bool postTransitionsConstraint = true) {
    Tool tool = factoryData.Tools[t];
    //if it is a inspection, we make sure there are no transitiontimes
    if (tool.CanPerformTaskType(factoryData.Inspection))
      tool2TransitionTimes[t].Add(null);
    else {
      int[,] tt = tool.TravellingTime;

      SequenceVar seq = allToolSequences[t];
      long s = seq.Size();
      IntVar[] nextLocation = new IntVar[s + 1];

      // The seq.Next(i) represents the task performed after the i-th
      // task in the sequence seq.Next(0) represents the first task
      // performed for extracting travelling times we need to get the
      // related location In case a task is not performed (seq.Next(i)
      // == i), i.e. it's pointing to itself The last performed task
      // (or pre-start task, if no tasks are performed) will have
      // seq.Next(i) == s + 1 therefore we add a virtual location
      // whose travelling time is equal to 0
      //
      // NOTE: The index of a SequenceVar are 0..n, but the domain
      // range is 1..(n+1), this is due to that the start node = 0 is
      // a dummy node, and the node where seq.Next(i) == n+1 is the
      // end node

      // Extra elements for the unreachable start node (0), and the
      // end node whose next task takes place in a virtual location
      int[] taskIndex2locationId = new int[s + 2];
      taskIndex2locationId[0] = -10;
      for (int i = 0; i < s; i++)
        taskIndex2locationId[i+1] =
            tasks[toolIntervalVar2TaskId[t][i]].LocationId;

      // this is the virtual location for unperformed tasks
      taskIndex2locationId[s + 1] = factoryData.NbWorkLocations;

      // Build the travelling time matrix with the additional virtual location
      int[][] ttWithVirtualLocation =
          new int[factoryData.NbWorkLocations + 1][];
      for (int d1 = 0; d1 < ttWithVirtualLocation.Length; d1++) {
        ttWithVirtualLocation[d1] = new int[factoryData.NbWorkLocations + 1];
        for (int d2 = 0; d2 < ttWithVirtualLocation.Length; d2++)
          if (d1 == factoryData.NbWorkLocations) {
            ttWithVirtualLocation[d1][d2] = 0;
          } else {
            ttWithVirtualLocation[d1][d2] =
                (d2 == factoryData.NbWorkLocations) ? 0 : tt[d1, d2];
        }
      }

      for (int i = 0; i < nextLocation.Length; i++) {
        // this is the next-location associated with the i-th task
        nextLocation[i] =
            solver.MakeElement(taskIndex2locationId, seq.Next(i )).Var();

        int d = (i == 0) ? tool.InitialLocationId
                         : tasks[toolIntervalVar2TaskId[t][i - 1]].LocationId;
        if (i == 0) {
          // To be changed - right now we don't have meaningful indata
          // of previous location Ugly way of setting initial travel
          // time to = 0, as this is how we find common grounds
          // between benchmark algorithm and this
          tool2TransitionTimes[t].Add(solver.MakeElement(
              new int[ttWithVirtualLocation[d].Length], nextLocation[i]).Var());
        } else {
          tool2TransitionTimes[t].Add(solver.MakeElement(
              ttWithVirtualLocation[d], nextLocation[i]).Var());
        }
      }

      // Extra elements for the unreachable start node (0), and the
      // end node whose next task takes place in a virtual location
      startingTimes[t] = new IntVar[s + 2];
      endTimes[t] = new IntVar[s + 2];

      startingTimes[t][0] = solver.MakeIntConst(0);
      // Tbd: Set this endtime to the estimated time of finishing
      // previous task for the current tool
      endTimes[t][0] = solver.MakeIntConst(0);

      for (int i = 0; i < s; i++) {
        startingTimes[t][i + 1] = tool2Task[t][i].SafeStartExpr(-1).Var();
        endTimes[t][i + 1] = tool2Task[t][i].SafeEndExpr(-1).Var();
      }
      startingTimes[t][s + 1] = solver.MakeIntConst(factoryData.Horizon);
      endTimes[t][s + 1] = solver.MakeIntConst(factoryData.Horizon);


      // Enforce (or not) that each task is separated by the
      // transition time to the next task
      for (int i = 0; i < nextLocation.Length; i++) {
        IntVar nextStart =
            solver.MakeElement(startingTimes[t], seq.Next(i).Var()).Var();
        if(postTransitionsConstraint)
          solver.Add(endTimes[t][i] + tool2TransitionTimes[t][i] <= nextStart);
      }
    }
  }

  private void Model() {
    /* Building basic task data structures */
    for (int i = 0; i < tasks.Length; i++) {

      /* Create a new set of possible IntervalVars & IntVar to decide
       * which one (and only 1) is performed */
      taskStructures[i] = new TaskAlternative(tasks[i]);

      /* Container to use when posting constraints */
      location2Task[tasks[i].LocationId][tasks[i].TaskPosition] =
          taskStructures[i];

      /* Get task type */
      int taskType = tasks[i].TaskType;

      /* Possible tool for this task */
      List<Tool> tools = taskType2Tool[taskType];
      bool optional = tools.Count > 1;

      /* List of boolean variables. If performedOnTool[t] == true then
       * the task is performed on tool t */
      List<IntVar> performedOnTool = new List<IntVar>();
      for (int t = 0; t < tools.Count; t++) {
        /* Creating an IntervalVar. If tools.Count > 1 the intervalVar
         * is *OPTIONAL* */
        int toolId = tools[t].Id;
        Debug.Assert(tasks[i].Durations.ContainsKey(toolId));
        int duration = tasks[i].Durations[toolId];
        string name = "J " + tasks[i].Id + " [" + toolId + "]";

        IntervalVar intervalVar;
        if (taskType == factoryData.Inspection) {
          /* We set a 0 time if the task is an inspection */
          duration = 0;
          intervalVar = solver.MakeFixedDurationIntervalVar(
              0, horizon, duration, optional, name);
          IntVar start = intervalVar.SafeStartExpr(-1).Var();

          intervalVar.SafeStartExpr(-1).Var().SetValues(
              factoryData.InspectionStarts);
        } else {
          intervalVar = solver.MakeFixedDurationIntervalVar(
              0, horizon, duration, optional, name);
        }

        taskStructures[i].Intervals.Add(intervalVar);
        tool2Task[toolId].Add(intervalVar);
        toolIntervalVar2TaskId[toolId].Add(i);

        /* Collecting all the bool vars, even if they are optional */
        performedOnTool.Add(intervalVar.PerformedExpr().Var());
      }

      /* Linking the bool var to a single integer variable: */
      /* if alternativeToolVar == t <=> performedOnTool[t] == true */
      string alternativeName = "J " + tasks[i].Id;
      IntVar alternativeToolVar =
          solver.MakeIntVar(0, tools.Count - 1, alternativeName);
      taskStructures[i].ToolVar = alternativeToolVar;

      solver.Add(
          solver.MakeMapDomain(alternativeToolVar, performedOnTool.ToArray()));
      Debug.Assert(
          performedOnTool.ToArray().Length == alternativeToolVar.Max()+1);

      selectedTool.Add(alternativeToolVar);
    }

    /* Creates precedences on a work Location in order to enforce a
     * fully ordered set within the same location
     */
    for (int d = 0; d < location2Task.Length; d++) {
      for (int i = 0; i < location2Task[d].Length - 1; i++) {
        TaskAlternative task1 = location2Task[d][i];
        TaskAlternative task2 = location2Task[d][i + 1];
        /* task1 must end before task2 starts */
        /* Adding precedence for each possible alternative pair */
        for (int t1 = 0; t1 < task1.Intervals.Count(); t1++) {
          IntervalVar task1Alternative = task1.Intervals[t1];
          for (int t2 = 0; t2 < task2.Intervals.Count(); t2++){
            IntervalVar task2Alternative = task2.Intervals[t2];
            Constraint precedence = solver.MakeIntervalVarRelation(
                task2Alternative, Solver.STARTS_AFTER_END, task1Alternative);
            solver.Add(precedence);
          }
        }
      }
    }

    /* Adds disjunctive constraints on unary resources, and creates
     * sequence variables. */
    for (int t = 0; t < factoryData.NbTools; t++) {
      string name = "Tool " + t;

      if (!factoryData.Tools[t].CanPerformTaskType(factoryData.Inspection)) {
        DisjunctiveConstraint ct =
            solver.MakeDisjunctiveConstraint(tool2Task[t].ToArray(), name);
        solver.Add(ct);
        allToolSequences[t] = ct.SequenceVar();
      }
      PostTransitionTimeConstraints(t, true);
    }


    /* Collecting all tasks end for makespan objective function */
    List<IntVar> intervalEnds = new List<IntVar>();
    for (int i = 0; i < tasks.Length; i++)
      foreach (IntervalVar var in taskStructures[i].Intervals)
        intervalEnds.Add(var.SafeEndExpr(-1).Var());


    /* Objective: minimize the makespan (maximum end times of all tasks) */
    makespan = solver.MakeMax(intervalEnds.ToArray()).Var();
    objective = solver.MakeMinimize(makespan, 1);
  }

  private void Search(){
    int seed = 2; //This is a good seed to show the crash

    /* Assigning first tools */
    DecisionBuilder myToolAssignmentPhase =
        new RandomSelectToolHeuristic(this, seed);

    /* Ranking of the tools */
    DecisionBuilder sequencingPhase =
        solver.MakePhase(allToolSequences, Solver.SEQUENCE_DEFAULT);

    /* Then fixing time of tasks as early as possible */
    DecisionBuilder timingPhase = solver.MakePhase(
        makespan, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

    /* Overall phase */
    DecisionBuilder mainPhase =
        solver.Compose(myToolAssignmentPhase, sequencingPhase, timingPhase);

    /* Logging */
    const int logFrequency = 1000000;
    SearchMonitor searchLog = solver.MakeSearchLog(logFrequency, objective);

    /* Restarts */
    SearchMonitor searchRestart = solver.MakeLubyRestart(100);

    /* Search Limit in ms */
    SearchLimit limit = solver.MakeTimeLimit(180*1000);

    /* Collecting best solution */
    SolutionCollector collector = solver.MakeLastSolutionCollector();
    collector.AddObjective(makespan);

    //collector.Add( pile.ToArray() );
    solver.NewSearch(mainPhase, searchLog, searchRestart, objective, limit);
    while (solver.NextSolution()){
      Console.WriteLine("MAKESPAN: " + makespan.Value());
    }
  }

  public void Solve() {
    Init();
    Model();
    Search();
  }

  public static void Main(string[] args) {
    FactoryScheduling scheduling =
        new FactoryScheduling(new SmallSyntheticData().FetchData());
    scheduling.Solve();
  }
}
}  // namespace FactoryProject