1.2.1

下载 Notebook 下载完整案例

多模式资源受限项目调度问题 (MRCPSP)¶

类别： 排程

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

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

问题描述¶

在多模式资源受限项目调度问题 (MRCPSP) 中，一个项目由一组需要调度的任务组成。对每个任务，其执行过程不可中断，且可以采用不同的执行模式。任务之间存在紧前关系约束：每个任务必须在其所有后继任务开始之前完成。问题中有一组资源，分为可再生资源（任务处理完成后所有资源消耗会归还）和不可再生资源。对每种模式，每种任务执行都有给定的持续时间，并消耗给定数量的资源或权重（可能为零）。每种资源具有给定的最大容量：可以同时处理多个任务，但被处理任务权重之和不得超过该最大容量。

目标是找到一个使 makespan（所有任务处理完成的时间）最小的调度方案。

建模要点¶

• 添加 可选区间决策变量 来建模任务及其模式
• 使用 hull 独立于模式管理任务
• 定义 lambda 函数 来建模累计资源约束

数据¶

我们为多模式资源受限项目调度问题 (MRCPSP) 提供的实例来自 PSPLIB instances。数据文件的格式如下：

• 第 6 行包含作业或任务的数量。

• 第 9 行包含可再生资源的数量。

• 第 10 行包含不可再生资源的数量。

• 从第 19 行开始，每个任务占一行，按顺序包含以下整数数据：

• 任务 ID

• 该任务的执行模式数量

• 该任务的后继任务数量

• 该任务的后继任务 ID

• 然后，从下方第 5 行开始，对任务和模式的每个组合各占一行。每行按顺序包含与该配置（任务，模式）相关的整数数据：

• 任务 ID

• 模式 ID

• 该配置下的持续时间

• 该配置下每种资源的消耗权重

• 最后，再下方第 4 行，给出一行包含每种资源的最大容量。

建模思路¶

多模式资源受限项目调度问题 (MRCPSP) 的 OptAgent 模型是 RCPSP 模型 的扩展。它使用 可选区间决策变量 来表示不同执行模式下的任务。我们使用 presence 来检测每个任务的激活模式。最后，我们使用 ‘hull’ 算子独立于执行模式管理任务。

对于激活模式，每个区间的长度等于该任务在此模式下执行的持续时间。

然后，我们编写紧前关系约束：每个任务必须在其任何后继任务开始之前结束。

我们确保每个任务恰好有一种激活模式。这保证了所有任务都会被调度。

可再生资源约束可以表述如下：对每种可再生资源以及每个时间段，被处理任务所消耗的资源总量不得超过资源容量。为了建模这些约束，我们对每种资源和每个时间段，将所有激活模式下所有激活任务的权重求和。我们使用可变参数 ‘and’ 形式结合 lambda 函数 来确保任何时刻都满足资源容量限制。这种写法集中表达了各时间段的资源约束；实际求解开销取决于实例规模与求解配置。

不可再生资源约束由涉及每个配置（任务，模式）的 presence 的线性约束建模。

最后，目标是使 makespan 最小化。

Python 实现¶

from pathlib import Path

from optagent import OptModel, solve


def main(instance_file, output_file=None, time_limit=60):
    (
        nb_tasks, nb_renewable_resources, nb_resources, nb_modes, capacity,
        duration, weight, nb_successors, successors, horizon,
    ) = read_input(instance_file)
    model = OptModel()

    tasks_in_mode = [
        [
            model.optional_interval(0, horizon)
            for mode in range(nb_modes[task])
        ]
        for task in range(nb_tasks)
    ]
    present_mode = [
        [interval.presence() for interval in modes]
        for modes in tasks_in_mode
    ]
    tasks = [model.hull(modes) for modes in tasks_in_mode]

    for task in range(nb_tasks):
        for mode, interval in enumerate(tasks_in_mode[task]):
            model.constraint(
                model.iif(
                    present_mode[task][mode],
                    interval.length() == duration[task][mode],
                    True,
                ),
            )
        model.constraint(
            model.sum(*present_mode[task]) == 1,
        )

    for task in range(nb_tasks):
        for successor in successors[task]:
            model.constraint(tasks[task] < tasks[successor])

    makespan = model.max([task.end() for task in tasks])
    capacity_data = model.array(capacity)

    def resource_capacity(resource, time):
        weight_terms = []
        for task in range(nb_tasks):
            for mode in range(nb_modes[task]):
                weight_terms.append(
                    weight[task][resource][mode]
                    * model.contains(tasks_in_mode[task][mode], time // 1)
                )
        return model.sum(weight_terms) <= capacity_data[resource]

    def make_capacity_lambda(resource):
        return model.lambda_function(lambda time: resource_capacity(resource, time))

    for resource in range(nb_renewable_resources):
        capacity_lambda = make_capacity_lambda(resource)
        model.constraint(model.and_(model.range(makespan), capacity_lambda))

    for resource in range(nb_renewable_resources, nb_resources):
        weight_terms = []
        for task in range(nb_tasks):
            for mode in range(nb_modes[task]):
                weight_terms.append(
                    weight[task][resource][mode] * present_mode[task][mode]
                )
        model.constraint(model.sum(weight_terms) <= capacity_data[resource])

    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

    lines = [f"Makespan = {makespan.value}; Status = {solution.feasible}"]
    for task in range(nb_tasks):
        active_mode = next(
            mode for mode in range(nb_modes[task]) if present_mode[task][mode].value
        )
        interval_value = tasks[task].value
        lines.append(
            f"Task {task + 1}: mode={active_mode + 1}; "
            f"start={interval_value['start']}; end={interval_value['end']}"
        )
    result_text = "\n".join(lines)
    print(result_text)
    if output_file is not None:
        Path(output_file).write_text(result_text + "\n", encoding="utf-8")
    return solution


def read_input(filename):
    with open(filename) as file:
        lines = file.readlines()

    ## Parse number of tasks
    line = lines[5].split(":")
    nb_tasks = int(line[1])

    ## Parse number of resources
    line = lines[8].split(":")
    nb_renewable_resources = int(line[1].split()[0])

    line = lines[9].split(":")
    nb_non_renewable_resources = int(line[1].split()[0])
    nb_resources = nb_renewable_resources + nb_non_renewable_resources

    # Number of available modes for each task
    nb_modes = [0 for i in range(nb_tasks)]
    
    # Number of successors of each task
    nb_successors = [0 for i in range(nb_tasks)]

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

    ## Parse successors of each task
    line_index = 18
    line = lines[line_index].split()
    task_id = int(line[0]) - 1

    while True:
        nb_modes[task_id] = int(line[1])
        nb_successors[task_id] = int(line[2])
        successors[task_id] = [int(line[3 + s]) - 1 for s in range(nb_successors[task_id])]
        if task_id + 1 == nb_tasks:
            break
        line_index = line_index + 1
        line = lines[line_index].split()
        task_id = int(line[0]) - 1
    
    ## Parse tasks durations per mode AND consumed resource weight per mode for each task
    line_index = line_index + 5
    
    # Duration of each task and mode
    duration = [[] for i in range(nb_tasks)]

    # Required resource weight for each task and mode
    weight = [[[]] for i in range(nb_tasks)]

    for task in range(nb_tasks):
        weight[task] = [[0 for m in range(nb_modes[task])] for r in range(nb_resources)]
        duration[task] = [0 for m in range(nb_modes[task])]
        for mode in range(nb_modes[task]):
            line = lines[line_index].split()
            base_index = 1 if mode == 0 else 0
            duration[task][mode] = int(line[base_index + 1])
            for resource in range(nb_resources):
                weight[task][resource][mode] = int(line[base_index + 2 + resource])
            line_index = line_index + 1

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

    # Trivial upper bound for the start times of the tasks
    horizon = sum(max(duration[task][mode] for mode in range(nb_modes[task])) for task in range(nb_tasks))

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

本地运行¶

以下代码格演示如何调用 OptAgent 的多模式项目调度模型。

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

solution_j3010 = main(INSTANCE_DIR / "j3010_5.mm", time_limit=1)