流水车间调度问题¶

类别： 排程

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

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

问题描述¶

流水车间调度问题描述如下。一组作业必须按照预定义的顺序在每台机器上处理。每台机器一次只能处理一个作业。它们可以并行工作，但必须以相同的顺序处理所有作业。工作流程如下：序列的第一个作业到第一台机器上进行处理。当第一台机器处理完第一个作业后，该作业前往第二台机器，序列中的第二个作业开始在第一台机器上进行处理，依此类推。换言之，一个作业在一台机器上开始处理时，前提是该作业已经在前一台机器上结束，并且前一个作业已经在这台机器上结束。

问题的目标是找到一个作业序列，使 makespan（即所有作业处理完成的时间）最小化。该版本的流水车间调度问题也称为"置换流水车间问题"。

学习要点¶

添加列表决策变量来建模机器上作业的顺序
使用递归 Lambda 函数定义数组来计算活动的结束时间

数据¶

我们提供的流水车间调度问题实例来自 Taillard。数据文件的格式如下：

第一行：作业数、机器数、生成实例所用的种子，以及先前找到的上界和下界。
对于每台机器：每个作业在该机器上的处理时间。

建模思路¶

模型中唯一的决策变量是一个 list variable，对应于作业的序列。使用 count 算子，我们约束所有作业都必须被处理。

为了计算 makespan（最后结束时间），我们使用 array 算子递归计算所有活动的结束时间。在第一台机器上，每个作业在前一个作业结束后立即开始。我们使用递归 Lambda 函数来填充包含第一台机器上结束时间的数组：位置 i 处作业的结束时间是前一个作业的结束时间（prev）与其处理时间（processingTime[0][jobs[i]]）之和。

然后，我们可以计算后续机器上的结束时间。一个作业在其中一台机器上的开始时间是两个量的最大值：该作业在前一台机器上的结束时间，以及前一个作业在当前机器上的结束时间。与第一台机器类似，我们通过使用递归 Lambda 函数填充数组来计算其他机器上的结束时间。

需要最小化的 makespan 是序列中最后一个作业在最后一台机器上被处理完成的时间：end[nbMachines-1][nbJobs-1]。

Python 实现¶

from pathlib import Path

from optagent import OptModel, solve




def read_integers(filename):
    return [int(value) for value in Path(filename).read_text().split()]


def read_instance(instance_file):
    file_it = iter(read_integers(instance_file))

    nb_jobs = int(next(file_it))
    nb_machines = int(next(file_it))
    next(file_it)
    next(file_it)
    next(file_it)

    processing_time_data = [[int(next(file_it)) for _ in range(nb_jobs)] for _ in range(nb_machines)]

    return nb_jobs, nb_machines, processing_time_data


def main(instance_file, output_file=None, time_limit=5):
    nb_jobs, nb_machines, processing_time_data = read_instance(instance_file)

    model = OptModel()

    # Permutation of jobs. The initial value only seeds OptAgent; count remains
    # the model constraint that requires every job to appear.
    jobs = model.list(nb_jobs)
    model.constraint(model.eq(model.count(jobs), nb_jobs))

    processing_time = [model.array(processing_time_data[machine]) for machine in range(nb_machines)]

    # On machine 0, each job ends after the previous job plus its processing time.
    job_end = [None] * nb_machines
    first_end_lambda = model.lambda_function(lambda position, previous: previous + processing_time[0][jobs[position]])
    job_end[0] = model.array(model.range(0, nb_jobs), first_end_lambda, 0)

    # On later machines, a job waits for both the machine and its previous stage.
    def make_end_lambda(machine):
        return model.lambda_function(
            lambda i, previous: model.max(previous, job_end[machine - 1][i])
            + processing_time[machine][jobs[i]]
        )

    for machine in range(1, nb_machines):
        end_lambda = make_end_lambda(machine)
        job_end[machine] = model.array(model.range(0, nb_jobs), end_lambda, 0)

    makespan = job_end[nb_machines - 1][nb_jobs - 1]
    model.minimize(makespan)

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

    values = {'makespan': makespan.value, 'jobs': jobs.value}
    jobs_text = " ".join(map(str, values["jobs"]))
    print(f"Makespan = {values['makespan']}; Status = {solution.feasible}")
    print(jobs_text)
    if output_file is not None:
        Path(output_file).write_text(f"{int(values['makespan'])}\n{jobs_text}\n", encoding="utf-8")
    return solution

本地运行¶

INSTANCE_DIR = Path.cwd() / "instances"

solution = main(INSTANCE_DIR / "tai20_5.txt", time_limit=5)