{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 烤箱调度问题 (OSP)\n", "\n", "**类别：** 排程\n", "\n", "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n", "\n", "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/oven-scheduling-problem-osp)。\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 问题描述\n", "\n", "在烤箱调度问题 (OSP) 中，一组作业必须被分配到烤箱、组合成批次，并在有限的时间范围内调度。每个作业具有释放日期、截止日期、尺寸、处理时间范围以及一个属性。每台烤箱具有初始属性、容量以及可用时间段。\n", "\n", "同一批次中的作业必须具有相同的属性。此外，同一烤箱上的连续批次可能需要依赖于其属性的准备时间和准备成本。\n", "\n", "目标是最小化四个准则的加权和：使用批次的总处理时间、延迟作业的数量、准备成本以及准备时间。\n", "\n", "### 建模要点\n", "\n", "- 使用 [set 决策变量](https://optagent.pages.dev/guide/modeling/) 建模批次的内容\n", "- 添加 [区间决策变量](https://optagent.pages.dev/guide/modeling/) 建模批次\n", "- 使用 [lambda 函数](https://optagent.pages.dev/guide/modeling/) 和 [`step_array`](https://optagent.pages.dev/api/model-reference/#optagent.OptModel.step_array) 建模可用时间段\n", "- 使用 [‘distinct’ 算子](https://optagent.pages.dev/guide/modeling/) 和 [lambda 函数](https://optagent.pages.dev/guide/modeling/) 确保同一批次中的所有作业具有相同类型\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 数据\n", "\n", "我们基于 [osp-ls](https://github.com/iolab-uniud/osp-ls/) 仓库中提供的实例给出了 OSP 输入文件，并采用了简化的格式以便于模型输入。\n", "\n", "每个实例包含：\n", "\n", "- 调度时间范围\n", "- 属性的数量\n", "- 准备成本矩阵\n", "- 准备时间矩阵\n", "- 烤箱的数量\n", "- 每台烤箱的最小和最大容量\n", "- 每台烤箱的初始属性\n", "- 每台烤箱的可用时间段\n", "- 作业数量\n", "- 每个作业可用的烤箱\n", "- 每个作业的释放日期和截止日期\n", "- 每个作业的最小和最大处理时间\n", "- 每个作业的尺寸和属性\n", "- 目标权重\n", "\n", "输入仅为实际目标属性（从 1 开始）提供准备值。相反，属性 0 对应空批次。因此，到空批次的转换的准备时间和准备成本均为零。\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 建模思路\n", "\n", "烤箱调度问题 (OSP) 的 OptAgent 模型使用 set 和区间决策变量。对每台烤箱，它创建固定数量的潜在批次。批次变量存储在一个扁平 list 中，然后按烤箱和批次位置被看作二维结构，这使得排序、准备和容量约束更容易表达。\n", "\n", "每个批次有一个 set 变量表示分配给它的作业，以及一个区间变量表示其处理时间。set 变量构成一个 partition，以确保我们将每个作业分配到恰好一个批次。[`find`](https://optagent.pages.dev/api/model-reference/#optagent.OptModel.find) 算子用于识别每个作业所属的批次，并将其链接到相应的区间。\n", "\n", "对每个批次，模型计算其总尺寸和属性。批次尺寸不得超过烤箱容量，批次中的所有作业必须具有相同的属性，并且每个作业只能分配到一台可用的烤箱。\n", "\n", "在每台烤箱上，连续批次必须遵守依赖于序列的准备时间。空批次放在非空批次之后。\n", "\n", "烤箱的可用性由 [`step_array`](https://optagent.pages.dev/api/model-reference/#optagent.OptModel.step_array) 表示，这些数组根据可用时间段构建。对每个使用的批次，其准备和处理过程都必须适合一个可用的时间段。\n", "\n", "目标是使用批次的总处理时间、延迟作业的数量、准备成本以及准备时间的加权和。\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Python 实现\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from pathlib import Path\n", "\n", "from optagent import OptModel, solve\n", "\n", "\n", "def read_integers(filename):\n", " return [\n", " int(x)\n", " for x in Path(filename).read_text(encoding=\"utf-8\").split()\n", " ]\n", "\n", "\n", "#\n", "# Create a step array from a dense array\n", "#\n", "def create_step_array(model, dense_array, horizon):\n", " indexes = []\n", " values = []\n", " value = dense_array[0]\n", " for t in range(1, horizon):\n", " if dense_array[t] != value:\n", " indexes.append(t)\n", " values.append(value)\n", " value = dense_array[t]\n", " indexes.append(horizon)\n", " values.append(value)\n", " return model.step_array(model.array(indexes), model.array(values))\n", "\n", "\n", "class _OptAgentRunner:\n", " \"\"\"Keep the original model block's lifecycle while using OptAgent.\"\"\"\n", "\n", " def __init__(self, time_limit):\n", " self.model = OptModel()\n", " self.time_limit = time_limit\n", "\n", " def __enter__(self):\n", " return self\n", "\n", " def __exit__(self, exc_type, exc_value, traceback):\n", " return False\n", "\n", " def solve(self):\n", " return solve(self.model, time_limit_s=float(self.time_limit))\n", "\n", "#\n", "# Read instance data from the input file\n", "#\n", "def main(input_file, output_file=None, time_limit=60):\n", " values = iter(read_integers(input_file))\n", "\n", " horizon = next(values)\n", " nb_attributes = next(values)\n", "\n", " # Attribute 0 is reserved for empty batches\n", " empty_attribute = 0\n", "\n", " # Input only provides setup values for real destination attributes;\n", " # transitions to empty batches are set to zero\n", " setup_costs_matrix = [\n", " [0 for _ in range(nb_attributes + 1)] for _ in range(nb_attributes + 1)\n", " ]\n", " for a1 in range(nb_attributes + 1):\n", " for a2 in range(nb_attributes + 1):\n", " setup_costs_matrix[a1][a2] = (\n", " 0 if a2 == empty_attribute else next(values)\n", " )\n", " setup_times_matrix = [\n", " [0 for _ in range(nb_attributes + 1)] for _ in range(nb_attributes + 1)\n", " ]\n", " for a1 in range(nb_attributes + 1):\n", " for a2 in range(nb_attributes + 1):\n", " setup_times_matrix[a1][a2] = (\n", " 0 if a2 == empty_attribute else next(values)\n", " )\n", " nb_machines = next(values)\n", " machine_min_capacity = [next(values) for _ in range(nb_machines)]\n", " machine_max_capacity = [next(values) for _ in range(nb_machines)]\n", " machine_initial_attribute = [next(values) for _ in range(nb_machines)]\n", " nb_availabilities = next(values)\n", " availability_start = [\n", " [next(values) for _ in range(nb_availabilities)]\n", " for _ in range(nb_machines)\n", " ]\n", " availability_end = [\n", " [next(values) for _ in range(nb_availabilities)]\n", " for _ in range(nb_machines)\n", " ]\n", " nb_jobs = next(values)\n", " machine_eligibility = [\n", " [False for _ in range(nb_machines)] for _ in range(nb_jobs)\n", " ]\n", " for j in range(nb_jobs):\n", " nb_eligible = next(values)\n", " for _ in range(nb_eligible):\n", " machine_id = next(values)\n", " # The machine IDs in the input start at 1\n", " machine_eligibility[j][machine_id - 1] = True\n", " job_release_date = [next(values) for _ in range(nb_jobs)]\n", " job_due_date = [next(values) for _ in range(nb_jobs)]\n", " job_min_processing_time = [next(values) for _ in range(nb_jobs)]\n", " job_max_processing_time = [next(values) for _ in range(nb_jobs)]\n", " job_size = [next(values) for _ in range(nb_jobs)]\n", " job_attribute = [next(values) for _ in range(nb_jobs)]\n", " upper_bound_integer_objective = next(values)\n", " weight_batch_processing_time = next(values)\n", " weight_tardy_jobs = next(values)\n", " weight_setup_times = next(values)\n", " weight_setup_costs = next(values)\n", "\n", " #\n", " # Preprocess instance data\n", " #\n", " # Create availability arrays from availability windows\n", " availabilities_dense = [\n", " [0 for _ in range(horizon)] for _ in range(nb_machines)\n", " ]\n", " for m in range(nb_machines):\n", " for a in range(nb_availabilities):\n", " for t in range(availability_start[m][a], availability_end[m][a]):\n", " availabilities_dense[m][t] = 1\n", "\n", " # Worst case: one job per batch and per machine\n", " nb_max_batch = nb_jobs\n", " nb_total_batch = nb_machines * nb_max_batch\n", "\n", " with _OptAgentRunner(time_limit) as optimizer:\n", " #\n", " # Declare the optimization model\n", " #\n", " model = optimizer.model\n", "\n", " setup_costs_array = model.array(setup_costs_matrix)\n", " setup_times_array = model.array(setup_times_matrix)\n", " job_size_array = model.array(job_size)\n", " job_attribute_array = model.array(job_attribute)\n", " job_release_date_array = model.array(job_release_date)\n", " job_due_date_array = model.array(job_due_date)\n", " job_min_processing_time_array = model.array(job_min_processing_time)\n", " job_max_processing_time_array = model.array(job_max_processing_time)\n", " machine_max_capacity_array = model.array(machine_max_capacity)\n", " machine_initial_attribute_array = model.array(machine_initial_attribute)\n", "\n", " # Convert availability arrays into step arrays to save space\n", " availabilities = [\n", " create_step_array(model, availabilities_dense[m], horizon)\n", " for m in range(nb_machines)\n", " ]\n", "\n", " # Set decisions: jobs assigned to each batch\n", " batch_content = [model.set(nb_jobs) for _ in range(nb_total_batch)]\n", "\n", " # Interval decisions: time range of each batch\n", " batch_interval = [\n", " model.interval(0, horizon) for _ in range(nb_total_batch)\n", " ]\n", "\n", " # Each job must be assigned to exactly one batch\n", " model.constraint(model.partition(batch_content))\n", "\n", " # View batches by machine and batch position\n", " machine_batch_content = [\n", " [batch_content[m * nb_max_batch + b] for b in range(nb_max_batch)]\n", " for m in range(nb_machines)\n", " ]\n", "\n", " # View time ranges by machine and batch position\n", " machine_batch_interval = [\n", " [batch_interval[m * nb_max_batch + b] for b in range(nb_max_batch)]\n", " for m in range(nb_machines)\n", " ]\n", "\n", " # Total size of each batch\n", " size_lambda = model.lambda_function(lambda j: job_size_array[j // 1])\n", " machine_batch_size = [\n", " [\n", " model.sum(machine_batch_content[m][b], size_lambda)\n", " for b in range(nb_max_batch)\n", " ]\n", " for m in range(nb_machines)\n", " ]\n", "\n", " # Identify non-empty batches\n", " machine_batch_used = [\n", " [\n", " model.count(machine_batch_content[m][b]) > 0\n", " for b in range(nb_max_batch)\n", " ]\n", " for m in range(nb_machines)\n", " ]\n", "\n", " # Identify common attribute of each batch\n", " attribute_lambda = model.lambda_function(\n", " lambda j: job_attribute_array[j // 1]\n", " )\n", " machine_batch_type = [\n", " [\n", " model.iif(\n", " machine_batch_used[m][b],\n", " model.min(machine_batch_content[m][b], attribute_lambda),\n", " empty_attribute,\n", " )\n", " for b in range(nb_max_batch)\n", " ]\n", " for m in range(nb_machines)\n", " ]\n", "\n", " # Batch selected for each job\n", " batch_content_array = model.array(batch_content)\n", " job_index = [model.find(batch_content_array, j) for j in range(nb_jobs)]\n", "\n", " # Jobs in the same batch share the same time range\n", " batch_interval_array = model.array(batch_interval)\n", " job_interval = [\n", " batch_interval_array[job_index[j]] for j in range(nb_jobs)\n", " ]\n", " for j in range(nb_jobs):\n", " # Jobs cannot start before their release date\n", " model.constraint(\n", " model.start(job_interval[j]) >= job_release_date_array[j]\n", " )\n", "\n", " # Batch length must satisfy each assigned job\n", " model.constraint(\n", " model.length(job_interval[j])\n", " >= job_min_processing_time_array[j]\n", " )\n", " model.constraint(\n", " model.length(job_interval[j])\n", " <= job_max_processing_time_array[j]\n", " )\n", "\n", " for j in range(nb_jobs):\n", " for m in range(nb_machines):\n", " if not machine_eligibility[j][m]:\n", " for b in range(nb_max_batch):\n", " # Jobs can only be assigned to eligible machines\n", " model.constraint(\n", " model.not_(\n", " model.contains(machine_batch_content[m][b], j)\n", " )\n", " )\n", "\n", " for b in range(nb_total_batch):\n", " # Each batch must consist of jobs with the same type\n", " model.constraint(\n", " model.count(model.distinct(batch_content[b], attribute_lambda))\n", " <= 1\n", " )\n", "\n", " for m in range(nb_machines):\n", " for b in range(nb_max_batch):\n", " # Batch size cannot exceed the machine capacity\n", " model.constraint(\n", " machine_batch_size[m][b] <= machine_max_capacity_array[m]\n", " )\n", "\n", " for m in range(nb_machines):\n", " for b in range(1, nb_max_batch):\n", " prev_attribute = machine_batch_type[m][b - 1]\n", " next_attribute = machine_batch_type[m][b]\n", " setup_time = setup_times_array[prev_attribute][next_attribute]\n", "\n", " # Non-overlap between batches, with sequence-dependent setup times\n", " model.constraint(\n", " model.end(machine_batch_interval[m][b - 1]) + setup_time\n", " <= model.start(machine_batch_interval[m][b])\n", " )\n", "\n", " # Empty batches must be last to keep setups between non-empty batches\n", " model.constraint(\n", " model.or_(\n", " model.not_(machine_batch_used[m][b]),\n", " machine_batch_used[m][b - 1],\n", " )\n", " )\n", "\n", " for m in range(nb_machines):\n", " setup_time = setup_times_array[machine_initial_attribute_array[m]][\n", " machine_batch_type[m][0]\n", " ]\n", "\n", " # Account for the setup time before the first batch for each machine\n", " model.constraint(\n", " model.start(machine_batch_interval[m][0]) >= setup_time\n", " )\n", "\n", " # Setup costs between each batch\n", " machine_setup_costs = [None for _ in range(nb_machines)]\n", " for m in range(nb_machines):\n", " machine_setup_costs[m] = model.sum(\n", " [\n", " setup_costs_array\n", " [machine_batch_type[m][b - 1]]\n", " [machine_batch_type[m][b]]\n", " for b in range(1, nb_max_batch)\n", " ]\n", " )\n", "\n", " # Setup times between each batch\n", " machine_setup_times = [None for _ in range(nb_machines)]\n", " for m in range(nb_machines):\n", " machine_setup_times[m] = model.sum(\n", " [\n", " setup_times_array\n", " [machine_batch_type[m][b - 1]]\n", " [machine_batch_type[m][b]]\n", " for b in range(1, nb_max_batch)\n", " ]\n", " )\n", "\n", " for m in range(nb_machines):\n", " availability = availabilities[m]\n", " availability_lambda = model.lambda_function(\n", " lambda t: availability[t // 1]\n", " )\n", " for b in range(nb_max_batch):\n", " next_interval = machine_batch_interval[m][b]\n", " prev_attribute = model.iif(\n", " b == 0,\n", " empty_attribute,\n", " machine_batch_type[m][b - 1],\n", " )\n", " next_attribute = machine_batch_type[m][b]\n", " setup_time = setup_times_array[prev_attribute][next_attribute]\n", "\n", " # Setup and processing must fit in a single machine availability\n", " model.constraint(\n", " model.min(\n", " model.range(\n", " model.start(next_interval) - setup_time,\n", " model.end(next_interval),\n", " ),\n", " availability_lambda,\n", " )\n", " >= 1\n", " )\n", "\n", " # Total batch processing time\n", " batch_processing_time = model.sum(\n", " [\n", " machine_batch_used[m][b]\n", " * model.length(machine_batch_interval[m][b])\n", " for m in range(nb_machines)\n", " for b in range(nb_max_batch)\n", " ]\n", " )\n", "\n", " # Number of tardy jobs\n", " tardy_jobs = model.sum(\n", " [\n", " model.end(job_interval[j]) > job_due_date_array[j]\n", " for j in range(nb_jobs)\n", " ]\n", " )\n", "\n", " # Total setup costs\n", " setup_costs = model.sum(machine_setup_costs)\n", "\n", " # Total setup times\n", " setup_times = model.sum(machine_setup_times)\n", "\n", " # Minimize weighted processing time, tardy jobs, and setup costs\n", " objective = (\n", " weight_batch_processing_time * batch_processing_time\n", " + weight_tardy_jobs * tardy_jobs\n", " + weight_setup_costs * setup_costs\n", " + weight_setup_times * setup_times\n", " )\n", " model.minimize(objective)\n", "\n", " solution = optimizer.solve()\n", " if not solution.feasible:\n", " print(f\"No feasible schedule found; Status = {solution.feasible}\")\n", " return solution\n", "\n", " write_solution(\n", " output_file,\n", " nb_machines,\n", " nb_max_batch,\n", " machine_batch_used,\n", " machine_batch_interval,\n", " machine_batch_content,\n", " objective,\n", " )\n", " print(f\"Objective = {objective.value}; Status = {solution.feasible}\")\n", " return solution\n", "\n", "#\n", "# Write the solution in a file\n", "#\n", "def write_solution(\n", " output_file,\n", " nb_machines,\n", " nb_max_batch,\n", " machine_batch_used,\n", " machine_batch_interval,\n", " machine_batch_content,\n", " objective,\n", "):\n", " if output_file is None:\n", " return\n", " with open(output_file, \"w\") as sol_file:\n", " sol_file.write(\"Objective: %s\\n\" % objective.value)\n", " sol_file.write(\"Machine Start End Jobs\\n\")\n", " for m in range(nb_machines):\n", " for b in range(nb_max_batch):\n", " if not machine_batch_used[m][b].value:\n", " continue\n", " sol_file.write(\n", " \"Machine: %d | Start: %d | End: %d | Jobs: \"\n", " % (\n", " m + 1,\n", " machine_batch_interval[m][b].value.start(),\n", " machine_batch_interval[m][b].value.end(),\n", " )\n", " )\n", " for j in machine_batch_content[m][b].value:\n", " sol_file.write(\"%d \" % (j + 1))\n", " sol_file.write(\"\\n\")\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 本地运行\n", "\n", "在 notebook 所在目录执行以下 cell，即可调用一个小型炉窑排程实例。\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "INSTANCE_DIR = Path.cwd() / \"instances\"\n", "print(\"Instances:\", INSTANCE_DIR)\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "solution_osp_01 = main(INSTANCE_DIR / \"01-n10-k2-a2.dat\", time_limit=1)\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3" } }, "nbformat": 4, "nbformat_minor": 5 }