{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 流水车间调度问题\n", "\n", "**类别：** 排程\n", "\n", "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n", "\n", "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/flow-shop-problem)。\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 问题描述\n", "\n", "**流水车间调度问题**描述如下。一组作业必须按照预定义的顺序在每台机器上处理。每台机器一次只能处理一个作业。它们可以并行工作，但必须以相同的顺序处理所有作业。工作流程如下：序列的第一个作业到第一台机器上进行处理。当第一台机器处理完第一个作业后，该作业前往第二台机器，序列中的第二个作业开始在第一台机器上进行处理，依此类推。换言之，一个作业在一台机器上开始处理时，前提是该作业已经在前一台机器上结束，并且前一个作业已经在这台机器上结束。\n", "\n", "问题的目标是找到一个作业序列，使 makespan（即所有作业处理完成的时间）最小化。该版本的流水车间调度问题也称为\"置换流水车间问题\"。\n", "\n", "### 学习要点\n", "\n", "- 添加 [列表决策变量](https://optagent.pages.dev/guide/modeling/) 来建模机器上作业的顺序\n", "- 使用 [递归 Lambda 函数](https://optagent.pages.dev/guide/modeling/) 定义数组来计算活动的结束时间\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 数据\n", "\n", "我们提供的**流水车间调度问题**实例来自 [Taillard](http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html)。数据文件的格式如下：\n", "\n", "- 第一行：作业数、机器数、生成实例所用的种子，以及先前找到的上界和下界。\n", "- 对于每台机器：每个作业在该机器上的处理时间。\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 建模思路\n", "\n", "模型中唯一的决策变量是一个 [list variable](https://optagent.pages.dev/guide/modeling/)，对应于作业的序列。使用 **count** 算子，我们约束所有作业都必须被处理。\n", "\n", "为了计算 makespan（最后结束时间），我们使用 **array** 算子递归计算所有活动的结束时间。在第一台机器上，每个作业在前一个作业结束后立即开始。我们使用 [递归 Lambda 函数](https://optagent.pages.dev/guide/modeling/) 来填充包含第一台机器上结束时间的数组：位置 i 处作业的结束时间是前一个作业的结束时间（prev）与其处理时间（processingTime[0][jobs[i]]）之和。\n", "\n", "然后，我们可以计算后续机器上的结束时间。一个作业在其中一台机器上的开始时间是两个量的最大值：该作业在前一台机器上的结束时间，以及前一个作业在当前机器上的结束时间。与第一台机器类似，我们通过使用 递归 Lambda 函数 填充数组来计算其他机器上的结束时间。\n", "\n", "需要最小化的 makespan 是序列中最后一个作业在最后一台机器上被处理完成的时间：end[nbMachines-1][nbJobs-1]。\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", "\n", "\n", "def read_integers(filename):\n", " return [int(value) for value in Path(filename).read_text().split()]\n", "\n", "\n", "def read_instance(instance_file):\n", " file_it = iter(read_integers(instance_file))\n", "\n", " nb_jobs = int(next(file_it))\n", " nb_machines = int(next(file_it))\n", " next(file_it)\n", " next(file_it)\n", " next(file_it)\n", "\n", " processing_time_data = [[int(next(file_it)) for _ in range(nb_jobs)] for _ in range(nb_machines)]\n", "\n", " return nb_jobs, nb_machines, processing_time_data\n", "\n", "\n", "def main(instance_file, output_file=None, time_limit=5):\n", " nb_jobs, nb_machines, processing_time_data = read_instance(instance_file)\n", "\n", " model = OptModel()\n", "\n", " # Permutation of jobs. The initial value only seeds OptAgent; count remains\n", " # the model constraint that requires every job to appear.\n", " jobs = model.list(nb_jobs)\n", " model.constraint(model.eq(model.count(jobs), nb_jobs))\n", "\n", " processing_time = [model.array(processing_time_data[machine]) for machine in range(nb_machines)]\n", "\n", " # On machine 0, each job ends after the previous job plus its processing time.\n", " job_end = [None] * nb_machines\n", " first_end_lambda = model.lambda_function(lambda position, previous: previous + processing_time[0][jobs[position]])\n", " job_end[0] = model.array(model.range(0, nb_jobs), first_end_lambda, 0)\n", "\n", " # On later machines, a job waits for both the machine and its previous stage.\n", " def make_end_lambda(machine):\n", " return model.lambda_function(\n", " lambda i, previous: model.max(previous, job_end[machine - 1][i])\n", " + processing_time[machine][jobs[i]]\n", " )\n", "\n", " for machine in range(1, nb_machines):\n", " end_lambda = make_end_lambda(machine)\n", " job_end[machine] = model.array(model.range(0, nb_jobs), end_lambda, 0)\n", "\n", " makespan = job_end[nb_machines - 1][nb_jobs - 1]\n", " model.minimize(makespan)\n", "\n", " solution = solve(model, time_limit_s=float(time_limit))\n", " if not solution.feasible:\n", " print(f\"No feasible sequence found; Status = {solution.feasible}\")\n", " return solution\n", "\n", " values = {'makespan': makespan.value, 'jobs': jobs.value}\n", " jobs_text = \" \".join(map(str, values[\"jobs\"]))\n", " print(f\"Makespan = {values['makespan']}; Status = {solution.feasible}\")\n", " print(jobs_text)\n", " if output_file is not None:\n", " Path(output_file).write_text(f\"{int(values['makespan'])}\\n{jobs_text}\\n\", encoding=\"utf-8\")\n", " return solution\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 本地运行\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "INSTANCE_DIR = Path.cwd() / \"instances\"\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "solution = main(INSTANCE_DIR / \"tai20_5.txt\", time_limit=5)\n" ] }, { "cell_type": "code", "execution_count": null, "id": "80d513fd", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": ".venv", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.14.6" } }, "nbformat": 4, "nbformat_minor": 5 }