一种常见的调度问题是“作业店”,即在多台机器上处理多个作业。
每个作业都由一系列任务组成,这些任务必须按给定顺序执行,并且每个任务都必须在特定的机器上处理。例如,作业可以是制造单件消费者商品(如汽车)。问题是在机器上调度任务,以最大限度减少时间表的 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 序列中的第 j 个任务。例如,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
- 无重叠约束 - 这些约束因机器无法同时处理两项任务的限制而产生。例如,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)
之前)。
问题的目标
求职招聘问题的目标是最大限度地缩短 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 时间。这两者都是有效的解决方案,但请注意:目标是最大限度地减少 Makespan。将 job_1_2 移至更早位置不会减少 makespan,因此从求解器的角度来看,这两种解决方案是相同的。
整个计划
最后,以下是有关求职商店问题的完整程序。
Python
"""Minimal jobshop example.""" import collections from ortools.sat.python import cp_model def main() -> None: """Minimal jobshop problem.""" # Data. jobs_data = [ # task = (machine_id, processing_time). [(0, 3), (1, 2), (2, 2)], # Job0 [(0, 2), (2, 1), (1, 4)], # Job1 [(1, 4), (2, 3)], # Job2 ] machines_count = 1 + max(task[0] for job in jobs_data for task in job) all_machines = range(machines_count) # Computes horizon dynamically as the sum of all durations. horizon = sum(task[1] for job in jobs_data for task in job) # Create the model. model = cp_model.CpModel() # Named tuple to store information about created variables. task_type = collections.namedtuple("task_type", "start end interval") # Named tuple to manipulate solution information. assigned_task_type = collections.namedtuple( "assigned_task_type", "start job index duration" ) # Creates job intervals and add to the corresponding machine lists. all_tasks = {} machine_to_intervals = collections.defaultdict(list) for job_id, job in enumerate(jobs_data): for task_id, task in enumerate(job): machine, duration = task suffix = f"_{job_id}_{task_id}" start_var = model.new_int_var(0, horizon, "start" + suffix) end_var = model.new_int_var(0, horizon, "end" + suffix) interval_var = model.new_interval_var( start_var, duration, end_var, "interval" + suffix ) all_tasks[job_id, task_id] = task_type( start=start_var, end=end_var, interval=interval_var ) machine_to_intervals[machine].append(interval_var) # Create and add disjunctive constraints. for machine in all_machines: model.add_no_overlap(machine_to_intervals[machine]) # Precedences inside a job. for job_id, job in enumerate(jobs_data): for task_id in range(len(job) - 1): model.add( all_tasks[job_id, task_id + 1].start >= all_tasks[job_id, task_id].end ) # Makespan objective. obj_var = model.new_int_var(0, horizon, "makespan") model.add_max_equality( obj_var, [all_tasks[job_id, len(job) - 1].end for job_id, job in enumerate(jobs_data)], ) model.minimize(obj_var) # Creates the solver and solve. solver = cp_model.CpSolver() status = solver.solve(model) if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE: print("Solution:") # Create one list of assigned tasks per machine. assigned_jobs = collections.defaultdict(list) for job_id, job in enumerate(jobs_data): for task_id, task in enumerate(job): machine = task[0] assigned_jobs[machine].append( assigned_task_type( start=solver.value(all_tasks[job_id, task_id].start), job=job_id, index=task_id, duration=task[1], ) ) # Create per machine output lines. output = "" for machine in all_machines: # Sort by starting time. assigned_jobs[machine].sort() sol_line_tasks = "Machine " + str(machine) + ": " sol_line = " " for assigned_task in assigned_jobs[machine]: name = f"job_{assigned_task.job}_task_{assigned_task.index}" # add spaces to output to align columns. sol_line_tasks += f"{name:15}" start = assigned_task.start duration = assigned_task.duration sol_tmp = f"[{start},{start + duration}]" # add spaces to output to align columns. sol_line += f"{sol_tmp:15}" sol_line += "\n" sol_line_tasks += "\n" output += sol_line_tasks output += sol_line # Finally print the solution found. print(f"Optimal Schedule Length: {solver.objective_value}") print(output) else: print("No solution found.") # Statistics. print("\nStatistics") print(f" - conflicts: {solver.num_conflicts}") print(f" - branches : {solver.num_branches}") print(f" - wall time: {solver.wall_time}s") if __name__ == "__main__": main()
C++
// Nurse scheduling problem with shift requests. #include <stdlib.h> #include <algorithm> #include <cstdint> #include <map> #include <numeric> #include <string> #include <tuple> #include <vector> #include "absl/strings/str_format.h" #include "ortools/base/logging.h" #include "ortools/sat/cp_model.h" #include "ortools/sat/cp_model.pb.h" #include "ortools/sat/cp_model_solver.h" namespace operations_research { namespace sat { void MinimalJobshopSat() { using Task = std::tuple<int64_t, int64_t>; // (machine_id, processing_time) using Job = std::vector<Task>; std::vector<Job> jobs_data = { {{0, 3}, {1, 2}, {2, 2}}, // Job_0: Task_0 Task_1 Task_2 {{0, 2}, {2, 1}, {1, 4}}, // Job_1: Task_0 Task_1 Task_2 {{1, 4}, {2, 3}}, // Job_2: Task_0 Task_1 }; int64_t num_machines = 0; for (const auto& job : jobs_data) { for (const auto& [machine, _] : job) { num_machines = std::max(num_machines, 1 + machine); } } std::vector<int> all_machines(num_machines); std::iota(all_machines.begin(), all_machines.end(), 0); // Computes horizon dynamically as the sum of all durations. int64_t horizon = 0; for (const auto& job : jobs_data) { for (const auto& [_, time] : job) { horizon += time; } } // Creates the model. CpModelBuilder cp_model; struct TaskType { IntVar start; IntVar end; IntervalVar interval; }; using TaskID = std::tuple<int, int>; // (job_id, task_id) std::map<TaskID, TaskType> all_tasks; std::map<int64_t, std::vector<IntervalVar>> machine_to_intervals; for (int job_id = 0; job_id < jobs_data.size(); ++job_id) { const auto& job = jobs_data[job_id]; for (int task_id = 0; task_id < job.size(); ++task_id) { const auto [machine, duration] = job[task_id]; std::string suffix = absl::StrFormat("_%d_%d", job_id, task_id); IntVar start = cp_model.NewIntVar({0, horizon}) .WithName(std::string("start") + suffix); IntVar end = cp_model.NewIntVar({0, horizon}) .WithName(std::string("end") + suffix); IntervalVar interval = cp_model.NewIntervalVar(start, duration, end) .WithName(std::string("interval") + suffix); TaskID key = std::make_tuple(job_id, task_id); all_tasks.emplace(key, TaskType{/*.start=*/start, /*.end=*/end, /*.interval=*/interval}); machine_to_intervals[machine].push_back(interval); } } // Create and add disjunctive constraints. for (const auto machine : all_machines) { cp_model.AddNoOverlap(machine_to_intervals[machine]); } // Precedences inside a job. for (int job_id = 0; job_id < jobs_data.size(); ++job_id) { const auto& job = jobs_data[job_id]; for (int task_id = 0; task_id < job.size() - 1; ++task_id) { TaskID key = std::make_tuple(job_id, task_id); TaskID next_key = std::make_tuple(job_id, task_id + 1); cp_model.AddGreaterOrEqual(all_tasks[next_key].start, all_tasks[key].end); } } // Makespan objective. IntVar obj_var = cp_model.NewIntVar({0, horizon}).WithName("makespan"); std::vector<IntVar> ends; for (int job_id = 0; job_id < jobs_data.size(); ++job_id) { const auto& job = jobs_data[job_id]; TaskID key = std::make_tuple(job_id, job.size() - 1); ends.push_back(all_tasks[key].end); } cp_model.AddMaxEquality(obj_var, ends); cp_model.Minimize(obj_var); const CpSolverResponse response = Solve(cp_model.Build()); if (response.status() == CpSolverStatus::OPTIMAL || response.status() == CpSolverStatus::FEASIBLE) { LOG(INFO) << "Solution:"; // create one list of assigned tasks per machine. struct AssignedTaskType { int job_id; int task_id; int64_t start; int64_t duration; bool operator<(const AssignedTaskType& rhs) const { return std::tie(this->start, this->duration) < std::tie(rhs.start, rhs.duration); } }; std::map<int64_t, std::vector<AssignedTaskType>> assigned_jobs; for (int job_id = 0; job_id < jobs_data.size(); ++job_id) { const auto& job = jobs_data[job_id]; for (int task_id = 0; task_id < job.size(); ++task_id) { const auto [machine, duration] = job[task_id]; TaskID key = std::make_tuple(job_id, task_id); int64_t start = SolutionIntegerValue(response, all_tasks[key].start); assigned_jobs[machine].push_back( AssignedTaskType{/*.job_id=*/job_id, /*.task_id=*/task_id, /*.start=*/start, /*.duration=*/duration}); } } // Create per machine output lines. std::string output = ""; for (const auto machine : all_machines) { // Sort by starting time. std::sort(assigned_jobs[machine].begin(), assigned_jobs[machine].end()); std::string sol_line_tasks = "Machine " + std::to_string(machine) + ": "; std::string sol_line = " "; for (const auto& assigned_task : assigned_jobs[machine]) { std::string name = absl::StrFormat( "job_%d_task_%d", assigned_task.job_id, assigned_task.task_id); // Add spaces to output to align columns. sol_line_tasks += absl::StrFormat("%-15s", name); int64_t start = assigned_task.start; int64_t duration = assigned_task.duration; std::string sol_tmp = absl::StrFormat("[%i,%i]", start, start + duration); // Add spaces to output to align columns. sol_line += absl::StrFormat("%-15s", sol_tmp); } output += sol_line_tasks + "\n"; output += sol_line + "\n"; } // Finally print the solution found. LOG(INFO) << "Optimal Schedule Length: " << response.objective_value(); LOG(INFO) << "\n" << output; } else { LOG(INFO) << "No solution found."; } // Statistics. LOG(INFO) << "Statistics"; LOG(INFO) << CpSolverResponseStats(response); } } // namespace sat } // namespace operations_research int main() { operations_research::sat::MinimalJobshopSat(); return EXIT_SUCCESS; }
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"); } }