我正在使用 google OR-Tools 来解决调度问题。
该设置有 6 个班次、3 个任务和 3 名工人。 （数字将来可能会发生变化。）
工人被命名为A、B、C。
数量是指完成该任务需要多少班次。（每个任务预定义。）
如果可能的话，我想编写一个约束，使得任务 1 仅由 1 个工作人员完成。并且 1 名工人不能在同一班次/时间内执行多项任务。
如何使用 google OR-Tools 编写这样的约束？
import pandas as pd
from ortools.sat.python import cp_model
""" Inputs """
num_workers = 3
num_shifts = 6
task_info = {
"task-1": 3,
"task-2": 3,
"task-3": 2,
}
""" Processing """
num_tasks = len(task_info)
quantities = list(task_info.values())
model = cp_model.CpModel()
shifts = {}
maximize_this = 0
for t in range(num_tasks):
for s in range(num_shifts):
for w in range(num_workers):
shifts[(t, s, w)] = model.NewBoolVar(f't{t} s{s} w{w}')
maximize_this += shifts[(t, s, w)]
for s in range(num_shifts):
for w in range(num_workers):
# Constraint: 1 worker in 1 shift can do at most 1 task of 1 quantity
model.Add(sum(shifts[(t, s, w)] for t in range(num_tasks)) <= 1)
for t in range(num_tasks):
# Constraint: 1 task is done by at most 1 worker in 1 shift
model.Add(sum(shifts[(t, s, w)] for w in range(num_workers)) <= 1)
# Constraint: 1 task of n quantity is done by 1 worker in n shifts
for t in range(num_tasks):
model.Add(sum(sum(shifts[(t, s, w)] for s in range(num_shifts))
for w in range(num_workers)) <= quantities[t])
# Constraint: 1 worker for 1 task if possible
# Need Suggestions
# To complete as many tasks as possible
model.Maximize(maximize_this)
solver = cp_model.CpSolver()
status = solver.Solve(model)
""" Output """
if status == cp_model.OPTIMAL:
alphabets = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
data = []
for t in range(num_tasks):
data_i = []
for s in range(num_shifts):
s_val = ""
for w in range(num_workers):
if solver.Value(shifts[(t, s, w)]) == 1:
s_val = f'{alphabets[w]}'
data_i.append(s_val)
data.append(data_i)
data = pd.DataFrame(
data,
index=list(task_info.keys()),
columns=[f'shift-{s}' for s in range(num_shifts)])
data["quantity"] = quantities
print(data)
else:
print("No solution found")
| shift-1 | shift-2 | shift-3 | shift-4 | shift-5 | shift-6 | 数量 | |
|---|---|---|---|---|---|---|---|
| 任务1 | B | B | B | 3 | |||
| 任务2 | C | A | A | 3 | |||
| 任务3 | A | B | 2 |
我想要的一个可能的输出如下表所示。
| shift-1 | shift-2 | shift-3 | shift-4 | shift-5 | shift-6 | 数量 | |
|---|---|---|---|---|---|---|---|
| 任务1 | A | A | A | 3 | |||
| 任务2 | B | B | B | 3 | |||
| 任务3 | C | C | 2 |
检查cph的答案后，我尝试写这个但无法完成......
for t in range(num_tasks):
for w in range(num_workers):
m_this = model.NewIntVar(0, num_shifts, "")
# model.Add(m_this == sum(shifts[(t, s, w)] for s in range(num_shifts)))
model.AddMaxEquality(m_this, [shifts[(t, s, w)] for s in range(num_shifts)])
m_others = model.NewIntVar(0, num_shifts, "")
# model.Add(m_others == sum(sum(shifts[(t, s, w1)] for s in range(num_shifts)) for w1 in range(num_workers) if w != w1))
model.AddMaxEquality(m_others, [shifts[(t, s, w1)] for s in range(num_shifts) for w1 in range(num_workers) if w != w1])
model.AddImplication(m_this, m_others.Not())
一个问题：为什么你的约束“n 数量的 1 项任务由 1 名工人在 n 班次中完成”使用 <= quantities[t] instead of == quantities[t]? Don't you want the number of shifts for the task to exactly equal the quantity? I guess it's because you are maximizing the number of task steps done during the shifts instead of minimizing the number of shifts required to finish all the defined tasks.
您正在寻找的约束可以用这样的元代码来表达：
For each worker w
For each task t
Let m_this = maximum value of all the shifts[(t, s, w)] for s = 1 to num_shifts
Let m_others = maximum value of all the shifts[(t, s, w1)] for s = 1 to num_shifts and w1 = 1 to num_workers, except where w1 = w
Add the constraint (m_this implies not m_others)
我对 Python 完全是门外汉，但我相信你可以通过
model.AddMaxEquality(m_this, <list of the BoolVar's>)可以使用
model.AddImplication(m_this, m_others.Not())