JobshopFt06Sat.cs

// Copyright 2010-2018 Google LLC
// 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 System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Sat;

public class JobshopFt06Sat
{

  public struct Task
  {
    public Task(IntVar s, IntVar e, IntervalVar i)
    {
      start = s;
      end = e;
      interval = i;
    }

    public IntVar start;
    public IntVar end;
    public IntervalVar interval;
  }

  static void Main()
  {
    int[,] durations = new int[,] { {1, 3, 6, 7, 3, 6},
                                    {8, 5, 10, 10, 10, 4},
                                    {5, 4, 8, 9, 1, 7},
                                    {5, 5, 5, 3, 8, 9},
                                    {9, 3, 5, 4, 3, 1},
                                    {3, 3, 9, 10, 4, 1} };
    int[,] machines = new int[,] { {2, 0, 1, 3, 5, 4},
                                   {1, 2, 4, 5, 0, 3},
                                   {2, 3, 5, 0, 1, 4},
                                   {1, 0, 2, 3, 4, 5},
                                   {2, 1, 4, 5, 0, 3},
                                   {1, 3, 5, 0, 4, 2} };

    int num_jobs = durations.GetLength(0);
    int num_machines = durations.GetLength(1);
    var all_jobs = Enumerable.Range(0, num_jobs);
    var all_machines = Enumerable.Range(0, num_machines);

    int horizon = 0;
    foreach (int j in all_jobs)
    {
      foreach (int m in all_machines)
      {
        horizon += durations[j, m];
      }
    }


    // Creates the model.
    CpModel model = new CpModel();

    // Creates jobs.
    Task[,] all_tasks = new Task[num_jobs, num_machines];
    foreach (int j in all_jobs)
    {
      foreach (int m in all_machines)
      {
        IntVar start_var = model.NewIntVar(
            0, horizon, String.Format("start_{0}_{1}", j, m));
        int duration = durations[j, m];
        IntVar end_var = model.NewIntVar(
            0, horizon, String.Format("end_{0}_{1}", j, m));
        IntervalVar interval_var = model.NewIntervalVar(
            start_var, duration, end_var,
            String.Format("interval_{0}_{1}", j, m));
        all_tasks[j, m] = new Task(start_var, end_var, interval_var);
      }
    }

    // Create disjuctive constraints.
    List<IntervalVar>[] machine_to_jobs = new List<IntervalVar>[num_machines];
    foreach (int m in all_machines)
    {
      machine_to_jobs[m] = new List<IntervalVar>();
    }
    foreach (int j in all_jobs)
    {
      foreach (int m in all_machines)
      {
        machine_to_jobs[machines[j, m]].Add(all_tasks[j, m].interval);
      }
    }
    foreach (int m in all_machines)
    {
      model.AddNoOverlap(machine_to_jobs[m]);
    }

    // Precedences inside a job.
    foreach (int j in all_jobs)
    {
      for (int k = 0; k < num_machines - 1; ++k)
      {
        model.Add(all_tasks[j, k + 1].start >= all_tasks[j, k].end);
      }
    }

    // Makespan objective.
    IntVar[] all_ends = new IntVar[num_jobs];
    foreach (int j in all_jobs)
    {
      all_ends[j] = all_tasks[j, num_machines - 1].end;
    }
    IntVar makespan = model.NewIntVar(0, horizon, "makespan");
    model.AddMaxEquality(makespan, all_ends);
    model.Minimize(makespan);

    Console.WriteLine(model.ModelStats());

    // Creates the solver and solve.
    CpSolver solver = new CpSolver();
    // Display a few solutions picked at random.
    solver.Solve(model);

    // Statistics.
    Console.WriteLine(solver.ResponseStats());
  }
}