{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 并行机调度问题 (PMS)\n",
    "\n",
    "**类别：** 排程\n",
    "\n",
    "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n",
    "\n",
    "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/parallel-machine-scheduling-problem-pms)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题描述\n",
    "\n",
    "**并行机调度问题 (PMS)** 是调度文献中的经典问题。它由在一组并行机上调度任务组成。在最基本的表述中，所有机器都是相同的（即任务可以在任何机器上调度），并且每个任务只能由一台机器处理。\n",
    "\n",
    "目标是找到一个使 makespan（所有任务的最大完成时间）最小的调度方案。这种并行机调度问题 (PMS) 的变体也被称为 **P || Cmax**，其中 P 表示存在相同的并行机，而 **Cmax** 表示优化准则是 makespan。\n",
    "\n",
    "### 建模要点\n",
    "\n",
    "- 添加 [set 决策变量](https://optagent.pages.dev/guide/modeling/) 建模任务到资源的分配\n",
    "- 定义 [lambda 函数](https://optagent.pages.dev/guide/modeling/) 来计算每台机器的 makespan\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 数据\n",
    "\n",
    "为了说明此示例，我们从文献中选取了一组实例。并行机调度 (PMS) 实例的格式如下：\n",
    "\n",
    "- 第一行：\n",
    "\n",
    "- 任务数量；\n",
    "- 机器数量；\n",
    "- 第二行：与每个任务相关联的长度。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 建模思路\n",
    "\n",
    "并行机调度 (PMS) 的 OptAgent 模型使用 [set 决策变量](https://optagent.pages.dev/guide/modeling/)。对每台机器，我们定义一个 set 变量表示分配给该机器的任务集合。我们将 set 变量约束为构成一个 partition，确保每个任务恰好在一台机器上调度。\n",
    "\n",
    "我们使用对 set 的可变参数 **sum** 算子和一个 [lambda 函数](https://optagent.pages.dev/guide/modeling/) 来计算一台机器的 makespan，该函数返回与任何任务索引相关联的长度。请注意，求和中的项数在搜索过程中会动态变化，set 的大小也会变化。\n",
    "\n",
    "我们使用 **max** 算子从每台机器各自的 makespan 中提取全局 makespan。该表达式定义了搜索过程中需要最小化的目标函数。\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_instance(filename):\n",
    "    lines = Path(filename).read_text(encoding=\"utf-8\").splitlines()\n",
    "    header = lines[0].split()\n",
    "    n_tasks = int(header[2])\n",
    "    n_machines = int(header[3])\n",
    "    task_lengths = [int(value) for value in lines[1].split() if value != \"0\"]\n",
    "    if len(task_lengths) != n_tasks:\n",
    "        raise ValueError(\"task length count does not match the instance header\")\n",
    "    return n_tasks, n_machines, task_lengths\n",
    "\n",
    "\n",
    "def main(input_file, output_file=None, time_limit=5):\n",
    "    n_tasks, n_machines, task_lengths = read_instance(input_file)\n",
    "    makespan_lb = sum(task_lengths) // n_machines\n",
    "    model = OptModel()\n",
    "\n",
    "    # machine_tasks[k] contains exactly the tasks assigned to machine k.\n",
    "    machine_tasks = [\n",
    "        model.set(n_tasks)\n",
    "        for k in range(n_machines)\n",
    "    ]\n",
    "    model.constraint(model.partition(machine_tasks))\n",
    "\n",
    "    lengths = model.array(task_lengths)\n",
    "    lengths_lambda = model.lambda_function(lambda task: lengths[task // 1])\n",
    "    machine_makespan = [\n",
    "        model.sum(tasks, lengths_lambda) for tasks in machine_tasks\n",
    "    ]\n",
    "    makespan = model.max(machine_makespan)\n",
    "    model.minimize(makespan)\n",
    "\n",
    "    solution = solve(\n",
    "        model,\n",
    "        time_limit_s=float(time_limit),\n",
    "        objective_threshold={0: makespan_lb},\n",
    "    )\n",
    "    if not solution.feasible:\n",
    "        print(f\"No feasible schedule found; Status = {solution.feasible}\")\n",
    "        return solution\n",
    "\n",
    "    lines = []\n",
    "    for machine in range(n_machines):\n",
    "        items = machine_tasks[machine].value\n",
    "        line = (\n",
    "            f\"Makespan machine {machine}: {machine_makespan[machine].value} | \"\n",
    "            f\"Items: {' '.join(map(str, items))}\"\n",
    "        )\n",
    "        print(line)\n",
    "        lines.append(line)\n",
    "    if output_file is not None:\n",
    "        Path(output_file).write_text(\"\\n\".join(lines) + \"\\n\", encoding=\"utf-8\")\n",
    "    return solution\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_pms = main(INSTANCE_DIR / \"p_cmax-n120-m3.txt\", 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
}