一种基于两阶段列生成法的数学规划方法，用于云制造环境中的集成调度

《European Journal of Operational Research》：A two-stage column-generation-based matheuristic for integrated scheduling in a cloud manufacturing environment

　　•提出了一种结合并行批量调度、多车辆路径规划以及资源约束的集成问题模型。•构建了一个混合整数线性规划模型来描述这一实际应用场景。•设计了一种基于列生成的两阶段启发式框架，用以获得接近最优的解决方案。•计算实验表明，该两阶段算法是解决这类集成问题的有效方法。

引言
云制造作为一种新的服务型网络化制造理念，代表了高度协作与创新制造领域的新发展（Xu, 2012）。在云制造模式下，客户可通过云平台便捷地获取分布式制造资源所提供的按需服务（Ren等，2017）。3D打印便是云制造成功应用的典型案例，它有助于解决地理上分布广泛的昂贵3D打印资源供需失衡的问题（Cui等，2022）。本文源于某地区增材制造服务公司所面临的实际运营管理难题。该公司为多家医院提供服务，这些医院可以通过该平台订购定制化的3D打印产品，如手术导板、康复支撑装置、骨科匹配模具等。在传统的调度方式下，生产调度与运输流程是分开进行的，这导致了供应链中的响应时间过长。为提升服务效率，该公司开始推动构建云平台，以连接不同地点的打印设备。在云平台中，存在三大主体：服务提供方、客户以及云平台运营商（Ren等，2017）。医院作为客户下达订单，而增材制造企业则负责提供3D打印机。云平台运营商则负责管理云服务的供需关系、业务交易、服务交付以及服务提供方与客户之间的社交互动。服务提供方又可进一步分为生产类企业和物流类企业。第三方制造商和物流公司会通过合同将部分机器和车辆的调度权交给云平台运营商，类似专业公司负责外包业务的管理。通过云平台，客户（医院）可以在线提交需求。由于3D打印机属于批量处理设备，云平台运营商不仅需要将订单分配给相应的机器，还需确定批量处理方案。当第三方物流服务被整合到云平台后，运输决策就需要与生产调度决策相协调。产品生产完成后，云平台运营商会安排第三方物流车辆从各个生产节点取回成品，将其运送到中央仓库进行后续处理，最终再将产品送至医院，以满足患者的紧急需求。通过集中控制，该平台能够优化资源利用效率（例如整合闲置的3D打印能力），并协调生产与物流流程，从而实现分散式系统无法达到的效率水平。同样，批量调度与运输的整合也是电镀、钢铁、半导体等诸多生产行业普遍面临的问题，Cheng等（2019）和Han等（2019）也对此进行了研究。这些行业通常生产高附加值产品，因此极其依赖高效且协调的交付体系。

针对这一问题，我们在生产阶段考虑并行批量调度，这是一种特殊的批量处理方式，即把任务分组为多个批次，同一批次内的任务会由同一台机器同时处理。而在运输阶段，则研究具有资源约束的多车辆路径问题。第三方物流服务提供方的出发地和返回地均为中央仓库。考虑到他们希望减少服务车辆的往返次数以降低成本，我们假设同一辆车只能访问一台机器一次。基于云制造的集成问题的处理流程如图1所示。

总体而言，本文研究的这一实际案例所带来的问题由于其诸多特殊特征而极为难以解决。首先，生产环境中的批量处理机器具有不同的处理能力，且分布在不同地点；其次，运输阶段的车辆类型多样，各自具有不同的容量限制；第三，某个地点的订单最早取货时间（进而决定车辆的出发时间）取决于打印任务的完成时间，而这个时间是在生产阶段确定的变量；第四，车辆需要前往的地点是由生产分配决定的，而在传统的路径规划问题中，这些地点是事先已知的。这些复杂的因素都源自实际的工业场景，给模型的构建和算法设计带来了巨大挑战。具体而言，该问题需要同时确定任务的分组方式、机器的分配方案、车辆的指派以及路径规划方案。因此，构建一个集成模型可能需要更高的计算成本，所以采用基于分解的解决方案策略十分必要。

本文的贡献如下。首先，我们基于实际应用场景，提出了一个包含并行批量调度与具有特殊约束的多车辆路径问题的集成模型。据我们所知，现有研究中尚未有学者探讨过这一特定问题。其次，我们为该集成问题构建了混合整数线性规划模型。这样的集成模型可以为各种启发式算法或分解算法提供一个高质量的评估基准。第三，我们设计了一种基于列生成并融入多种局部搜索方法的两阶段启发式框架来解决该问题。我们的两阶段启发式框架可为更多类似的集成调度问题提供参考。这种启发式方法充分利用了数学规划在解决问题方面的优势，能够确保得到稳健且高质量的解决方案。最后，我们在多种问题实例上测试了不同策略下这些方法的性能，并将其与其他最先进的方法进行了比较。数值实验结果表明，该框架显著降低了大规模实例的计算时间。

本文的其余结构如下：第2节概述相关文献；第3节详细介绍问题描述中的混合整数线性规划模型；第4节介绍基于列生成的两阶段启发式框架；第5至6节分别详细阐述生产阶段和配送阶段的算法，第7节介绍反馈机制；第8节报告实验结果，第9节总结全文。

文献综述
本研究所涉及的规划问题与两个经典的组合优化问题密切相关：并行批量调度问题以及具有资源约束的车辆路径问题。本节简要回顾了若干研究这些问题的重要文献，并探讨了在云制造框架下的集成生产与运输调度问题。

问题描述
一个云平台会收到来自多个客户的n个任务，记为集合N=1,2,…,n。每个任务i∈N都有大小qi和处理时间pi。另一组集合M=1,2,…,m代表m台批量处理机器，这些机器除了处理能力和位置不同外，其他特性均相同。每台机器k都是一台具有容量Capk的批量处理机器，能够同时处理多个任务；我们假设对于每个i∈N，都有qi≤Capk。每台机器上会处理n个任务组成的批次，记为集合B=1,2,…,n。显然，最多只有nA种可能的批次划分方式。

基于列生成的两阶段启发式框架
对于规模较小的实例，上述模型可以使用Gurobi等商业优化软件在可接受的时间内求解。但随着实例规模的增大，优化软件的计算效率会显著下降。为了解决这一难题，我们提出了一种基于列生成的两阶段启发式方法。本节将简要介绍我们的两阶段算法框架。该两阶段方法的思路是将整个问题分解为多个子问题依次解决。

并行批量调度问题的求解流程
在这一阶段，我们介绍了通过列生成和虚拟噪声搜索算法得到批量方案的方法。首先，我们给出用于求解线性松弛问题的集合划分模型，然后通过启发式算法找到一组可行的初始批次。在求解定价问题时，我们首先使用启发式算法生成具有负降低成本的列。如果启发式算法失效，就会对定价问题（模型（25）–（32））进行精确求解，以确保不会遗漏任何有可能带来更好结果的列。

多车辆路径问题的求解流程
对于并行批量调度问题的每一个解H=1,2,…,h，如果该解进入第二阶段，就可以通过列生成算法得到对应的配送方案。我们提出了一种标签设置算法来最优地求解定价问题。一旦算法找到更好的解，就会更新OP2值。当搜索过程结束时，目标函数值最小的配送方案即为最终解。终止条件为H中的所有批量方案都已求解，或者达到其他预设条件。

反馈机制
本节介绍了两种用于反馈的局部搜索方法。我们期望通过配送方案的信息得到更好的批量方案，具体方法如下。

计算实验
本节汇报了我们为验证所提出的基于列生成的两阶段启发式算法TSCGM_VNSLS的有效性而进行的多次计算实验的结果。我们设计了两种对比方案：（1）不采用虚拟噪声搜索算法和反馈机制的TSCGM_VNSLS算法；（2）用经典的随机键遗传算法来替代列生成和虚拟噪声搜索方法，用于求解并行批量调度问题（Zhou等，2018），以此比较不同方法的性能。

结论
在本文中，我们为基于云制造的集成生产与运输问题提出了新的模型和算法。我们的主要贡献可总结如下：（1）提出了该集成问题的新型混合整数线性规划模型，并开发了一种两阶段启发式方法。在第一阶段，运用列生成算法生成批量方案，同时使用启发式算法加速定价问题的求解；我们还提出了虚拟噪声搜索算法，以获得更多可行的批量方案。

CRediT作者贡献说明
Qiao Wu：撰写原始稿件、获取资金支持、概念构思。Naiming Xie：获取资金支持、概念构思。Roel Leus：撰写审稿与编辑稿件、项目指导。Shaoxiang Zheng：方法设计、概念构思。

利益冲突声明
作者声明不存在任何可能影响本文研究工作的已知财务利益或个人关系。

致谢
本研究始于第一作者访问鲁汶大学期间，得到了中国国家留学基金委的支持。此外，该研究还获得了国家自然科学基金[72501149, 72571138, 72401115]、江苏省高校哲学社会科学研究项目（项目编号2025SJYB0097）以及南京邮电大学人才引进科研启动基金项目（项目编号NYY224022）的资助。

Qiao Wu|Naiming Xie|Roel Leus|Shaoxiang Zheng