{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 批调度问题\n",
    "\n",
    "**类别：** 排程\n",
    "\n",
    "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n",
    "\n",
    "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/batch-scheduling-problem)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题描述\n",
    "\n",
    "**在批调度问题**中,一组任务必须在一组可用资源上以批次形式进行处理。同一批次中的任务会被一起处理,因此它们必须具有相同的时长、相同的类型以及相同的资源类型。资源之间互斥,同一时间只能处理一个批次。每个任务都有给定的资源类型、类型、时长以及若干后续任务。目标是最小化所有任务完成的总体时间(完工时间)。\n",
    "\n",
    "### 学习要点\n",
    "\n",
    "- 使用集合决策变量建模批次\n",
    "- 使用 [区间决策变量](https://optagent.pages.dev/guide/modeling/) 建模每个批次的时间范围\n",
    "- 使用 [distinct 算子](https://optagent.pages.dev/guide/modeling/) 与 [lambda 函数](https://optagent.pages.dev/guide/modeling/) 确保同一批次内的所有任务具有相同的类型\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 数据\n",
    "\n",
    "数据文件的格式如下:\n",
    "\n",
    "- 第一行:任务数量,资源数量\n",
    "- 第二行:每个资源的最大容量\n",
    "- 后续每一行对应一个任务:\n",
    "\n",
    "- 其关联的资源类型\n",
    "- 其类型\n",
    "- 其时长\n",
    "- 其后续任务数量\n",
    "- 其每个后续任务的 ID\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6454a944",
   "metadata": {},
   "source": [
    "## 建模思路\n",
    "\n",
    "批调度问题的 OptAgent 模型使用集合决策变量来建模在每个资源上调度的批次。每个集合中的元素对应于该批次内任务的索引。使用 [**partition**](https://optagent.pages.dev/guide/modeling/) 算子,可以确保一个任务不会被分配到多个批次,且不会遗漏任何任务。\n",
    "\n",
    "同一批次内的所有任务必须具有相同的类型。使用 [**distinct**](https://optagent.pages.dev/guide/modeling/) 算子与 [lambda 函数](https://optagent.pages.dev/guide/modeling/),我们可以约束同一批次内的所有任务具有相同的类型。\n",
    "\n",
    "除集合外,我们还使用区间决策变量来建模每个批次的时间范围。为了确保每个资源上的批次互不重叠,我们通过优先约束对这些资源的批次区间进行排序。\n",
    "\n",
    "借助 [`find`](https://optagent.pages.dev/api/model-reference/#optagent.OptModel.find) 算子,我们可以检索包含每个任务的批次区间。然后我们可以约束该区间的长度等于任务的时长,并强制其后续任务的开始时间不早于该批次的结束时间。\n",
    "\n",
    "目标是最小化完工时间(makespan),即所有任务完成的时间。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7f113d4",
   "metadata": {},
   "source": [
    "## Python 实现\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "batch-model",
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "from optagent import OptModel, solve\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "def read_instance(filename):\n",
    "    # The import files follow the \"Taillard\" format\n",
    "    with open(filename, encoding=\"utf-8\") as f:\n",
    "        lines = f.readlines()\n",
    "\n",
    "    first_line = lines[0].split()\n",
    "    nb_tasks = int(first_line[0])\n",
    "    nb_resources = int(first_line[1])\n",
    "\n",
    "    second_line = lines[1].split()\n",
    "    capacity = [int(value) for value in second_line]\n",
    "\n",
    "    nb_tasks_per_resource = [0 for _ in range(nb_resources)]\n",
    "    types_in_resource = [[] for _ in range(nb_resources)]\n",
    "    tasks_in_resource = [[] for _ in range(nb_resources)]\n",
    "    task_index_in_resource = []\n",
    "    types, resources, duration, nb_successors = [], [], [], []\n",
    "    successors = [[] for _ in range(nb_tasks)]\n",
    "\n",
    "    for i in range(nb_tasks):\n",
    "        task_line = i + 2\n",
    "        task_information = lines[task_line].split()\n",
    "\n",
    "        types.append(int(task_information[0]))\n",
    "        resources.append(int(task_information[1]))\n",
    "        task_index_in_resource.append(nb_tasks_per_resource[resources[i]])\n",
    "        types_in_resource[resources[i]].append(types[i])\n",
    "        tasks_in_resource[resources[i]].append(i)\n",
    "        nb_tasks_per_resource[resources[i]] += 1\n",
    "\n",
    "        duration.append(int(task_information[2]))\n",
    "        nb_successors.append(int(task_information[3]))\n",
    "        for succeeding_task in task_information[4:]:\n",
    "            successors[i].append(int(succeeding_task))\n",
    "\n",
    "    time_horizon = sum(duration[t] for t in range(nb_tasks))\n",
    "\n",
    "    return (\n",
    "        nb_tasks,\n",
    "        nb_resources,\n",
    "        capacity,\n",
    "        types,\n",
    "        resources,\n",
    "        duration,\n",
    "        nb_successors,\n",
    "        successors,\n",
    "        nb_tasks_per_resource,\n",
    "        task_index_in_resource,\n",
    "        types_in_resource,\n",
    "        tasks_in_resource,\n",
    "        time_horizon,\n",
    "    )\n",
    "\n",
    "\n",
    "def main(instance_file, output_file=None, time_limit=60):\n",
    "    (\n",
    "        nb_tasks,\n",
    "        nb_resources,\n",
    "        capacity,\n",
    "        types,\n",
    "        resources,\n",
    "        duration,\n",
    "        nb_successors,\n",
    "        successors,\n",
    "        nb_tasks_per_resource,\n",
    "        task_index_in_resource,\n",
    "        types_in_resource,\n",
    "        tasks_in_resource,\n",
    "        time_horizon,\n",
    "    ) = read_instance(instance_file)\n",
    "\n",
    "    model = OptModel()\n",
    "\n",
    "    batch_content = [\n",
    "        [\n",
    "            model.set(nb_tasks_per_resource[r])\n",
    "            for b in range(nb_tasks_per_resource[r])\n",
    "        ]\n",
    "        for r in range(nb_resources)\n",
    "    ]\n",
    "    batch_content_arrays = [model.array(batch_content[r]) for r in range(nb_resources)]\n",
    "\n",
    "    for r in range(nb_resources):\n",
    "        model.constraint(\n",
    "            model.partition(batch_content_arrays[r])\n",
    "        )\n",
    "\n",
    "    types_in_resource_array = model.array(types_in_resource)\n",
    "    def resource_type_lambda(resource):\n",
    "        return model.lambda_function(lambda i: types_in_resource_array[resource][i])\n",
    "\n",
    "    for r in range(nb_resources):\n",
    "        resource_type_mapper = resource_type_lambda(r)\n",
    "        for batch in batch_content[r]:\n",
    "            model.constraint(\n",
    "                model.count(model.distinct(batch, resource_type_mapper)) <= 1,\n",
    "            )\n",
    "\n",
    "    for r in range(nb_resources):\n",
    "        for batch in batch_content[r]:\n",
    "            model.constraint(\n",
    "                model.count(batch) <= capacity[r]\n",
    "            )\n",
    "\n",
    "    batch_interval = [\n",
    "        [model.interval(0, time_horizon) for b in range(nb_tasks_per_resource[r])]\n",
    "        for r in range(nb_resources)\n",
    "    ]\n",
    "    batch_interval_arrays = [\n",
    "        model.array(batch_interval[r]) for r in range(nb_resources)\n",
    "    ]\n",
    "\n",
    "    for r in range(nb_resources):\n",
    "        for b in range(1, nb_tasks_per_resource[r]):\n",
    "            model.constraint(\n",
    "                batch_interval[r][b - 1] < batch_interval[r][b],\n",
    "            )\n",
    "\n",
    "    task_interval = [None for _ in range(nb_tasks)]\n",
    "    for t in range(nb_tasks):\n",
    "        r = resources[t]\n",
    "        b = model.find(batch_content_arrays[r], task_index_in_resource[t])\n",
    "        task_interval[t] = batch_interval_arrays[r][b]\n",
    "\n",
    "    for t in range(nb_tasks):\n",
    "        model.constraint(\n",
    "            task_interval[t].length() == duration[t]\n",
    "        )\n",
    "\n",
    "    for t in range(nb_tasks):\n",
    "        for s in successors[t]:\n",
    "            model.constraint(\n",
    "                task_interval[t] < task_interval[s]\n",
    "            )\n",
    "\n",
    "    makespan = model.max(\n",
    "        *(\n",
    "            batch_interval_arrays[r][i].end()\n",
    "            for r in range(nb_resources)\n",
    "            for i in range(nb_tasks_per_resource[r])\n",
    "        )\n",
    "    )\n",
    "    model.minimize(makespan)\n",
    "\n",
    "    solution = solve(model, time_limit_s=float(time_limit))\n",
    "    result_values = {'makespan': makespan.value, **{f'task_{t}': task_interval[t].value for t in range(nb_tasks)}}\n",
    "\n",
    "    lines = [\n",
    "        f\"Status = {solution.feasible}\",\n",
    "        f\"Makespan = {result_values['makespan']}\",\n",
    "    ]\n",
    "    if solution.feasible:\n",
    "        for r in range(nb_resources):\n",
    "            lines.append(f\"Resource {r}\")\n",
    "            for task in tasks_in_resource[r]:\n",
    "                interval = result_values[f\"task_{task}\"]\n",
    "                lines.append(f\"{task} {interval['start']} {interval['end']}\")\n",
    "\n",
    "    result_text = \"\\n\".join(lines)\n",
    "    print(result_text)\n",
    "    if output_file is not None:\n",
    "        Path(output_file).write_text(result_text + \"\\n\", encoding=\"utf-8\")\n",
    "    return solution\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "batch-runs",
   "metadata": {},
   "source": [
    "## 本地运行\n",
    "\n",
    "Notebook 直接调用 `main` 并显式传入实例路径。以下代码格相互独立，可以按需要单独运行；调整 `time_limit` 可以控制每个实例的求解时间。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "batch-instance-dir",
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "INSTANCE_DIR = Path.cwd() / \"instances\"\n",
    "print(\"Instances:\", INSTANCE_DIR)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "batch-run-5-2-000",
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_5_2_000 = main(INSTANCE_DIR / \"5_2-000.nfb\", time_limit=10)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bcac6a48",
   "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
}