취업정보 문제

일반적인 일정 예약 문제 중 하나는 여러 개의 채용정보가 있는 채용정보 매장입니다. 여러 머신에서 처리됩니다

각 작업은 주어진 일정에서 수행되어야 하는 일련의 작업으로 구성됩니다. 각 태스크는 특정 머신에서 처리되어야 합니다. 예를 들어 단일 소비자 품목의 제조가 될 수 있습니다(예: 자동차입니다. 문제는 작업 시간을 최소화하여 일정의 length: 모든 작업이 완료되는 데 걸리는 시간입니다.

구인/구직 문제에는 몇 가지 제약조건이 있습니다.

• 작업의 이전 태스크가 시작될 때까지 작업에 대한 태스크를 시작할 수 없습니다. 완료되었습니다.
• 머신은 한 번에 하나의 태스크만 처리할 수 있습니다.
• 작업은 시작되면 완료될 때까지 실행되어야 합니다.

문제 예시

다음은 각 작업에 라벨이 지정되는 구직서 문제의 간단한 예입니다. 숫자 쌍 (m, p)으로 표현되며 여기서 m은 태스크가 수행된 머신의 수입니다. p는 작업의 처리 시간입니다. 즉, 시간이 오래 걸릴 수 있다는 사실을 알고 있을 겁니다 (작업 및 머신의 수는 0부터 시작합니다.)

• 작업 0 = [(0, 3), (1, 2), (2, 2)]
• 작업 1 = [(0, 2), (2, 1), (1, 4)]
• 작업 2 = [(1, 4), (2, 3)]

이 예에서 작업 0에는 3개의 태스크가 있습니다. 첫 번째 값(0, 3)은 3개의 단위로 실행합니다 두 번째 (1, 2)는 2단위의 머신 1과 같은 식입니다. 총 8개의 태스크가 있습니다.

문제의 해결책

구직 문제를 해결하는 방법은 각자 시작 시간을 할당하는 것입니다. 태스크가 수행되어야 합니다. 아래 다이어그램은 이 문제에 대한 한 가지 가능한 해결 방법을 보여줍니다.

각 작업의 태스크가 겹치지 않는 시간으로 예약되어 있는지 확인할 수 있습니다. 간격이 될 수 있습니다.

이 솔루션의 길이는 12로, 세 개의 작업이 모두 완료됩니다. 하지만 아래에서 볼 수 있듯이 이 방법은 있습니다.

문제의 변수 및 제약 조건

이 섹션에서는 있습니다. 먼저 task(i, j)가 작업 i의 시퀀스에서 j번째 작업을 나타낸다고 가정합니다. 대상 예를 들어 task(0, 2)는 작업 0의 두 번째 작업을 나타내며 문제 설명에 있는 (1, 2) 쌍입니다.

다음으로 t_{i, j}를 task(i, j)의 시작 시간으로 정의합니다. 이 t_i, j는 취업 매장 문제의 변수입니다. 조건을 충족하는 해당 변수의 값을 문제를 해결할 수 있습니다

채용정보 매장 문제에는 두 가지 유형의 제약 조건이 있습니다.

• 선행 제약 조건 — 특정 우선순위에 해당하는 경우 두 개의 연속된 작업을 실행하는 경우 첫 번째 작업은 시작할 수 있습니다 예를 들어 task(0, 2) 및 task(0, 3)는 다음과 같습니다. 작업을 수행합니다 task(0, 2)의 처리 시간이 2이므로 task(0, 3)은 작업 2의 시작 시간 이후 2단위 이상의 시간 단위여야 합니다. (작업 2가 문에 페인트를 칠하는 것으로, 페인트가 페인트를 칠하려면 2시간이 dry.) 따라서 다음과 같은 제약 조건이 적용됩니다. <ph type="x-smartling-placeholder">
  </ph>
  • t_{0, 2} + 2 <= t_{0, 3}
• 중복 제약 조건 없음 — 중복 제약 조건 없이 두 가지 작업을 동시에 수행할 수 없습니다. 예를 들어 작업(0, 2)과 작업(2, 1)은 모두 머신 1에서 처리됩니다. 처리 시간이 각각 2와 4이므로 다음 중 하나입니다. 제약 조건은 다음과 같아야 합니다. <ph type="x-smartling-placeholder">
  </ph>
  • t_{0, 2} + 2 <= t_{2, 1} (task(0, 2)이 예약된 경우) task(2, 1) 이전) 또는
  • t_{2, 1} + 4 <= t_{0, 2} (task(2, 1)가 예약된 경우) (task(0, 2) 이전)

문제의 목표

구직 사항의 목표는 makespan을 최소화하는 것입니다. 가장 이른 시작 시간부터 가장 늦은 종료 시간까지의 기간을 의미합니다.

프로그램 솔루션

다음 섹션에서는 문제를 해결하는 프로그램의 주요 요소를 설명합니다. 구직 문제를 겪을 수 있습니다.

라이브러리 가져오기

다음 코드는 필요한 라이브러리를 가져옵니다.

Python

import collections
from ortools.sat.python import cp_model

C++

#include <stdlib.h>

#include <algorithm>
#include <cstdint>
#include <map>
#include <numeric>
#include <string>
#include <tuple>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"

자바

import static java.lang.Math.max;

import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.IntervalVar;
import com.google.ortools.sat.LinearExpr;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.IntStream;

C#

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Sat;

데이터 정의

다음으로 프로그램은 문제에 관한 데이터를 정의합니다.

Python

jobs_data = [  # task = (machine_id, processing_time).
    [(0, 3), (1, 2), (2, 2)],  # Job0
    [(0, 2), (2, 1), (1, 4)],  # Job1
    [(1, 4), (2, 3)],  # Job2
]

machines_count = 1 + max(task[0] for job in jobs_data for task in job)
all_machines = range(machines_count)
# Computes horizon dynamically as the sum of all durations.
horizon = sum(task[1] for job in jobs_data for task in job)

C++

using Task = std::tuple<int64_t, int64_t>;  // (machine_id, processing_time)
using Job = std::vector<Task>;
std::vector<Job> jobs_data = {
    {{0, 3}, {1, 2}, {2, 2}},  // Job_0: Task_0 Task_1 Task_2
    {{0, 2}, {2, 1}, {1, 4}},  // Job_1: Task_0 Task_1 Task_2
    {{1, 4}, {2, 3}},          // Job_2: Task_0 Task_1
};

int64_t num_machines = 0;
for (const auto& job : jobs_data) {
  for (const auto& [machine, _] : job) {
    num_machines = std::max(num_machines, 1 + machine);
  }
}

std::vector<int> all_machines(num_machines);
std::iota(all_machines.begin(), all_machines.end(), 0);

// Computes horizon dynamically as the sum of all durations.
int64_t horizon = 0;
for (const auto& job : jobs_data) {
  for (const auto& [_, time] : job) {
    horizon += time;
  }
}

자바

class Task {
  int machine;
  int duration;
  Task(int machine, int duration) {
    this.machine = machine;
    this.duration = duration;
  }
}

final List<List<Task>> allJobs =
    Arrays.asList(Arrays.asList(new Task(0, 3), new Task(1, 2), new Task(2, 2)), // Job0
        Arrays.asList(new Task(0, 2), new Task(2, 1), new Task(1, 4)), // Job1
        Arrays.asList(new Task(1, 4), new Task(2, 3)) // Job2
    );

int numMachines = 1;
for (List<Task> job : allJobs) {
  for (Task task : job) {
    numMachines = max(numMachines, 1 + task.machine);
  }
}
final int[] allMachines = IntStream.range(0, numMachines).toArray();

// Computes horizon dynamically as the sum of all durations.
int horizon = 0;
for (List<Task> job : allJobs) {
  for (Task task : job) {
    horizon += task.duration;
  }
}

C#

var allJobs =
    new[] {
        new[] {
            // job0
            new { machine = 0, duration = 3 }, // task0
            new { machine = 1, duration = 2 }, // task1
            new { machine = 2, duration = 2 }, // task2
        }
            .ToList(),
        new[] {
            // job1
            new { machine = 0, duration = 2 }, // task0
            new { machine = 2, duration = 1 }, // task1
            new { machine = 1, duration = 4 }, // task2
        }
            .ToList(),
        new[] {
            // job2
            new { machine = 1, duration = 4 }, // task0
            new { machine = 2, duration = 3 }, // task1
        }
            .ToList(),
    }
        .ToList();

int numMachines = 0;
foreach (var job in allJobs)
{
    foreach (var task in job)
    {
        numMachines = Math.Max(numMachines, 1 + task.machine);
    }
}
int[] allMachines = Enumerable.Range(0, numMachines).ToArray();

// Computes horizon dynamically as the sum of all durations.
int horizon = 0;
foreach (var job in allJobs)
{
    foreach (var task in job)
    {
        horizon += task.duration;
    }
}

모델 선언

다음 코드는 문제에 관한 모델을 선언합니다.

Python

model = cp_model.CpModel()

C++

CpModelBuilder cp_model;

자바

CpModel model = new CpModel();

C#

CpModel model = new CpModel();

변수 정의

다음 코드는 문제의 변수를 정의합니다.

Python

# Named tuple to store information about created variables.
task_type = collections.namedtuple("task_type", "start end interval")
# Named tuple to manipulate solution information.
assigned_task_type = collections.namedtuple(
    "assigned_task_type", "start job index duration"
)

# Creates job intervals and add to the corresponding machine lists.
all_tasks = {}
machine_to_intervals = collections.defaultdict(list)

for job_id, job in enumerate(jobs_data):
    for task_id, task in enumerate(job):
        machine, duration = task
        suffix = f"_{job_id}_{task_id}"
        start_var = model.new_int_var(0, horizon, "start" + suffix)
        end_var = model.new_int_var(0, horizon, "end" + suffix)
        interval_var = model.new_interval_var(
            start_var, duration, end_var, "interval" + suffix
        )
        all_tasks[job_id, task_id] = task_type(
            start=start_var, end=end_var, interval=interval_var
        )
        machine_to_intervals[machine].append(interval_var)

C++

struct TaskType {
  IntVar start;
  IntVar end;
  IntervalVar interval;
};

using TaskID = std::tuple<int, int>;  // (job_id, task_id)
std::map<TaskID, TaskType> all_tasks;
std::map<int64_t, std::vector<IntervalVar>> machine_to_intervals;
for (int job_id = 0; job_id < jobs_data.size(); ++job_id) {
  const auto& job = jobs_data[job_id];
  for (int task_id = 0; task_id < job.size(); ++task_id) {
    const auto [machine, duration] = job[task_id];
    std::string suffix = absl::StrFormat("_%d_%d", job_id, task_id);
    IntVar start = cp_model.NewIntVar({0, horizon})
                       .WithName(std::string("start") + suffix);
    IntVar end = cp_model.NewIntVar({0, horizon})
                     .WithName(std::string("end") + suffix);
    IntervalVar interval = cp_model.NewIntervalVar(start, duration, end)
                               .WithName(std::string("interval") + suffix);

    TaskID key = std::make_tuple(job_id, task_id);
    all_tasks.emplace(key, TaskType{/*.start=*/start,
                                    /*.end=*/end,
                                    /*.interval=*/interval});
    machine_to_intervals[machine].push_back(interval);
  }
}

자바

class TaskType {
  IntVar start;
  IntVar end;
  IntervalVar interval;
}
Map<List<Integer>, TaskType> allTasks = new HashMap<>();
Map<Integer, List<IntervalVar>> machineToIntervals = new HashMap<>();

for (int jobID = 0; jobID < allJobs.size(); ++jobID) {
  List<Task> job = allJobs.get(jobID);
  for (int taskID = 0; taskID < job.size(); ++taskID) {
    Task task = job.get(taskID);
    String suffix = "_" + jobID + "_" + taskID;

    TaskType taskType = new TaskType();
    taskType.start = model.newIntVar(0, horizon, "start" + suffix);
    taskType.end = model.newIntVar(0, horizon, "end" + suffix);
    taskType.interval = model.newIntervalVar(
        taskType.start, LinearExpr.constant(task.duration), taskType.end, "interval" + suffix);

    List<Integer> key = Arrays.asList(jobID, taskID);
    allTasks.put(key, taskType);
    machineToIntervals.computeIfAbsent(task.machine, (Integer k) -> new ArrayList<>());
    machineToIntervals.get(task.machine).add(taskType.interval);
  }
}

C#

Dictionary<Tuple<int, int>, Tuple<IntVar, IntVar, IntervalVar>> allTasks =
    new Dictionary<Tuple<int, int>, Tuple<IntVar, IntVar, IntervalVar>>(); // (start, end, duration)
Dictionary<int, List<IntervalVar>> machineToIntervals = new Dictionary<int, List<IntervalVar>>();
for (int jobID = 0; jobID < allJobs.Count(); ++jobID)
{
    var job = allJobs[jobID];
    for (int taskID = 0; taskID < job.Count(); ++taskID)
    {
        var task = job[taskID];
        String suffix = $"_{jobID}_{taskID}";
        IntVar start = model.NewIntVar(0, horizon, "start" + suffix);
        IntVar end = model.NewIntVar(0, horizon, "end" + suffix);
        IntervalVar interval = model.NewIntervalVar(start, task.duration, end, "interval" + suffix);
        var key = Tuple.Create(jobID, taskID);
        allTasks[key] = Tuple.Create(start, end, interval);
        if (!machineToIntervals.ContainsKey(task.machine))
        {
            machineToIntervals.Add(task.machine, new List<IntervalVar>());
        }
        machineToIntervals[task.machine].Add(interval);
    }
}

프로그램은 각 작업과 태스크에 대해 모델의 NewIntVar/new_int_var/newIntVar 메서드를 사용하여 변수를 만듭니다.

• start_var: 작업의 시작 시간입니다.
• end_var: 작업의 종료 시간입니다.

start_var 및 end_var의 상한값은 horizon이며 처리 시간을 단축할 수 있습니다. horizon는 다음과 같은 이유로 모든 작업을 완료하기에 충분히 큽니다. 겹치지 않는 시간 간격으로 작업을 예약하는 경우 (최적화되지 않은 솔루션) 일정의 총 길이는 정확히 horizon입니다. 따라서 최적 솔루션의 지속 시간은 horizon 이하여야 합니다.

다음으로 프로그램은 NewIntervalVar/new_interval_var/newIntervalVar를 사용합니다. 메서드를 사용하여 값이 가변 시간인 간격 변수를 만듭니다. 간격 — 태스크의 간격입니다. 이 메서드에 대한 입력은 다음과 같습니다.

• 작업의 시작 시간입니다.
• 작업 시간 간격의 길이입니다.
• 작업의 종료 시간입니다.
• 간격 변수의 이름입니다.

어떤 솔루션에서든 end_var에서 start_var를 뺀 값은 duration와 같아야 합니다.

제약 조건 정의

다음 코드는 문제의 제약 조건을 정의합니다.

Python

# Create and add disjunctive constraints.
for machine in all_machines:
    model.add_no_overlap(machine_to_intervals[machine])

# Precedences inside a job.
for job_id, job in enumerate(jobs_data):
    for task_id in range(len(job) - 1):
        model.add(
            all_tasks[job_id, task_id + 1].start >= all_tasks[job_id, task_id].end
        )

C++

// Create and add disjunctive constraints.
for (const auto machine : all_machines) {
  cp_model.AddNoOverlap(machine_to_intervals[machine]);
}

// Precedences inside a job.
for (int job_id = 0; job_id < jobs_data.size(); ++job_id) {
  const auto& job = jobs_data[job_id];
  for (int task_id = 0; task_id < job.size() - 1; ++task_id) {
    TaskID key = std::make_tuple(job_id, task_id);
    TaskID next_key = std::make_tuple(job_id, task_id + 1);
    cp_model.AddGreaterOrEqual(all_tasks[next_key].start, all_tasks[key].end);
  }
}

자바

// Create and add disjunctive constraints.
for (int machine : allMachines) {
  List<IntervalVar> list = machineToIntervals.get(machine);
  model.addNoOverlap(list);
}

// Precedences inside a job.
for (int jobID = 0; jobID < allJobs.size(); ++jobID) {
  List<Task> job = allJobs.get(jobID);
  for (int taskID = 0; taskID < job.size() - 1; ++taskID) {
    List<Integer> prevKey = Arrays.asList(jobID, taskID);
    List<Integer> nextKey = Arrays.asList(jobID, taskID + 1);
    model.addGreaterOrEqual(allTasks.get(nextKey).start, allTasks.get(prevKey).end);
  }
}

C#

// Create and add disjunctive constraints.
foreach (int machine in allMachines)
{
    model.AddNoOverlap(machineToIntervals[machine]);
}

// Precedences inside a job.
for (int jobID = 0; jobID < allJobs.Count(); ++jobID)
{
    var job = allJobs[jobID];
    for (int taskID = 0; taskID < job.Count() - 1; ++taskID)
    {
        var key = Tuple.Create(jobID, taskID);
        var nextKey = Tuple.Create(jobID, taskID + 1);
        model.Add(allTasks[nextKey].Item1 >= allTasks[key].Item2);
    }
}

프로그램은 모델의 AddNoOverlap/add_no_overlap/addNoOverlap 메서드를 사용합니다. 중복되지 않는 제약 조건을 생성하여 시간이 겹치지 않도록 할 수 있습니다.

다음으로 프로그램은 우선순위 제약 조건을 추가하여 동일한 작업에 대한 연속 작업의 경우 시간이 겹치지 않도록 할 수 있습니다. 각 작업에 대해 작업의 각 태스크에 끝이 있음을 나타내기 위해 선형 제약조건이 추가됩니다. 작업의 다음 태스크 시작 시간 전에 발생할 태스크의 시간입니다.

목표 정의

다음 코드는 문제의 목표를 정의합니다.

Python

# Makespan objective.
obj_var = model.new_int_var(0, horizon, "makespan")
model.add_max_equality(
    obj_var,
    [all_tasks[job_id, len(job) - 1].end for job_id, job in enumerate(jobs_data)],
)
model.minimize(obj_var)

C++

// Makespan objective.
IntVar obj_var = cp_model.NewIntVar({0, horizon}).WithName("makespan");

std::vector<IntVar> ends;
for (int job_id = 0; job_id < jobs_data.size(); ++job_id) {
  const auto& job = jobs_data[job_id];
  TaskID key = std::make_tuple(job_id, job.size() - 1);
  ends.push_back(all_tasks[key].end);
}
cp_model.AddMaxEquality(obj_var, ends);
cp_model.Minimize(obj_var);

자바

// Makespan objective.
IntVar objVar = model.newIntVar(0, horizon, "makespan");
List<IntVar> ends = new ArrayList<>();
for (int jobID = 0; jobID < allJobs.size(); ++jobID) {
  List<Task> job = allJobs.get(jobID);
  List<Integer> key = Arrays.asList(jobID, job.size() - 1);
  ends.add(allTasks.get(key).end);
}
model.addMaxEquality(objVar, ends);
model.minimize(objVar);

C#

// Makespan objective.
IntVar objVar = model.NewIntVar(0, horizon, "makespan");

List<IntVar> ends = new List<IntVar>();
for (int jobID = 0; jobID < allJobs.Count(); ++jobID)
{
    var job = allJobs[jobID];
    var key = Tuple.Create(jobID, job.Count() - 1);
    ends.Add(allTasks[key].Item2);
}
model.AddMaxEquality(objVar, ends);
model.Minimize(objVar);

이 코드는 목표 변수를 생성하고 이를 종료할 수 있습니다

솔버 호출

다음 코드는 솔버를 호출합니다.

Python

solver = cp_model.CpSolver()
status = solver.solve(model)

C++

const CpSolverResponse response = Solve(cp_model.Build());

자바

CpSolver solver = new CpSolver();
CpSolverStatus status = solver.solve(model);

C#

CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);
Console.WriteLine($"Solve status: {status}");

결과 표시

다음 코드는 최적의 일정과 작업을 포함하여 결과를 표시합니다. 인코더-디코더 아키텍처를

Python

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print("Solution:")
    # Create one list of assigned tasks per machine.
    assigned_jobs = collections.defaultdict(list)
    for job_id, job in enumerate(jobs_data):
        for task_id, task in enumerate(job):
            machine = task[0]
            assigned_jobs[machine].append(
                assigned_task_type(
                    start=solver.value(all_tasks[job_id, task_id].start),
                    job=job_id,
                    index=task_id,
                    duration=task[1],
                )
            )

    # Create per machine output lines.
    output = ""
    for machine in all_machines:
        # Sort by starting time.
        assigned_jobs[machine].sort()
        sol_line_tasks = "Machine " + str(machine) + ": "
        sol_line = "           "

        for assigned_task in assigned_jobs[machine]:
            name = f"job_{assigned_task.job}_task_{assigned_task.index}"
            # add spaces to output to align columns.
            sol_line_tasks += f"{name:15}"

            start = assigned_task.start
            duration = assigned_task.duration
            sol_tmp = f"[{start},{start + duration}]"
            # add spaces to output to align columns.
            sol_line += f"{sol_tmp:15}"

        sol_line += "\n"
        sol_line_tasks += "\n"
        output += sol_line_tasks
        output += sol_line

    # Finally print the solution found.
    print(f"Optimal Schedule Length: {solver.objective_value}")
    print(output)
else:
    print("No solution found.")

C++

if (response.status() == CpSolverStatus::OPTIMAL ||
    response.status() == CpSolverStatus::FEASIBLE) {
  LOG(INFO) << "Solution:";
  // create one list of assigned tasks per machine.
  struct AssignedTaskType {
    int job_id;
    int task_id;
    int64_t start;
    int64_t duration;

    bool operator<(const AssignedTaskType& rhs) const {
      return std::tie(this->start, this->duration) <
             std::tie(rhs.start, rhs.duration);
    }
  };

  std::map<int64_t, std::vector<AssignedTaskType>> assigned_jobs;
  for (int job_id = 0; job_id < jobs_data.size(); ++job_id) {
    const auto& job = jobs_data[job_id];
    for (int task_id = 0; task_id < job.size(); ++task_id) {
      const auto [machine, duration] = job[task_id];
      TaskID key = std::make_tuple(job_id, task_id);
      int64_t start = SolutionIntegerValue(response, all_tasks[key].start);
      assigned_jobs[machine].push_back(
          AssignedTaskType{/*.job_id=*/job_id,
                           /*.task_id=*/task_id,
                           /*.start=*/start,
                           /*.duration=*/duration});
    }
  }

  // Create per machine output lines.
  std::string output = "";
  for (const auto machine : all_machines) {
    // Sort by starting time.
    std::sort(assigned_jobs[machine].begin(), assigned_jobs[machine].end());
    std::string sol_line_tasks = "Machine " + std::to_string(machine) + ": ";
    std::string sol_line = "           ";

    for (const auto& assigned_task : assigned_jobs[machine]) {
      std::string name = absl::StrFormat(
          "job_%d_task_%d", assigned_task.job_id, assigned_task.task_id);
      // Add spaces to output to align columns.
      sol_line_tasks += absl::StrFormat("%-15s", name);

      int64_t start = assigned_task.start;
      int64_t duration = assigned_task.duration;
      std::string sol_tmp =
          absl::StrFormat("[%i,%i]", start, start + duration);
      // Add spaces to output to align columns.
      sol_line += absl::StrFormat("%-15s", sol_tmp);
    }
    output += sol_line_tasks + "\n";
    output += sol_line + "\n";
  }
  // Finally print the solution found.
  LOG(INFO) << "Optimal Schedule Length: " << response.objective_value();
  LOG(INFO) << "\n" << output;
} else {
  LOG(INFO) << "No solution found.";
}

자바

if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
  class AssignedTask {
    int jobID;
    int taskID;
    int start;
    int duration;
    // Ctor
    AssignedTask(int jobID, int taskID, int start, int duration) {
      this.jobID = jobID;
      this.taskID = taskID;
      this.start = start;
      this.duration = duration;
    }
  }
  class SortTasks implements Comparator<AssignedTask> {
    @Override
    public int compare(AssignedTask a, AssignedTask b) {
      if (a.start != b.start) {
        return a.start - b.start;
      } else {
        return a.duration - b.duration;
      }
    }
  }
  System.out.println("Solution:");
  // Create one list of assigned tasks per machine.
  Map<Integer, List<AssignedTask>> assignedJobs = new HashMap<>();
  for (int jobID = 0; jobID < allJobs.size(); ++jobID) {
    List<Task> job = allJobs.get(jobID);
    for (int taskID = 0; taskID < job.size(); ++taskID) {
      Task task = job.get(taskID);
      List<Integer> key = Arrays.asList(jobID, taskID);
      AssignedTask assignedTask = new AssignedTask(
          jobID, taskID, (int) solver.value(allTasks.get(key).start), task.duration);
      assignedJobs.computeIfAbsent(task.machine, (Integer k) -> new ArrayList<>());
      assignedJobs.get(task.machine).add(assignedTask);
    }
  }

  // Create per machine output lines.
  String output = "";
  for (int machine : allMachines) {
    // Sort by starting time.
    Collections.sort(assignedJobs.get(machine), new SortTasks());
    String solLineTasks = "Machine " + machine + ": ";
    String solLine = "           ";

    for (AssignedTask assignedTask : assignedJobs.get(machine)) {
      String name = "job_" + assignedTask.jobID + "_task_" + assignedTask.taskID;
      // Add spaces to output to align columns.
      solLineTasks += String.format("%-15s", name);

      String solTmp =
          "[" + assignedTask.start + "," + (assignedTask.start + assignedTask.duration) + "]";
      // Add spaces to output to align columns.
      solLine += String.format("%-15s", solTmp);
    }
    output += solLineTasks + "%n";
    output += solLine + "%n";
  }
  System.out.printf("Optimal Schedule Length: %f%n", solver.objectiveValue());
  System.out.printf(output);
} else {
  System.out.println("No solution found.");
}

C#

if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
{
    Console.WriteLine("Solution:");

    Dictionary<int, List<AssignedTask>> assignedJobs = new Dictionary<int, List<AssignedTask>>();
    for (int jobID = 0; jobID < allJobs.Count(); ++jobID)
    {
        var job = allJobs[jobID];
        for (int taskID = 0; taskID < job.Count(); ++taskID)
        {
            var task = job[taskID];
            var key = Tuple.Create(jobID, taskID);
            int start = (int)solver.Value(allTasks[key].Item1);
            if (!assignedJobs.ContainsKey(task.machine))
            {
                assignedJobs.Add(task.machine, new List<AssignedTask>());
            }
            assignedJobs[task.machine].Add(new AssignedTask(jobID, taskID, start, task.duration));
        }
    }

    // Create per machine output lines.
    String output = "";
    foreach (int machine in allMachines)
    {
        // Sort by starting time.
        assignedJobs[machine].Sort();
        String solLineTasks = $"Machine {machine}: ";
        String solLine = "           ";

        foreach (var assignedTask in assignedJobs[machine])
        {
            String name = $"job_{assignedTask.jobID}_task_{assignedTask.taskID}";
            // Add spaces to output to align columns.
            solLineTasks += $"{name,-15}";

            String solTmp = $"[{assignedTask.start},{assignedTask.start+assignedTask.duration}]";
            // Add spaces to output to align columns.
            solLine += $"{solTmp,-15}";
        }
        output += solLineTasks + "\n";
        output += solLine + "\n";
    }
    // Finally print the solution found.
    Console.WriteLine($"Optimal Schedule Length: {solver.ObjectiveValue}");
    Console.WriteLine($"\n{output}");
}
else
{
    Console.WriteLine("No solution found.");
}

최적의 일정은 다음과 같습니다.

 Optimal Schedule Length: 11
Machine 0: job_0_0   job_1_0
           [0,3]     [3,5]
Machine 1: job_2_0   job_0_1   job_1_2
           [0,4]     [4,6]     [7,11]
Machine 2: job_1_1   job_0_2   job_2_1
           [5,6]     [6,8]     [8,11]

눈 1 7이라고 하는 것을 볼 수 있습니다. 둘 다 유효한 솔루션이지만, 목표는 makespan을 최소화하는 것입니다 job_1_2을 일찍 이동해도 makespan이 줄어들지 않습니다. 로 되어 있으므로 문제 해결사의 관점에서는 두 솔루션이 동일합니다.

전체 프로그램

마지막으로 구직 문제에 관한 전체 프로그램이 있습니다.

Python

"""Minimal jobshop example."""
import collections
from ortools.sat.python import cp_model


def main() -> None:
    """Minimal jobshop problem."""
    # Data.
    jobs_data = [  # task = (machine_id, processing_time).
        [(0, 3), (1, 2), (2, 2)],  # Job0
        [(0, 2), (2, 1), (1, 4)],  # Job1
        [(1, 4), (2, 3)],  # Job2
    ]

    machines_count = 1 + max(task[0] for job in jobs_data for task in job)
    all_machines = range(machines_count)
    # Computes horizon dynamically as the sum of all durations.
    horizon = sum(task[1] for job in jobs_data for task in job)

    # Create the model.
    model = cp_model.CpModel()

    # Named tuple to store information about created variables.
    task_type = collections.namedtuple("task_type", "start end interval")
    # Named tuple to manipulate solution information.
    assigned_task_type = collections.namedtuple(
        "assigned_task_type", "start job index duration"
    )

    # Creates job intervals and add to the corresponding machine lists.
    all_tasks = {}
    machine_to_intervals = collections.defaultdict(list)

    for job_id, job in enumerate(jobs_data):
        for task_id, task in enumerate(job):
            machine, duration = task
            suffix = f"_{job_id}_{task_id}"
            start_var = model.new_int_var(0, horizon, "start" + suffix)
            end_var = model.new_int_var(0, horizon, "end" + suffix)
            interval_var = model.new_interval_var(
                start_var, duration, end_var, "interval" + suffix
            )
            all_tasks[job_id, task_id] = task_type(
                start=start_var, end=end_var, interval=interval_var
            )
            machine_to_intervals[machine].append(interval_var)

    # Create and add disjunctive constraints.
    for machine in all_machines:
        model.add_no_overlap(machine_to_intervals[machine])

    # Precedences inside a job.
    for job_id, job in enumerate(jobs_data):
        for task_id in range(len(job) - 1):
            model.add(
                all_tasks[job_id, task_id + 1].start >= all_tasks[job_id, task_id].end
            )

    # Makespan objective.
    obj_var = model.new_int_var(0, horizon, "makespan")
    model.add_max_equality(
        obj_var,
        [all_tasks[job_id, len(job) - 1].end for job_id, job in enumerate(jobs_data)],
    )
    model.minimize(obj_var)

    # Creates the solver and solve.
    solver = cp_model.CpSolver()
    status = solver.solve(model)

    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        print("Solution:")
        # Create one list of assigned tasks per machine.
        assigned_jobs = collections.defaultdict(list)
        for job_id, job in enumerate(jobs_data):
            for task_id, task in enumerate(job):
                machine = task[0]
                assigned_jobs[machine].append(
                    assigned_task_type(
                        start=solver.value(all_tasks[job_id, task_id].start),
                        job=job_id,
                        index=task_id,
                        duration=task[1],
                    )
                )

        # Create per machine output lines.
        output = ""
        for machine in all_machines:
            # Sort by starting time.
            assigned_jobs[machine].sort()
            sol_line_tasks = "Machine " + str(machine) + ": "
            sol_line = "           "

            for assigned_task in assigned_jobs[machine]:
                name = f"job_{assigned_task.job}_task_{assigned_task.index}"
                # add spaces to output to align columns.
                sol_line_tasks += f"{name:15}"

                start = assigned_task.start
                duration = assigned_task.duration
                sol_tmp = f"[{start},{start + duration}]"
                # add spaces to output to align columns.
                sol_line += f"{sol_tmp:15}"

            sol_line += "\n"
            sol_line_tasks += "\n"
            output += sol_line_tasks
            output += sol_line

        # Finally print the solution found.
        print(f"Optimal Schedule Length: {solver.objective_value}")
        print(output)
    else:
        print("No solution found.")

    # Statistics.
    print("\nStatistics")
    print(f"  - conflicts: {solver.num_conflicts}")
    print(f"  - branches : {solver.num_branches}")
    print(f"  - wall time: {solver.wall_time}s")


if __name__ == "__main__":
    main()

C++

// Nurse scheduling problem with shift requests.
#include <stdlib.h>

#include <algorithm>
#include <cstdint>
#include <map>
#include <numeric>
#include <string>
#include <tuple>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"

namespace operations_research {
namespace sat {

void MinimalJobshopSat() {
  using Task = std::tuple<int64_t, int64_t>;  // (machine_id, processing_time)
  using Job = std::vector<Task>;
  std::vector<Job> jobs_data = {
      {{0, 3}, {1, 2}, {2, 2}},  // Job_0: Task_0 Task_1 Task_2
      {{0, 2}, {2, 1}, {1, 4}},  // Job_1: Task_0 Task_1 Task_2
      {{1, 4}, {2, 3}},          // Job_2: Task_0 Task_1
  };

  int64_t num_machines = 0;
  for (const auto& job : jobs_data) {
    for (const auto& [machine, _] : job) {
      num_machines = std::max(num_machines, 1 + machine);
    }
  }

  std::vector<int> all_machines(num_machines);
  std::iota(all_machines.begin(), all_machines.end(), 0);

  // Computes horizon dynamically as the sum of all durations.
  int64_t horizon = 0;
  for (const auto& job : jobs_data) {
    for (const auto& [_, time] : job) {
      horizon += time;
    }
  }

  // Creates the model.
  CpModelBuilder cp_model;

  struct TaskType {
    IntVar start;
    IntVar end;
    IntervalVar interval;
  };

  using TaskID = std::tuple<int, int>;  // (job_id, task_id)
  std::map<TaskID, TaskType> all_tasks;
  std::map<int64_t, std::vector<IntervalVar>> machine_to_intervals;
  for (int job_id = 0; job_id < jobs_data.size(); ++job_id) {
    const auto& job = jobs_data[job_id];
    for (int task_id = 0; task_id < job.size(); ++task_id) {
      const auto [machine, duration] = job[task_id];
      std::string suffix = absl::StrFormat("_%d_%d", job_id, task_id);
      IntVar start = cp_model.NewIntVar({0, horizon})
                         .WithName(std::string("start") + suffix);
      IntVar end = cp_model.NewIntVar({0, horizon})
                       .WithName(std::string("end") + suffix);
      IntervalVar interval = cp_model.NewIntervalVar(start, duration, end)
                                 .WithName(std::string("interval") + suffix);

      TaskID key = std::make_tuple(job_id, task_id);
      all_tasks.emplace(key, TaskType{/*.start=*/start,
                                      /*.end=*/end,
                                      /*.interval=*/interval});
      machine_to_intervals[machine].push_back(interval);
    }
  }

  // Create and add disjunctive constraints.
  for (const auto machine : all_machines) {
    cp_model.AddNoOverlap(machine_to_intervals[machine]);
  }

  // Precedences inside a job.
  for (int job_id = 0; job_id < jobs_data.size(); ++job_id) {
    const auto& job = jobs_data[job_id];
    for (int task_id = 0; task_id < job.size() - 1; ++task_id) {
      TaskID key = std::make_tuple(job_id, task_id);
      TaskID next_key = std::make_tuple(job_id, task_id + 1);
      cp_model.AddGreaterOrEqual(all_tasks[next_key].start, all_tasks[key].end);
    }
  }

  // Makespan objective.
  IntVar obj_var = cp_model.NewIntVar({0, horizon}).WithName("makespan");

  std::vector<IntVar> ends;
  for (int job_id = 0; job_id < jobs_data.size(); ++job_id) {
    const auto& job = jobs_data[job_id];
    TaskID key = std::make_tuple(job_id, job.size() - 1);
    ends.push_back(all_tasks[key].end);
  }
  cp_model.AddMaxEquality(obj_var, ends);
  cp_model.Minimize(obj_var);

  const CpSolverResponse response = Solve(cp_model.Build());

  if (response.status() == CpSolverStatus::OPTIMAL ||
      response.status() == CpSolverStatus::FEASIBLE) {
    LOG(INFO) << "Solution:";
    // create one list of assigned tasks per machine.
    struct AssignedTaskType {
      int job_id;
      int task_id;
      int64_t start;
      int64_t duration;

      bool operator<(const AssignedTaskType& rhs) const {
        return std::tie(this->start, this->duration) <
               std::tie(rhs.start, rhs.duration);
      }
    };

    std::map<int64_t, std::vector<AssignedTaskType>> assigned_jobs;
    for (int job_id = 0; job_id < jobs_data.size(); ++job_id) {
      const auto& job = jobs_data[job_id];
      for (int task_id = 0; task_id < job.size(); ++task_id) {
        const auto [machine, duration] = job[task_id];
        TaskID key = std::make_tuple(job_id, task_id);
        int64_t start = SolutionIntegerValue(response, all_tasks[key].start);
        assigned_jobs[machine].push_back(
            AssignedTaskType{/*.job_id=*/job_id,
                             /*.task_id=*/task_id,
                             /*.start=*/start,
                             /*.duration=*/duration});
      }
    }

    // Create per machine output lines.
    std::string output = "";
    for (const auto machine : all_machines) {
      // Sort by starting time.
      std::sort(assigned_jobs[machine].begin(), assigned_jobs[machine].end());
      std::string sol_line_tasks = "Machine " + std::to_string(machine) + ": ";
      std::string sol_line = "           ";

      for (const auto& assigned_task : assigned_jobs[machine]) {
        std::string name = absl::StrFormat(
            "job_%d_task_%d", assigned_task.job_id, assigned_task.task_id);
        // Add spaces to output to align columns.
        sol_line_tasks += absl::StrFormat("%-15s", name);

        int64_t start = assigned_task.start;
        int64_t duration = assigned_task.duration;
        std::string sol_tmp =
            absl::StrFormat("[%i,%i]", start, start + duration);
        // Add spaces to output to align columns.
        sol_line += absl::StrFormat("%-15s", sol_tmp);
      }
      output += sol_line_tasks + "\n";
      output += sol_line + "\n";
    }
    // Finally print the solution found.
    LOG(INFO) << "Optimal Schedule Length: " << response.objective_value();
    LOG(INFO) << "\n" << output;
  } else {
    LOG(INFO) << "No solution found.";
  }

  // Statistics.
  LOG(INFO) << "Statistics";
  LOG(INFO) << CpSolverResponseStats(response);
}

}  // namespace sat
}  // namespace operations_research

int main() {
  operations_research::sat::MinimalJobshopSat();
  return EXIT_SUCCESS;
}

자바

package com.google.ortools.sat.samples;
import static java.lang.Math.max;

import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.IntervalVar;
import com.google.ortools.sat.LinearExpr;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.IntStream;

/** Minimal Jobshop problem. */
public class MinimalJobshopSat {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    class Task {
      int machine;
      int duration;
      Task(int machine, int duration) {
        this.machine = machine;
        this.duration = duration;
      }
    }

    final List<List<Task>> allJobs =
        Arrays.asList(Arrays.asList(new Task(0, 3), new Task(1, 2), new Task(2, 2)), // Job0
            Arrays.asList(new Task(0, 2), new Task(2, 1), new Task(1, 4)), // Job1
            Arrays.asList(new Task(1, 4), new Task(2, 3)) // Job2
        );

    int numMachines = 1;
    for (List<Task> job : allJobs) {
      for (Task task : job) {
        numMachines = max(numMachines, 1 + task.machine);
      }
    }
    final int[] allMachines = IntStream.range(0, numMachines).toArray();

    // Computes horizon dynamically as the sum of all durations.
    int horizon = 0;
    for (List<Task> job : allJobs) {
      for (Task task : job) {
        horizon += task.duration;
      }
    }

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

    class TaskType {
      IntVar start;
      IntVar end;
      IntervalVar interval;
    }
    Map<List<Integer>, TaskType> allTasks = new HashMap<>();
    Map<Integer, List<IntervalVar>> machineToIntervals = new HashMap<>();

    for (int jobID = 0; jobID < allJobs.size(); ++jobID) {
      List<Task> job = allJobs.get(jobID);
      for (int taskID = 0; taskID < job.size(); ++taskID) {
        Task task = job.get(taskID);
        String suffix = "_" + jobID + "_" + taskID;

        TaskType taskType = new TaskType();
        taskType.start = model.newIntVar(0, horizon, "start" + suffix);
        taskType.end = model.newIntVar(0, horizon, "end" + suffix);
        taskType.interval = model.newIntervalVar(
            taskType.start, LinearExpr.constant(task.duration), taskType.end, "interval" + suffix);

        List<Integer> key = Arrays.asList(jobID, taskID);
        allTasks.put(key, taskType);
        machineToIntervals.computeIfAbsent(task.machine, (Integer k) -> new ArrayList<>());
        machineToIntervals.get(task.machine).add(taskType.interval);
      }
    }

    // Create and add disjunctive constraints.
    for (int machine : allMachines) {
      List<IntervalVar> list = machineToIntervals.get(machine);
      model.addNoOverlap(list);
    }

    // Precedences inside a job.
    for (int jobID = 0; jobID < allJobs.size(); ++jobID) {
      List<Task> job = allJobs.get(jobID);
      for (int taskID = 0; taskID < job.size() - 1; ++taskID) {
        List<Integer> prevKey = Arrays.asList(jobID, taskID);
        List<Integer> nextKey = Arrays.asList(jobID, taskID + 1);
        model.addGreaterOrEqual(allTasks.get(nextKey).start, allTasks.get(prevKey).end);
      }
    }

    // Makespan objective.
    IntVar objVar = model.newIntVar(0, horizon, "makespan");
    List<IntVar> ends = new ArrayList<>();
    for (int jobID = 0; jobID < allJobs.size(); ++jobID) {
      List<Task> job = allJobs.get(jobID);
      List<Integer> key = Arrays.asList(jobID, job.size() - 1);
      ends.add(allTasks.get(key).end);
    }
    model.addMaxEquality(objVar, ends);
    model.minimize(objVar);

    // Creates a solver and solves the model.
    CpSolver solver = new CpSolver();
    CpSolverStatus status = solver.solve(model);

    if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
      class AssignedTask {
        int jobID;
        int taskID;
        int start;
        int duration;
        // Ctor
        AssignedTask(int jobID, int taskID, int start, int duration) {
          this.jobID = jobID;
          this.taskID = taskID;
          this.start = start;
          this.duration = duration;
        }
      }
      class SortTasks implements Comparator<AssignedTask> {
        @Override
        public int compare(AssignedTask a, AssignedTask b) {
          if (a.start != b.start) {
            return a.start - b.start;
          } else {
            return a.duration - b.duration;
          }
        }
      }
      System.out.println("Solution:");
      // Create one list of assigned tasks per machine.
      Map<Integer, List<AssignedTask>> assignedJobs = new HashMap<>();
      for (int jobID = 0; jobID < allJobs.size(); ++jobID) {
        List<Task> job = allJobs.get(jobID);
        for (int taskID = 0; taskID < job.size(); ++taskID) {
          Task task = job.get(taskID);
          List<Integer> key = Arrays.asList(jobID, taskID);
          AssignedTask assignedTask = new AssignedTask(
              jobID, taskID, (int) solver.value(allTasks.get(key).start), task.duration);
          assignedJobs.computeIfAbsent(task.machine, (Integer k) -> new ArrayList<>());
          assignedJobs.get(task.machine).add(assignedTask);
        }
      }

      // Create per machine output lines.
      String output = "";
      for (int machine : allMachines) {
        // Sort by starting time.
        Collections.sort(assignedJobs.get(machine), new SortTasks());
        String solLineTasks = "Machine " + machine + ": ";
        String solLine = "           ";

        for (AssignedTask assignedTask : assignedJobs.get(machine)) {
          String name = "job_" + assignedTask.jobID + "_task_" + assignedTask.taskID;
          // Add spaces to output to align columns.
          solLineTasks += String.format("%-15s", name);

          String solTmp =
              "[" + assignedTask.start + "," + (assignedTask.start + assignedTask.duration) + "]";
          // Add spaces to output to align columns.
          solLine += String.format("%-15s", solTmp);
        }
        output += solLineTasks + "%n";
        output += solLine + "%n";
      }
      System.out.printf("Optimal Schedule Length: %f%n", solver.objectiveValue());
      System.out.printf(output);
    } else {
      System.out.println("No solution found.");
    }

    // Statistics.
    System.out.println("Statistics");
    System.out.printf("  conflicts: %d%n", solver.numConflicts());
    System.out.printf("  branches : %d%n", solver.numBranches());
    System.out.printf("  wall time: %f s%n", solver.wallTime());
  }

  private MinimalJobshopSat() {}
}

C#

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Sat;

public class ScheduleRequestsSat
{
    private class AssignedTask : IComparable
    {
        public int jobID;
        public int taskID;
        public int start;
        public int duration;

        public AssignedTask(int jobID, int taskID, int start, int duration)
        {
            this.jobID = jobID;
            this.taskID = taskID;
            this.start = start;
            this.duration = duration;
        }

        public int CompareTo(object obj)
        {
            if (obj == null)
                return 1;

            AssignedTask otherTask = obj as AssignedTask;
            if (otherTask != null)
            {
                if (this.start != otherTask.start)
                    return this.start.CompareTo(otherTask.start);
                else
                    return this.duration.CompareTo(otherTask.duration);
            }
            else
                throw new ArgumentException("Object is not a Temperature");
        }
    }

    public static void Main(String[] args)
    {
        var allJobs =
            new[] {
                new[] {
                    // job0
                    new { machine = 0, duration = 3 }, // task0
                    new { machine = 1, duration = 2 }, // task1
                    new { machine = 2, duration = 2 }, // task2
                }
                    .ToList(),
                new[] {
                    // job1
                    new { machine = 0, duration = 2 }, // task0
                    new { machine = 2, duration = 1 }, // task1
                    new { machine = 1, duration = 4 }, // task2
                }
                    .ToList(),
                new[] {
                    // job2
                    new { machine = 1, duration = 4 }, // task0
                    new { machine = 2, duration = 3 }, // task1
                }
                    .ToList(),
            }
                .ToList();

        int numMachines = 0;
        foreach (var job in allJobs)
        {
            foreach (var task in job)
            {
                numMachines = Math.Max(numMachines, 1 + task.machine);
            }
        }
        int[] allMachines = Enumerable.Range(0, numMachines).ToArray();

        // Computes horizon dynamically as the sum of all durations.
        int horizon = 0;
        foreach (var job in allJobs)
        {
            foreach (var task in job)
            {
                horizon += task.duration;
            }
        }

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

        Dictionary<Tuple<int, int>, Tuple<IntVar, IntVar, IntervalVar>> allTasks =
            new Dictionary<Tuple<int, int>, Tuple<IntVar, IntVar, IntervalVar>>(); // (start, end, duration)
        Dictionary<int, List<IntervalVar>> machineToIntervals = new Dictionary<int, List<IntervalVar>>();
        for (int jobID = 0; jobID < allJobs.Count(); ++jobID)
        {
            var job = allJobs[jobID];
            for (int taskID = 0; taskID < job.Count(); ++taskID)
            {
                var task = job[taskID];
                String suffix = $"_{jobID}_{taskID}";
                IntVar start = model.NewIntVar(0, horizon, "start" + suffix);
                IntVar end = model.NewIntVar(0, horizon, "end" + suffix);
                IntervalVar interval = model.NewIntervalVar(start, task.duration, end, "interval" + suffix);
                var key = Tuple.Create(jobID, taskID);
                allTasks[key] = Tuple.Create(start, end, interval);
                if (!machineToIntervals.ContainsKey(task.machine))
                {
                    machineToIntervals.Add(task.machine, new List<IntervalVar>());
                }
                machineToIntervals[task.machine].Add(interval);
            }
        }

        // Create and add disjunctive constraints.
        foreach (int machine in allMachines)
        {
            model.AddNoOverlap(machineToIntervals[machine]);
        }

        // Precedences inside a job.
        for (int jobID = 0; jobID < allJobs.Count(); ++jobID)
        {
            var job = allJobs[jobID];
            for (int taskID = 0; taskID < job.Count() - 1; ++taskID)
            {
                var key = Tuple.Create(jobID, taskID);
                var nextKey = Tuple.Create(jobID, taskID + 1);
                model.Add(allTasks[nextKey].Item1 >= allTasks[key].Item2);
            }
        }

        // Makespan objective.
        IntVar objVar = model.NewIntVar(0, horizon, "makespan");

        List<IntVar> ends = new List<IntVar>();
        for (int jobID = 0; jobID < allJobs.Count(); ++jobID)
        {
            var job = allJobs[jobID];
            var key = Tuple.Create(jobID, job.Count() - 1);
            ends.Add(allTasks[key].Item2);
        }
        model.AddMaxEquality(objVar, ends);
        model.Minimize(objVar);

        // Solve
        CpSolver solver = new CpSolver();
        CpSolverStatus status = solver.Solve(model);
        Console.WriteLine($"Solve status: {status}");

        if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
        {
            Console.WriteLine("Solution:");

            Dictionary<int, List<AssignedTask>> assignedJobs = new Dictionary<int, List<AssignedTask>>();
            for (int jobID = 0; jobID < allJobs.Count(); ++jobID)
            {
                var job = allJobs[jobID];
                for (int taskID = 0; taskID < job.Count(); ++taskID)
                {
                    var task = job[taskID];
                    var key = Tuple.Create(jobID, taskID);
                    int start = (int)solver.Value(allTasks[key].Item1);
                    if (!assignedJobs.ContainsKey(task.machine))
                    {
                        assignedJobs.Add(task.machine, new List<AssignedTask>());
                    }
                    assignedJobs[task.machine].Add(new AssignedTask(jobID, taskID, start, task.duration));
                }
            }

            // Create per machine output lines.
            String output = "";
            foreach (int machine in allMachines)
            {
                // Sort by starting time.
                assignedJobs[machine].Sort();
                String solLineTasks = $"Machine {machine}: ";
                String solLine = "           ";

                foreach (var assignedTask in assignedJobs[machine])
                {
                    String name = $"job_{assignedTask.jobID}_task_{assignedTask.taskID}";
                    // Add spaces to output to align columns.
                    solLineTasks += $"{name,-15}";

                    String solTmp = $"[{assignedTask.start},{assignedTask.start+assignedTask.duration}]";
                    // Add spaces to output to align columns.
                    solLine += $"{solTmp,-15}";
                }
                output += solLineTasks + "\n";
                output += solLine + "\n";
            }
            // Finally print the solution found.
            Console.WriteLine($"Optimal Schedule Length: {solver.ObjectiveValue}");
            Console.WriteLine($"\n{output}");
        }
        else
        {
            Console.WriteLine("No solution found.");
        }

        Console.WriteLine("Statistics");
        Console.WriteLine($"  conflicts: {solver.NumConflicts()}");
        Console.WriteLine($"  branches : {solver.NumBranches()}");
        Console.WriteLine($"  wall time: {solver.WallTime()}s");
    }
}