常見的排程問題是工作坊;在這個工作中,系統會透過多部機器處理多項工作。
每項工作都是由一系列的工作組成,而這些工作必須依照特定順序執行,而且每個工作都必須在特定機器上處理。
舉例來說,這項工作可能是單一消費性商品 (例如汽車) 的製造商。問題在於將工作安排在機器上,為了盡量減少排程的 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)
表示工作 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 是在為門上畫,而繪製需要兩小時的時間才能乾燥。)因此,您會取得以下限制:t
0、2 + 2 <=t
0、3
- 無重疊限制:這是因機器無法同時處理兩項任務的限制所導致。舉例來說,工作(0, 2) 和工作(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)
之前)。
問題目標
工作坊問題的目標是盡量減少 makespan:工作從工作最早開始到最後結束時間的時間長度。
計畫解決方案
以下各節將說明可解決工作中心問題的程式主要元素。
匯入程式庫
下列程式碼會匯入必要的程式庫。
Python
import collections from ortools.sat.python import cp_model
C++
#include <stdlib.h> #include <algorithm> #include <cstdint> #include <map> #include <numeric> #include <string> #include <tuple> #include <vector> #include "absl/strings/str_format.h" #include "ortools/base/logging.h" #include "ortools/sat/cp_model.h" #include "ortools/sat/cp_model.pb.h" #include "ortools/sat/cp_model_solver.h"
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 的老眼讀者可能想知道為什麼 Job_1_2 是排定在 7 時,而不是 6 時間。這兩種解決方案都是有效的解決方案,但請注意:目標是盡可能減少 make Span。提前遷移工作_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"); } }