אחת הבעיות הנפוצות בלוח הזמנים היא job shop, שבה מעובדות מספר משימות במספר מכונות.
כל משימה מורכבת מרצף של משימות, שצריכות להתבצע בסדר נתון ושצריך לעבד כל משימה במכונה ספציפית.
לדוגמה, העבודה יכולה להיות ייצור של פריט צריכה יחיד, כמו רכב.
הבעיה היא לתזמן את המשימות במכונות כדי לצמצם את 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 כוללת שלוש משימות. את הראשון (0, 3), צריך לעבד במכונה 0 ב-3 יחידות זמן. את השני (1, 2), צריך לעבד במכונה 1 ב-2 יחידות זמן, וכן הלאה. בסך הכול, יש שמונה משימות.
פתרון לבעיה
כדי לפתור את הבעיה של חדר העבודה, צריך להקצות שעת התחלה לכל משימה, שעומדת במגבלות שצוינו למעלה.
בתרשים הבא מוצג פתרון אפשרי אחד לבעיה:
תוכלו לבדוק שהמשימות בכל משימה מתוזמנות במרווחי זמן לא חופפים, לפי הסדר שנקבע לבעיה.
הפתרון הוא באורך 12 - זו הפעם הראשונה שבה כל שלוש המשימות הושלמו. עם זאת, כפי שאפשר לראות בהמשך, זה לא הפתרון האופטימלי לבעיה.
משתנים ואילוצים של הבעיה
בקטע הזה נסביר איך להגדיר את המשתנים והאילוצים של הבעיה.
קודם כול צריך לאפשר ל-task(i, j) לציין את משימת ה-jth ברצף של משימה i. לדוגמה, task(0, 2) מציין את המשימה השנייה של משימה 0, שתואמת לצמד (1, 2) בתיאור הבעיה.
לאחר מכן, מגדירים את ti, j כשעת ההתחלה של task(i, j). ti, j הם המשתנים בבעיה של חנות העבודה. כדי למצוא פתרון, צריך לקבוע ערכים למשתנים שעומדים בדרישת הבעיה.
יש שני סוגי אילוצים לגבי הבעיה של חנות עבודות:
- אילוצי קדימות – אלה נוצרים כתוצאה מהתנאי שלכל שתי משימות עוקבות באותה המשימה, הראשונה צריכה להסתיים לפני שאפשר להתחיל את השנייה. לדוגמה,
task(0, 2)ו-task(0, 3)הן משימות עוקבות של משימה 0. מכיוון שזמן העיבוד עבורtask(0, 2)הוא 2, שעת ההתחלה שלtask(0, 3)חייבת להיות לפחות 2 יחידות זמן אחרי שעת ההתחלה של משימה 2. (יכול להיות שמשימה 2 היא ציור של דלת, ונדרשות שעתיים עד שהצבע יתייבש.) כתוצאה מכך, מתקבלת המגבלה הבאה:t0, 2 + 2 <=t0, 3
- ללא אילוצים חופפים – הם נובעים מההגבלה שמכונה לא יכולה לעבוד על שתי משימות בו-זמנית.
לדוגמה, גם משימה(0, 2) ומשימה(2, 1) מעובדות במכונה 1.
זמני העיבוד שלהם הם 2 ו-4, בהתאמה, אחת מהמגבלות הבאות חייבת להתקיים:
t0, 2 + 2 <=t2, 1 (אם התאריךtask(0, 2)מתוזמן לפניtask(2, 1)) אוt2, 1 + 4 <=t0, 2 (אם התאריךtask(2, 1)מתוזמן לפניtask(0, 2)).
מטרת הבעיה
מטרת הבעיה של חנות העבודה היא למזער את האיפור: משך הזמן משעת ההתחלה המוקדמת ביותר של המשימות ועד לשעת הסיום האחרונה.
פתרון תוכנית
בקטעים הבאים מתוארים המרכיבים העיקריים של תוכנית שפותרת את הבעיה של חנות המשרות.
ייבוא הספריות
הקוד הבא מייבא את הספרייה הנדרשת.
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"
Java
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;
}
}
Java
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;
Java
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);
}
}
Java
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);
}
}
Java
// 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);
Java
// 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());
Java
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.";
}
Java
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 עשויים לתהות למה משימה_1_2 תוזמנה לשעה 7 במקום בשעה 6. שניהם הם פתרונות תקפים, אבל חשוב לזכור: המטרה היא למזער את פוטנציאל החשיפה. העברת משימה_1_2 מוקדם יותר לא תצמצם את פוטנציאל החשיפה, כך ששני הפתרונות שווים מבחינתו של הפותר.
כל התוכנית
לבסוף, הנה התוכנית המלאה שמתמקדת בבעיה של חנות העבודה.
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;
}
Java
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");
}
}