1.2.1

下载 Notebook 下载完整案例

随机作业车间调度问题¶

类别： 排程

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

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

问题描述¶

在作业车间调度问题中，一组作业必须在车间中的每台机器上完成加工。每个作业由若干按顺序排列的任务（称为活动）组成。一个活动表示该作业在某台机器上的加工过程，并具有给定的加工时间。每个作业在每台机器上都有一个活动，且每个活动只能在其前一个活动结束之后才能开始。每台机器同一时刻只能处理一个活动。在本例中，我们考虑带有多场景的作业车间调度问题的随机版本：每个活动的加工时间在不同场景下会有所不同。对于给定的作业加工顺序和给定的场景，makespan 是所有作业加工完成的时间。本问题的目标是寻找一种作业顺序，使得所有场景下的最大 makespan 最小化。

学习要点¶

• 使用 OptAgent 的 interval 决策变量表示各场景中的活动
• 使用 list 决策变量表示每台机器共享的作业加工顺序
• 使用 lambda 将机器顺序与不同场景中的 interval 约束关联起来

数据¶

数据文件的格式如下：

• 第一行：作业数、机器数、场景数
• 对每个场景：每个作业依次给出其在加工顺序中各机器上的加工时间
• 最后对每个作业给出固定的机器加工顺序，该顺序在所有场景中相同

建模思路¶

每个场景、作业和机器对应一个 interval，其长度等于该场景下的加工时间；同一作业的 interval 按给定机器顺序建立紧前约束。

每台机器使用一个包含全部作业的 list 表示加工顺序，且该顺序由所有随机场景共享。对每个场景和机器，lambda 约束 list 中相邻作业的 interval 不重叠。每个场景的 makespan 是所有作业最后一道活动结束时间的最大值，目标是最小化所有场景 makespan 的最大值。

Python 实现¶

from pathlib import Path

from optagent import OptModel, solve


def read_instance(filename):
    lines = Path(filename).read_text(encoding="utf-8").splitlines()
    nb_jobs, nb_machines, nb_scenarios = map(int, lines[1].split())

    processing_times_in_order = [
        [
            [
                int(lines[scenario * (nb_jobs + 1) + row].split()[machine])
                for machine in range(nb_machines)
            ]
            for row in range(3, 3 + nb_jobs)
        ]
        for scenario in range(nb_scenarios)
    ]

    machine_order_start = 4 + nb_scenarios * (nb_jobs + 1)
    machine_order = [
        [int(lines[row].split()[machine]) - 1 for machine in range(nb_machines)]
        for row in range(machine_order_start, machine_order_start + nb_jobs)
    ]

    # processing_times[s][j][m] is the duration on machine m.
    processing_times = [
        [
            [
                processing_times_in_order[scenario][job][
                    machine_order[job].index(machine)
                ]
                for machine in range(nb_machines)
            ]
            for job in range(nb_jobs)
        ]
        for scenario in range(nb_scenarios)
    ]
    max_end = max(
        sum(sum(processing_times[scenario][job]) for job in range(nb_jobs))
        for scenario in range(nb_scenarios)
    )
    return (
        nb_jobs,
        nb_machines,
        nb_scenarios,
        processing_times,
        machine_order,
        max_end,
    )


def main(input_file, output_file=None, time_limit=20):
    (
        nb_jobs,
        nb_machines,
        nb_scenarios,
        processing_times,
        machine_order,
        max_end,
    ) = read_instance(input_file)

    model = OptModel()

    # tasks[s][j][m] is job j's interval on machine m in scenario s.
    tasks = [
        [
            [
                model.interval(
                    0, max_end
                )
                for machine in range(nb_machines)
            ]
            for job in range(nb_jobs)
        ]
        for scenario in range(nb_scenarios)
    ]

    for scenario in range(nb_scenarios):
        for job in range(nb_jobs):
            for machine in range(nb_machines):
                model.constraint(
                    tasks[scenario][job][machine].length()
                    == processing_times[scenario][job][machine],
                )

    task_array = model.array(
        [
            model.array(
                [model.array(job_tasks) for job_tasks in scenario_tasks]
            )
            for scenario_tasks in tasks
        ]
    )

    # Respect each job's fixed machine-processing order in every scenario.
    for scenario in range(nb_scenarios):
        for job in range(nb_jobs):
            for operation in range(nb_machines - 1):
                before = machine_order[job][operation]
                after = machine_order[job][operation + 1]
                model.constraint(
                    tasks[scenario][job][before]
                    < tasks[scenario][job][after],
                )

    # The machine order is shared by all processing-time scenarios.
    jobs_order = [
        model.list(nb_jobs)
        for machine in range(nb_machines)
    ]

    def make_sequence_lambda(sequence, scenario, machine):
        return model.lambda_function(
            lambda position: task_array[
                scenario, sequence[position], machine
            ]
            < task_array[scenario, sequence[position + 1], machine]
        )

    for machine, sequence in enumerate(jobs_order):
        model.constraint(
            sequence.count() == nb_jobs,
        )
        for scenario in range(nb_scenarios):
            precedes_next = make_sequence_lambda(
                sequence, scenario, machine
            )
            model.constraint(
                model.and_(model.range(0, nb_jobs - 1), precedes_next),
            )

    makespans = [
        model.max(
            [
                tasks[scenario][job][machine_order[job][-1]].end()
                for job in range(nb_jobs)
            ]
        )
        for scenario in range(nb_scenarios)
    ]
    max_makespan = model.max(makespans)
    model.minimize(max_makespan)

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

    final_jobs_order = [list(sequence.value) for sequence in jobs_order]
    output_lines = [
        " ".join(str(job) for job in sequence)
        for sequence in final_jobs_order
    ]
    display_lines = [
        f"Maximum makespan = {max_makespan.value}; Status = {solution.status}"
    ]
    display_lines.extend(
        f"Machine {machine}: {line}"
        for machine, line in enumerate(output_lines)
    )
    print("\n".join(display_lines))

    if output_file is not None:
        Path(output_file).write_text(
            "\n".join(output_lines) + "\n", encoding="utf-8"
        )
    return solution

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

solution_ft20_10 = main(
    INSTANCE_DIR / "ft20_10.txt",
    time_limit=1,
)