1.2.1

下载 Notebook 下载完整案例

可抢占资源约束项目调度问题 (PRCPSP)¶

类别： 排程

使用 OptAgent 的 Python 接口描述变量、约束与目标。

问题与原始示例来源：Hexaly Code Templates。

问题描述¶

在可抢占资源约束项目调度问题 (PRCPSP) 中，一个项目由一组需要调度的任务组成。每个任务都有一个给定的持续时间，并且可以被中断。任务之间存在优先级约束：每个任务必须在其所有后继任务开始之前结束。问题涉及一组可再生资源。每个任务对每种资源都有一个给定的资源需求或权重（可能为零），表示该任务在执行过程中消耗的资源量。每种资源都有一个给定的最大容量：它可以同时处理多个任务，但被处理任务的权重之和不能超过该最大容量。目标是找到一个调度方案，使完工时间（makespan）最小：即所有任务处理完成的时间。

学习要点¶

• 通过将每个任务拆分为子任务来放宽抢占约束
• 添加 区间决策变量 来建模子任务
• 定义 符号 Lambda 函数 来建模累积资源约束

数据¶

我们提供的 可抢占资源约束项目调度问题 (PRCPSP) 实例遵循 Patterson [1] 格式：

• 第一行：

• 任务数量（包括两个额外的持续时间为 0 的虚拟任务：源和汇）

• 可再生资源的数量

• 第二行：每种资源的最大容量

• 从第三行开始，对于每个任务：

• 任务的持续时间

• 每种资源的资源需求（权重）

• 后继任务的数量

• 每个后继任务的 ID

建模思路¶

我们考虑 可抢占资源约束项目调度问题 (PRCPSP) 的伪抢占版本，其中每个任务最多可被拆分为 N 个子任务，N 为一个常数。该问题的 OptAgent 模型使用 N 个 区间决策变量 来表示每个任务的子任务。对于每个任务，我们约束其所有子任务 interval 长度之和等于该任务的总持续时间。

为了使建模更简洁，我们对每个任务的抢占 interval 施加一个顺序。然后我们写出任务间的优先级约束：每个任务的最后一个子任务必须在其任何后继任务的第一个子任务开始之前结束。

累积资源约束可以表述如下：对于每种资源以及每个时间槽 t，正在处理的任务所消耗的资源量不能超过该资源的容量。为了建模这些约束，我们对每种资源和每个时间槽的所有活跃任务的权重进行求和。我们使用可变参数的 ‘and’ 公式结合 符号 Lambda 函数，以确保资源容量在任何时刻都被满足。这种写法集中表达了各时间段的资源约束；实际求解开销取决于实例规模与求解配置。

需要最小化的完工时间（makespan）是所有任务结束的时间。

[1] Patterson, J. H.,( 1984), A comparison of exact approaches for solving the multiple constrained resource, Project Scheduling Problem, Management Science, Vol. 30, p854-867

Python 实现¶

# Copyright (c) Hexaly. Permission is hereby granted to use, copy,
# and modify this code for applications developed with Hexaly.
from pathlib import Path

from optagent import OptModel, solve


# The input files follow the "Patterson" format
def read_instance(filename):
    lines = Path(filename).read_text(encoding="utf-8").splitlines()

    first_line = lines[0].split()

    # Number of tasks
    nb_tasks = int(first_line[0])

    # Number of resources
    nb_resources = int(first_line[1])

    # Maximum capacity of each resource
    capacity = [int(lines[1].split()[r]) for r in range(nb_resources)]

    # Duration of each task
    duration = [0 for i in range(nb_tasks)]

    # Resource weight of resource r required for task i
    weight = [[] for i in range(nb_tasks)]

    # Number of successors
    nb_successors = [0 for i in range(nb_tasks)]

    # Successors of each task i
    successors = [[] for i in range(nb_tasks)]

    for i in range(nb_tasks):
        line = lines[i + 2].split()
        duration[i] = int(line[0])
        weight[i] = [int(line[r + 1]) for r in range(nb_resources)]
        nb_successors[i] = int(line[nb_resources + 1])
        successors[i] = [int(line[nb_resources + 2 + s]) - 1 for s in range(nb_successors[i])]

    # Trivial upper bound for the end times of the tasks
    horizon = sum(duration[i] for i in range(nb_tasks))

    # Number of intervals authorized for each task (pseudo preemption)
    max_nb_preemptions = 4 

    return (nb_tasks, nb_resources, capacity, duration, weight, nb_successors, successors, horizon, max_nb_preemptions)


def main(instance_file, output_file=None, time_limit=60):
    nb_tasks, nb_resources, capacity, duration, weight, nb_successors, successors, horizon, max_nb_preemptions = read_instance(
        instance_file)

    model = OptModel()

        # Interval decisions: time range of each task
        # Each task can be split into max_nb_preemtptions subtasks
    tasks = [
        [
            model.interval(0, horizon)
            for t in range(max_nb_preemptions)
        ]
        for i in range(nb_tasks)
    ]

    for i in range(nb_tasks):
            # Task duration constraints
        model.constraint(
            model.sum(tasks[i][t].length() for t in range(max_nb_preemptions)) == duration[i]
        )
            
            # Precedence constraints between each task's subtasks
        for t in range(max_nb_preemptions - 1):
            model.constraint(tasks[i][t] < tasks[i][t + 1])
           
        # Precedence constraints between the tasks
    for i in range(nb_tasks):
        for s in range(nb_successors[i]):
            model.constraint(tasks[i][max_nb_preemptions - 1] < tasks[successors[i][s]][0])

        # Makespan: end of the last task
    makespan = model.max([tasks[i][max_nb_preemptions - 1].end() for i in range(nb_tasks)])

        # Cumulative resource constraints
    for r in range(nb_resources):
        capacity_respected = model.lambda_function(
            lambda t: model.sum(
                weight[i][r] * model.contains(tasks[i][k], t // 1)
                for i in range(nb_tasks)
                for k in range(max_nb_preemptions)
            ) <= capacity[r]
        )
        model.constraint(model.and_(model.range(makespan), capacity_respected))

        # Minimize the makespan
    model.minimize(makespan)
    solution = solve(model, time_limit_s=float(time_limit))
    if not solution.feasible:
        print(f"No feasible schedule found; Status = {solution.feasible}")
        return solution

        #
        # Write the solution in a file with the following format:
        # - total makespan
        # - for each task, the task id, the start and end times of each subtask
        #
    if output_file is not None:
        output_path = Path(output_file)
        with output_path.open("w", encoding="utf-8") as f:
            print("Solution written in file", output_path)
            f.write(str(makespan.value) + "\n")
            for i in range(nb_tasks):
                f.write(str(i + 1))
                for k in range(max_nb_preemptions):
                    start = tasks[i][k].value.start()
                    end = tasks[i][k].value.end()
                    if end != start:
                        f.write(f" ({start} {end})")
                f.write("\n")
    return solution

实例调用¶

下面使用仓库提供的 Patterson 格式实例运行模型。

INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)

solution_prcpsp = main(INSTANCE_DIR / "Pat1.rcp", time_limit=1)
solution_prcpsp.feasible