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蘇.
推薦閱讀：
