Integrated packing, placement, scheduling, and routing of personalized production: a pharmaceutical Industry 4.0 use-case with a planar transport system

这是一份关于论文《集成个性化生产的包装、布局、调度与路径规划：制药工业 4.0 平面运输系统用例》（Integrated packing, placement, scheduling, and routing of personalized production: a pharmaceutical Industry 4.0 use-case with a planar transport system）的详细技术总结。

1. 研究背景与问题定义

背景：
制药行业正面临从大规模生产向大规模个性化生产（Mass Personalization）的转型。传统的固定剂量组合（Fixed-Dose Combinations）难以应对患者复杂的用药需求（多药并用），而传统的人工配药缺乏可扩展性。新兴的平面运输系统（Planar Transport Systems，如 Beckhoff XPlanar）提供了二维自由度的独立移动器（Movers），能够直接在网格上移动并与工作站交互，消除了传统流水线或机械臂辅助的局限性。

核心问题：
如何在平面运输系统上实现个性化药物的自动化生产？这需要解决一个复杂的多阶段优化问题，涉及两个决策层级：

1. 战术层（Tactical Level）： 长期决策。包括生产线的物理布局设计、药物分配器的数量分配（Packing）以及它们在平面网格上的具体位置安排（Placement）。目标是基于历史处方数据，最小化未来的预期移动距离。
2. 操作层（Operational Level）： 日常决策。针对每日接收的新订单，调度移动器（Movers）以最快的速度完成生产。这包括将订单分配给移动器、确定操作序列（Scheduling）以及生成无冲突的路径（Routing）。

挑战：

• 组合爆炸： 药物组合的多样性导致巨大的解空间。
• 耦合性： 布局设计直接影响调度效率，而调度中的冲突又受路径限制。
• 资源约束： 移动器被视为“取 - 给”（Take-Give）资源，一旦开始处理订单直到完成前不可中断或处理其他订单。

2. 方法论与框架

论文提出了一套分层优化框架，将问题分解为四个核心子问题：

2.1 战术层：包装（Packing）与布局（Placement）

• 包装问题 (Packing Problem)：

  • 目标： 决定每种药物需要多少个分配器，以及将哪些药物组合放在同一个瓷砖（Tile）上，以利用药物共现（Co-occurrence）模式并平衡负载。
  • 模型： 建立了一个**混合整数二次规划（MIQP）**模型。
  • 策略： 利用历史处方数据估算每种药物的总需求，最小化单个瓷砖上的最大预期负载（Makespan），同时考虑药物共现以减少移动器在单个订单内的移动次数。

• 布局问题 (Placement Problem)：

  • 目标： 将已打包的分配器瓷砖和接口（Interface）映射到具体的物理坐标（网格布局），以最小化移动历史订单所需的平均曼哈顿距离。
  • 模型： 这是一个双层优化问题。
    • 外层：分配问题（将瓷砖分配到网格位置）。
    • 内层：带邻域的最短哈密顿路径问题（SHPPN），即寻找访问所有所需分配器的最短路径。
  • 算法： 由于内层问题复杂，提出了一种遗传算法（GA）。在适应度函数计算中，采用了一种基于采样的启发式方法（模拟多个“情节”），不仅考虑最近邻的贪婪策略，还以逆距离概率采样较远的分配器，以模拟操作层调度中可能遇到的资源冲突，从而获得更鲁棒的布局。
  • 复杂度： 证明了该布局问题即使在直线布局下也是 NP-hard 的（通过从 Exact 3-Cover 归约）。

2.2 操作层：调度（Scheduling）与路径规划（Routing）

• 调度问题 (Scheduling Problem)：

  • 目标： 将每日订单分配给可用的移动器，确定操作序列和开始时间，最小化最大完工时间（Makespan）。
  • 模型： 采用约束规划（Constraint Programming, CP）。
  • 关键创新： 将移动器建模为**“取 - 给”（Take-Give）储备资源**。这意味着移动器在开始处理一个订单时“占用”资源，直到该订单所有操作（包括加载、分配、卸载）完成后才“释放”资源。
  • 约束： 包括移动器互斥、分配器互斥、瓷砖互斥、旅行时间（基于曼哈顿距离）以及订单操作的先后顺序（加载 -> 分配 -> 卸载）。
  • 下界估计： 提出了一个基于平行机调度（Parallel Machine Scheduling）和 SHPPN 的下界计算方法，用于评估解的质量和为求解器提供热启动。

• 路径规划问题 (Routing Problem)：

  • 目标： 根据调度结果生成无冲突的物理路径。
  • 机制： 不同于传统的多智能体路径规划（MAPF），该系统允许移动器在非分配操作时共享瓷砖。
  • 算法： 采用迭代冲突解决机制结合**有向无环图（DAG）**推理。
    1. 生成休息点（Resting Sites）布局（最大独立集问题）。
    2. 将空闲时间分配给休息点。
    3. 构建 DAG 表示操作间的依赖关系（同移动器顺序、同分配器顺序）。
    4. 检测冲突（如移动器穿过正在分配药物的瓷砖），通过延长开始时间（暂停）来消除冲突，并迭代更新直到无冲突。

• 可扩展性策略： 对于大规模订单集，采用**基于 DAG 的调度合并（Batch Merging）**策略，将大订单集拆分为小批次独立调度，然后合并 DAG 并调整时间，以平衡计算效率与解的质量。

3. 主要贡献

1. 形式化定义： 首次将平面运输系统上的个性化药物自动化组装形式化为一个包含战术（包装/布局）和操作（调度/路径）的综合优化问题。
2. 分层优化框架： 提出了一种解耦战术与操作决策的框架，确保长期布局设计能预判操作约束。
3. 算法创新：
   • 开发了基于 MIQP 的包装模型，利用药物共现模式。
   • 设计了结合遗传算法与内层 SHPPN 启发式采样的布局优化算法。
   • 构建了基于 CP 的调度模型，创新性地使用“取 - 给”资源模型处理移动器独占性。
   • 提出了基于 DAG 的迭代冲突解决路径规划方法，适应平面系统的特殊物理约束。
4. 理论分析： 证明了布局问题的 NP-hard 性质，并提出了结合平行机调度与 SHPPN 的 Makespan 下界。
5. 实证评估： 使用真实的 NHANES 处方数据（40 种药物）和合成数据进行了广泛实验，验证了框架的有效性。

4. 实验结果

• 数据基础： 基于美国国家健康与营养调查（NHANES）的真实处方数据，模拟了 3-8 种药物的个性化订单。
• 战术层鲁棒性： 在 100 个不同的验证集上测试，生成的布局在未见数据上的 Makespan 偏差控制在 ±10% 以内，证明未发生过拟合。
• 目标函数相关性： 布局优化的目标函数（最小化预期步数）与实际调度 Makespan 呈现强线性正相关，验证了代理目标的有效性。
• 调度性能：
  • 移动器数量影响： 增加移动器数量能显著减少 Makespan，但在达到一定数量后（受限于分配器瓶颈），收益递减。
  • 时间限制： 对于 100 个订单以内的场景，300 秒的计算时间通常足够获得高质量解；对于 500 个订单，分解策略（Batching）显著提升了求解效率。
  • 下界差距： 实际解与理论下界的差距通常在 8% - 25% 之间，表明解的质量接近最优。
• 路径规划开销： 路由阶段的冲突解决带来的额外时间开销极小（标准速度下 < 1.2%，高速速度下 < 11.5%），证明调度模型已很好地近似了物理约束。
• 可扩展性： 通过 DAG 合并策略，系统能有效处理高达 500 个订单 的批次，且计算时间可控。

5. 意义与结论

• 工业 4.0 应用： 该研究为制药行业的个性化生产提供了具体的工业 4.0 解决方案，展示了平面运输系统在处理高混合、小批量生产中的巨大潜力。
• 决策支持工具： 提出的框架可作为投资者和系统设计者的仿真工具，用于在物理实施前评估设施配置（布局、分配器数量、移动器数量）的吞吐量和投资回报率。
• 方法论价值： 该论文展示了如何将复杂的物流问题分解为战术和操作层级，并结合混合整数规划、约束规划和启发式算法来解决实际工业中的耦合优化问题。
• 未来展望： 随着分配速度的提升，路径冲突的影响会略微增加，但整体框架仍保持高效。未来的工作可进一步关注物理实现的细节和更复杂的动态环境。

总结： 本文成功构建了一个从长期布局设计到日常订单调度的完整闭环系统，利用先进的运筹学方法解决了平面运输系统在个性化制药生产中的核心挑战，实现了高效、鲁棒且可扩展的自动化生产方案。