基于Python Pulp的时间范围任务分配：最小化资源数优化问询

问题概述 #

目标 #

最小化处理所有需求所需的资源数量。每个需求需分配至指定资源列表中的任一资源，按请求小时数分配时长，且必须在给定日期范围内完成（日期格式如24w211代表2024年第21周第1天，即周一）。

现有代码的局限 #

提供的Pulp代码仅从可用范围起始日期分配资源，无法在整个日期范围内选择最优起始日期来实现资源使用量最小化。例如：需求1需3周时长（120小时/40小时每周），可用范围是22W211至22W305，可选择的时间段包括22W211-22W235、22W221-22W245等，但现有代码无法自动挑选能让资源复用率最高的起始时间。

示例输入 #

优化后的解决方案 #

核心思路是确保代码遍历所有合法的起始日期（即需求可用范围内所有能容纳需求时长的起始点），并让线性规划模型自动选择能最大化资源复用的起始时间组合，从而最小化资源数量。

关键修改点 #

1. 统一日期转换逻辑：将22W211格式的日期转换为连续整数天数，方便计算时间范围和时长。
2. 修正起始日期遍历范围：确保遍历需求可用范围内所有合法的起始日期，即起始日期加上需求所需天数不超过需求的结束日期。
3. 优化约束条件：确保非重叠约束准确覆盖所有日期，避免逻辑漏洞。

完整优化代码 #

from pulp import LpProblem, LpVariable, LpBinary, lpSum, LpMinimize

def date_to_day_num(date_str):
    """将22W211格式的日期转换为连续整数天数（可根据实际日历规则调整）"""
    year = int(date_str[:2])
    week = int(date_str[3:5])
    day = int(date_str[5])
    # 假设每年52周，每周5个工作日（周一到周五），计算从基准年开始的总天数
    base_year = 2000
    years_diff = year - base_year
    total_days = years_diff * 52 * 5 + (week - 1) * 5 + (day - 1)
    return total_days

def solve_group(res_pool, reqs):
    # 预处理需求：转换日期为整数天数，计算需求所需天数
    processed_reqs = []
    for req in reqs:
        start_day = date_to_day_num(req['available_start'])
        end_day = date_to_day_num(req['available_end'])
        # 计算需求所需工作日天数：每天8小时，向上取整
        required_days = (req['hours_required'] + 7) // 8
        processed_reqs.append({
            'req_id': req['req_id'],
            'start_day': start_day,
            'end_day': end_day,
            'required_days': required_days,
            'pnos': req['resource_list']
        })

    # 初始化线性规划问题
    prob = LpProblem(f"Minimize_Resources_Group", LpMinimize)

    # 步骤1：定义决策变量
    # x[res, req_id, start_day] = 1 表示资源res被分配给需求req_id，从start_day开始执行
    x = {}
    for res in res_pool:
        for req in processed_reqs:
            # 遍历所有合法的起始日期：start_day + required_days -1 <= end_day
            max_start_day = req['end_day'] - req['required_days'] + 1
            for start_day in range(req['start_day'], max_start_day + 1):
                var_name = f"x_{res}_{req['req_id']}_{start_day}"
                x[(res, req['req_id'], start_day)] = LpVariable(var_name, 0, 1, LpBinary)

    # 步骤2：定义资源使用标记变量
    # used[res] = 1 表示资源res被使用
    used = {}
    for res in res_pool:
        used[res] = LpVariable(f"used_{res}", 0, 1, LpBinary)

    # 步骤3：目标函数：最小化使用的资源数量
    prob += lpSum(used[res] for res in res_pool), "Minimize_Number_of_Resources"

    # 步骤4：约束条件
    # 4.1 每个需求必须被恰好分配一次
    for req in processed_reqs:
        prob += lpSum(
            x[(res, req['req_id'], start_day)]
            for res in req['pnos']
            for start_day in range(req['start_day'], req['end_day'] - req['required_days'] + 2)
        ) == 1, f"Fulfill_Req_{req['req_id']}"

    # 4.2 同一资源在同一天只能处理一个需求（无重叠）
    # 先确定所有涉及的日期范围
    all_days = range(
        min(req['start_day'] for req in processed_reqs),
        max(req['end_day'] for req in processed_reqs) + 1
    )
    for res in res_pool:
        for day in all_days:
            prob += lpSum(
                x[(res, req['req_id'], start_day)]
                for req in processed_reqs
                for start_day in range(req['start_day'], req['end_day'] - req['required_days'] + 2)
                # 检查当前day是否在该需求的执行时间段内
                if start_day <= day <= start_day + req['required_days'] - 1
            ) <= 1, f"No_Overlap_{res}_{day}"

    # 4.3 资源使用标记与分配的关联：如果资源被分配了任何需求，则标记为已使用
    for res in res_pool:
        for req in processed_reqs:
            for start_day in range(req['start_day'], req['end_day'] - req['required_days'] + 2):
                prob += used[res] >= x[(res, req['req_id'], start_day)], f"Link_Usage_{res}_{req['req_id']}_{start_day}"

    # 步骤5：求解问题
    prob.solve()

    # 整理结果
    used_resources = [res for res in res_pool if used[res].value() == 1]
    assignments = []
    for (res, req_id, start_day), var in x.items():
        if var.value() == 1:
            req = next(r for r in processed_reqs if r['req_id'] == req_id)
            assignments.append({
                'resource': res,
                'req_id': req_id,
                'start_day': start_day,
                'end_day': start_day + req['required_days'] - 1
            })

    return prob, used_resources, assignments

代码解释 #

1. 日期转换函数：date_to_day_num将YYWDDD格式的日期转换为连续整数，方便时间范围和时长的计算（可根据实际日历规则调整，比如加入节假日逻辑）。
2. 需求预处理：统一计算每个需求所需的工作日天数，并转换日期格式，避免重复计算。
3. 起始日期遍历：通过max_start_day = req['end_day'] - req['required_days'] + 1确定每个需求的最晚合法起始日期，确保遍历所有可能的起始点。
4. 非重叠约束优化：遍历所有涉及的日期，准确判断每个需求的执行时间段是否覆盖当前日期，确保同一资源不会在同一天被重复分配。
5. 结果整理：返回已使用的资源列表和具体分配信息，方便后续查看。

验证示例 #

假设有3个需求：每个需求需1周（5天，40小时），时间范围为24w201至24w225（第20周到第22周的周一到周五）。优化后的代码会自动将三个需求分配给同一资源：

• 需求1：24w201（起始日）
• 需求2：24w211（起始日）
• 需求3：24w221（起始日）
  从而实现仅使用1个资源完成所有需求，达到资源最小化的目标。

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