ortools系列：分配问题之任务大小约束
ortools系列：分配问题之任务大小约束
1. 任务大小的限制
在前面的例子中，我们假设任务没有什么资源约束，但是在实际业务场景中，每个任务可能需要不同的时间，不同的资源约束等。下面描述一个分配问题，其中每个任务都有一个大小，它表示任务需要多少时间或工作量，每个工人执行的任务的总大小有一个固定的界限，即工作量不能超标。
针对这个问题，我们使用CP-SAT以及MIP两种模型分别讲解思路和解决方法。
2. CP-SAT
首先讲讲如何建模成CP-SAT问题。
from ortools.sat.python import cp_model
import time
import numpy as np
def main():
# 创建约束规划模型
model = cp_model.CpModel()
start = time.time()
# 成本矩阵给出了工人i执行任务j的成本
cost = [[90, 76, 75, 70, 50, 74, 12, 68],
[35, 85, 55, 65, 48, 101, 70, 83],
[125, 95, 90, 105, 59, 120, 36, 73],
[45, 110, 95, 115, 104, 83, 37, 71],
[60, 105, 80, 75, 59, 62, 93, 88],
[45, 65, 110, 95, 47, 31, 81, 34],
[38, 51, 107, 41, 69, 99, 115, 48],
[47, 85, 57, 71, 92, 77, 109, 36],
[39, 63, 97, 49, 118, 56, 92, 61],
[47, 101, 71, 60, 88, 109, 52, 90]]
# size向量给出了每个任务的大小
sizes = [10, 7, 3, 12, 15, 4, 11, 5]
# total_size_max是任何单个工作者执行的任务的总大小的上限
total_size_max = 15
# 任务数量和工人数量
num_workers = len(cost)
num_tasks = len(cost[1])
# Variables
# 创建整数变数，值是[0,1]
x = []
for i in range(num_workers):
t = []
for j in range(num_tasks):
t.append(model.NewIntVar(0, 1, "x[%i,%i]" % (i, j)))
x.append(t)
x_array = [x[i][j] for i in range(num_workers) for j in range(num_tasks)]
# Constraint
# Each task is assigned to at least one worker.
# 添加约束，每个任务至少一个分配给一个工人
[model.Add(sum(x[i][j] for i in range(num_workers)) >= 1)
for j in range(num_tasks)]
# Total size of tasks for each worker is at most total_size_max.
# 添加约束，每个工作的总工作量不能超过每个工人的最大允许工作量
[model.Add(sum(sizes[j] * x[i][j] for j in range(num_tasks)) <= total_size_max)
for i in range(num_workers)]
# 目标函数
model.Minimize(sum([np.dot(x_row, cost_row) for (x_row, cost_row) in zip(x, cost)]))
solver = cp_model.CpSolver()
# 求解并列印结果
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
print(Minimum cost = %i % solver.ObjectiveValue())
print()
for i in range(num_workers):
for j in range(num_tasks):
if solver.Value(x[i][j]) == 1:
print(Worker , i, assigned to task , j, Cost = , cost[i][j])
print()
end = time.time()
print("Time = ", round(end - start, 4), "seconds")
if __name__ == __main__:
main()
# 结果
Minimum cost = 326
Worker 0 assigned to task 6 Cost = 12
Worker 1 assigned to task 0 Cost = 35
Worker 1 assigned to task 2 Cost = 55
Worker 4 assigned to task 4 Cost = 59
Worker 5 assigned to task 5 Cost = 31
Worker 5 assigned to task 7 Cost = 34
Worker 6 assigned to task 1 Cost = 51
Worker 8 assigned to task 3 Cost = 49
Time = 6.5922 seconds
3. MIP
接下来，我们描述一个使用MIP求解器的分配问题的解决方案。
from __future__ import print_function
import time
from ortools.linear_solver import pywraplp
def main():
# 初始化整数规划求解器
solver = pywraplp.Solver(SolveAssignmentProblem,
pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
start = time.time()
# 成本矩阵给出了工人i执行任务j的成本
cost = [[90, 76, 75, 70, 50, 74, 12, 68],
[35, 85, 55, 65, 48, 101, 70, 83],
[125, 95, 90, 105, 59, 120, 36, 73],
[45, 110, 95, 115, 104, 83, 37, 71],
[60, 105, 80, 75, 59, 62, 93, 88],
[45, 65, 110, 95, 47, 31, 81, 34],
[38, 51, 107, 41, 69, 99, 115, 48],
[47, 85, 57, 71, 92, 77, 109, 36],
[39, 63, 97, 49, 118, 56, 92, 61],
[47, 101, 71, 60, 88, 109, 52, 90]]
# size向量给出了每个任务的大小
sizes = [10, 7, 3, 12, 15, 4, 11, 5]
# total_size_max是任何单个工作者执行的任务的总大小的上限
total_size_max = 15
# 任务数量和工人数量
num_workers = len(cost)
num_tasks = len(cost[1])
# Variables
# 创建整数变数
x = {}
for i in range(num_workers):
for j in range(num_tasks):
x[i, j] = solver.IntVar(0, 1, x[%i,%i] % (i, j))
# Constraints
# The total size of the tasks each worker takes on is at most total_size_max.
# 添加约束，每个工人的工作量不能超过最大允许量
for i in range(num_workers):
solver.Add(solver.Sum([task_sizes[j] * x[i, j] for j in range(num_tasks)]) <= total_size_max)
# Each task is assigned to at least one worker.
# 添加约束，每个任务至少分配给一个工人
for j in range(num_tasks):
solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) >= 1)
# 目标函数
solver.Minimize(solver.Sum([cost[i][j] * x[i, j] for i in range(num_workers)
for j in range(num_tasks)]))
# 求解问题
sol = solver.Solve()
print(Minimum cost = , solver.Objective().Value())
print()
for i in range(num_workers):
for j in range(num_tasks):
if x[i, j].solution_value() > 0:
print(Worker, i, assigned to task, j, Cost = , cost[i][j])
print()
end = time.time()
print("Time = ", round(end - start, 4), "seconds")
if __name__ == __main__:
main()
# 结果
Minimum cost = 326.0
Worker 0 assigned to task 6 Cost = 12
Worker 1 assigned to task 0 Cost = 35
Worker 1 assigned to task 2 Cost = 55
Worker 4 assigned to task 4 Cost = 59
Worker 5 assigned to task 5 Cost = 31
Worker 5 assigned to task 7 Cost = 34
Worker 6 assigned to task 1 Cost = 51
Worker 8 assigned to task 3 Cost = 49
Time = 0.037 seconds
CP-SAT和MIP的代码好相似，经常把他们搞混，多看看多记记吧。
4. 参考
- google_ortools_guide
大家看完记得关注点赞.
master苏.
推荐阅读：
