مشکل فروشگاه کار

یکی از مشکلات رایج زمان‌بندی، کارگاه است که در آن چندین کار در چندین ماشین پردازش می‌شوند.

هر کار متشکل از دنباله ای از وظایف است که باید به ترتیب معین انجام شود و هر کار باید بر روی یک ماشین خاص پردازش شود. به عنوان مثال، این شغل می تواند تولید یک کالای مصرفی واحد، مانند خودرو باشد. مشکل این است که وظایف روی ماشین‌ها را به گونه‌ای برنامه‌ریزی کنید که 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)]

در مثال، job 0 دارای سه وظیفه است. اولین، (0، 3)، باید در ماشین 0 در 3 واحد زمان پردازش شود. دوم، (1، 2)، باید در ماشین 1 در 2 واحد زمان پردازش شود، و غیره. در مجموع، هشت وظیفه وجود دارد.

راه حلی برای مشکل

یک راه حل برای مشکل کارگاه، تعیین یک زمان شروع برای هر کار است که محدودیت های داده شده در بالا را برآورده می کند. نمودار زیر یک راه حل ممکن برای مشکل را نشان می دهد:

می‌توانید بررسی کنید که وظایف هر کار در بازه‌های زمانی غیرهمپوشانی، به ترتیبی که با مشکل ارائه می‌شود، برنامه‌ریزی شده باشند.

طول این محلول 12 است که برای اولین بار است که هر سه کار کامل می شود. با این حال، همانطور که در زیر خواهید دید، این راه حل بهینه برای مشکل نیست.

متغیرها و محدودیت ها برای مسئله

این بخش نحوه تنظیم متغیرها و محدودیت ها را برای مشکل توضیح می دهد. ابتدا، اجازه دهید task(i, j) وظیفه j را در دنباله کار i نشان دهد. برای مثال task(0, 2) وظیفه دوم را برای job 0 نشان می‌دهد که با جفت (1, 2) در توضیحات مشکل مطابقت دارد.

بعد، t _{i, j را} به عنوان زمان شروع task(i, j) تعریف کنید. t _{i، j} متغیرهای مشکل کارگاه هستند. یافتن راه حل مستلزم تعیین مقادیری برای این متغیرها است که نیاز مسئله را برآورده می کند.

دو نوع محدودیت برای مشکل کارگاه وجود دارد:

• محدودیت‌های اولویت - اینها از شرایطی ناشی می‌شوند که برای هر دو کار متوالی در یک کار، اولین باید قبل از شروع دوم تکمیل شود. به عنوان مثال، task(0, 2) و task(0, 3) وظایف متوالی برای job 0 هستند. از آنجایی که زمان پردازش برای task(0, 2) 2 است، زمان شروع task(0, 3) باید در حداقل 2 واحد زمان بعد از زمان شروع برای کار 2. (شاید کار 2 رنگ آمیزی درب باشد و دو ساعت طول می کشد تا رنگ خشک شود.) در نتیجه محدودیت زیر را دریافت می کنید:
  • t _{0, 2} + 2 <= t _{0, 3}
• بدون محدودیت های همپوشانی - این محدودیت ها از این محدودیت ناشی می شوند که یک ماشین نمی تواند همزمان روی دو کار کار کند. به عنوان مثال، task(0،2) و task(2،1) هر دو در ماشین 1 پردازش می شوند. از آنجایی که زمان پردازش آنها به ترتیب 2 و 4 است، یکی از محدودیت های زیر باید برقرار باشد:
  • 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) برنامه ریزی شده باشد).

هدف برای مشکل

هدف از مشکل کارگاه به حداقل رساندن زمان ساخت است: مدت زمان از اولین زمان شروع کار تا آخرین زمان پایان.

یک راه حل برنامه

بخش‌های زیر عناصر اصلی برنامه‌ای را توضیح می‌دهند که مشکل کارگاه را حل می‌کند.

کتابخانه ها را وارد کنید

کد زیر کتابخانه مورد نیاز را وارد می کند.

پایتون

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;

سی شارپ

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

داده ها را تعریف کنید

در مرحله بعد، برنامه داده های مشکل را تعریف می کند.

پایتون

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;
  }
}

سی شارپ

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;
    }
}

مدل را اعلام کنید

کد زیر مدل مشکل را اعلام می کند.

پایتون

model = cp_model.CpModel()

C++

CpModelBuilder cp_model;

جاوا

CpModel model = new CpModel();

سی شارپ

CpModel model = new 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)

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

سی شارپ

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 برابر باشد.

محدودیت ها را تعریف کنید

کد زیر محدودیت های مشکل را تعریف می کند.

پایتون

# 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);
  }
}

سی شارپ

// 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 مدل برای ایجاد محدودیت‌های بدون همپوشانی استفاده می‌کند، که مانع از همپوشانی وظایف یک دستگاه در زمان می‌شود.

سپس، برنامه محدودیت‌های اولویت را اضافه می‌کند، که مانع از همپوشانی کارهای متوالی برای یک کار در زمان می‌شود. برای هر کار و هر وظیفه در کار، یک محدودیت خطی اضافه می شود تا مشخص شود که زمان پایان یک کار قبل از زمان شروع کار بعدی در کار رخ دهد.

هدف را تعریف کنید

کد زیر هدف را در مسئله مشخص می کند.

پایتون

# 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);

سی شارپ

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

این کد یک متغیر هدف ایجاد می کند و آن را محدود می کند تا حداکثر پایان همه کارها باشد.

حل کننده را فراخوانی کنید

کد زیر حل کننده را فراخوانی می کند.

پایتون

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);

سی شارپ

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

نمایش نتایج

کد زیر نتایج، از جمله زمان بندی بهینه و فواصل وظایف را نمایش می دهد.

پایتون

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.");
}

سی شارپ

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 را بررسی می کنند ممکن است تعجب کنند که چرا job_1_2 در زمان 7 به جای زمان 6 برنامه ریزی شده است. هر دو راه حل معتبری هستند، اما به یاد داشته باشید: هدف به حداقل رساندن زمان ساخت است. جابجایی job_1_2 زودتر باعث کاهش طول عمر نمی شود، بنابراین این دو راه حل از دیدگاه حل کننده برابر هستند.

کل برنامه

در نهایت، در اینجا کل برنامه برای مشکل فروشگاه کار آمده است.

پایتون

"""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() {}
}

سی شارپ

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");
    }
}