如何在Google OR-Tools中实现最大用工量最小化的MILP建模

可行性说明 #

该需求完全可以通过Google OR-Tools实现。你遇到的Python原生max函数无法正常运行的问题，本质原因是：OR-Tools中的优化变量在求解前仅为逻辑占位符，没有实际数值，原生max函数无法处理这类变量，需要通过MILP领域通用的「辅助上界变量法」实现最小化最大值的逻辑。

核心实现思路 #

要实现最小化所有周次最大用工量的目标，不需要直接调用max函数，只需要：

1. 新增一个全局辅助变量max_worker，代表所有周的用工量上限
2. 添加约束：每一周的实际用工量都小于等于max_worker
3. 优化目标设置为最小化max_worker，求解得到的最优值就是最小的最大用工量

具体实现方案 #

这里提供一种对新手友好、不容易出错的枚举启动周实现方案，适合大部分中小规模场景：

变量定义 #

• 定义0-1变量z[i][s]：取值为1代表任务i选择在第s周启动，为0代表不选该启动时间
• 定义整数变量max_worker：全局最大用工量，即优化目标

约束条件 #

• 每个任务有且仅有一个启动时间：对每个任务i，所有可选启动周对应的z[i][s]之和等于1
• 每周实际用工量不超过上限：对每个周j，所有在本周执行的任务对应的用工量之和小于等于max_worker

可运行代码示例 #

from ortools.linear_solver import pywraplp

# 初始化MILP求解器（CBC为开源整数规划求解器）
solver = pywraplp.Solver.CreateSolver('CBC')

# -------------- 输入参数样例 --------------
T = 10  # 总周数上限
w = [2, 3, 2]  # 每个任务的耗时（单位：周）
# p[i][k]：任务i执行第k周（k从0开始）需要的工人数
p = [[3, 2], [4, 4, 2], [5, 1]]
task_count = len(w)

# -------------- 变量定义 --------------
# z[i][s]：任务i是否在第s周启动
z = []
for i in range(task_count):
    # 任务i的最晚启动周：保证可以在总周数内完成
    latest_start = T - w[i]
    z_i = [solver.IntVar(0, 1, f'z_{i}_{s}') for s in range(latest_start + 1)]
    z.append(z_i)
# 全局最大用工量，上界可根据实际用工最大值调整
max_worker = solver.IntVar(0, 1000, 'max_worker')

# -------------- 约束添加 --------------
# 约束1：每个任务必须选且仅选一个启动周
for i in range(task_count):
    solver.Add(sum(z[i][s] for s in range(len(z[i]))) == 1)

# 约束2：每周总用工量不超过max_worker
for j in range(T):
    week_total = 0
    for i in range(task_count):
        # 遍历任务i所有可选的启动周
        for s in range(len(z[i])):
            # 判断第j周是否在任务i的执行区间内
            if s <= j <= s + w[i] - 1:
                exec_week_idx = j - s
                week_total += z[i][s] * p[i][exec_week_idx]
    solver.Add(week_total <= max_worker)

# -------------- 求解与结果输出 --------------
solver.Minimize(max_worker)
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL:
    print(f"最小最大用工量：{int(max_worker.solution_value())}")
    for i in range(task_count):
        for s in range(len(z[i])):
            if z[i][s].solution_value() > 0.9:
                print(f"任务{i}启动周：{s}")
else:
    print("不存在可行解，请检查参数设置是否合理")

规模优化提示 #

如果你的任务数和总周数非常大（比如T>100，任务数>200），可以改用「启动周整数变量+执行状态指示变量+线性化约束」的方案减少变量数量，降低求解耗时。

内容的提问来源于stack exchange，提问作者N Fp