面向工具转移的分布式置换流水车间调度问题以最小化总拖期

《Computers & Operations Research》：The distributed permutation flowshop scheduling problem with tool transfers to minimize the total tardiness

　　

摘要
竞争压力与经济增长促使企业分散其生产地点，以靠近客户和原材料市场。由此产生的生产网络需要在多个工厂之间进行协调规划，从而引致分布式调度问题。在工业生产网络中，某些机床上的加工需要使用专用且昂贵工具，这类工具仅在部分工厂可用，由此产生工厂资格约束。尽管此类约束具有实际重要性，但在过去15年的调度文献中却在很大程度上被忽视。本项研究通过扩展分布式置换流水车间调度问题，纳入由工具可用性引发的资格约束，并通过工厂间工具转移使约束动态演化，填补了这一空白。为在兼顾地理分散工厂的同时支持按时交付，模型引入了工厂相关交期，并以最小化总拖期为目标。为此，研究人员开发了三种求解方法：一种新颖的基于网络流的混合整数规划模型、一种约束规划模型，以及一种定制化迭代贪婪算法。对于大规模实例，该算法相较于约束规划方法平均降低了7.7%的总拖期。计算实验进一步表明，与静态工具分配相比，工具转移平均降低了21.67%的总拖期。敏感性分析证实，在变化的工具冗余水平和地理网络配置下，工具转移均保持其有效性。

基于工具转移的分布式置换流水车间调度问题研究解读

一、研究背景与动机

随着市场自由化与全球化贸易的深入发展，制造企业的生产组织模式正从集中式制造转向全球生产网络，旨在以尽可能高效灵活的方式响应动态市场变化。企业地理分散或迁移的动机包括追求更低的劳动力和能源成本、接近市场与客户、获取熟练劳动力、税收激励与补贴，以及靠近关键原材料和核心技术等。分布式生产网络的有效性在很大程度上取决于各工厂之间的高效协调、协作与同步，但这同时增加了生产计划与调度的复杂性。在这一背景下，分布式置换流水车间调度问题（DPFSP）被正式提出并被证明是NP完全的。该问题将传统置换流水车间调度推广至包含多个同构流水车间的工厂网络。尽管过去十余年间针对DPFSP的算法研究已取得大量成果，但若干具有明确工业相关性的问题特征仍未被充分探索。既有文献普遍假设所有工厂能够加工任意作业，然而在实际生产中，加工往往依赖专用工具，如注塑成型中的产品专用模具。受高昂采购成本限制，在所有工厂均配备冗余工具通常不经济，由此产生工具可用性限制及工厂资格约束。允许工具在工厂间转移可放松此类资格约束并提高调度灵活性。此外，以往分布式调度研究主要关注最大完工时间和成本目标，而来自工业界的调查表明按时交付是约66%企业的首要目标，因此拖期导向目标具有高度现实意义。同时，地理分散导致不同工厂至客户的交付距离不同，进而产生工厂相关生产交期。基于上述原因，本项研究将工具转移引入分布式置换流水车间调度问题，建立DPFSP-TT以最小化总拖期。

二、研究内容与关键方法

研究人员将传统DPFSP扩展为包含工厂资格约束和动态工具转移的DPFSP-TT模型，并开发了三种求解方法：基于网络流的混合整数规划（MIP）模型、约束规划（CP）模型和定制化迭代贪婪（IG）算法。MIP模型将工具移动建模为流网络，以位置变量为基础扩展工具可用性约束；CP模型利用区间变量和状态函数刻画工具转移与调度约束；IG算法采用置换表示，提出包含工厂序列和工具序列的解码图，并设计了高效的总拖期评价程序。算法初始化采用改进的NEH启发式，局部搜索采用插入式邻域搜索，并使用模拟退火接受准则平衡勘探与开发。实验数据基于欧洲真实道路网络生成实例，工厂国家按工业GDP加权选择，客户位置随机分配至欧盟27国城市，利用开源路由机计算转移与交付时间。实例规模涵盖小型与大型测试集。

三、实验结果分析

（一）小规模测试集性能

在包含480个实例的小规模基准上，对比了CP和MIP两种精确方法的性能。结果表明，随着作业数量增加，两种精确方法的性能均迅速下降。CP模型在绝大多数实例中性能优于MIP，当作业数为12时，MIP无法在60个实例中的任何一个证明最优性，而CP在43个实例中做到了。CP模型在作业数n=12时的平均求解时间从n=10时的33.07秒急剧增加到710.4秒。以IG算法（时间限制0.5n秒）的结果为参考基准，CP在n=18时的平均相对百分比偏差为2.62%，而MIP为20.34%。IG算法在所有480个实例中均找到了最佳已知解，显示出其高效性和解质量。

（二）大规模测试集性能

大规模测试集包含360个实例，涵盖n=10至60、m=5至20、工厂数2至4。结果显示，问题复杂度从DPFSP-E到DPFSP再到DPFSP-TT递增。CP模型只在10个作业的实例中表现较好，当n>10时，在每个因子水平上，CP在60个实例中最多找到两次最佳已知解。相比之下，IG算法在360个实例中的359个找到了最佳已知解（三种问题类型共1080个实例中的1079个），且平均总拖期比CP低7.7%，运行时间仅为2n秒，远低于CP的1800秒限制。CP模型在DPFSP-E上性能尚可，但在允许工具转移的DPFSP和DPFSP-TT上性能显著下降，表明工具转移大幅扩大了搜索空间。

（三）工具转移的价值量化

以固定工具分配的DPFSP-E为基线，评估工具转移（DPFSP-TT）和完全工具冗余（DPFSP）对总拖期的降低效果。在大型实例上，采用IG算法并使用n×m秒的时间预算，依次求解DPFSP-E、DPFSP-TT和DPFSP，并以先前问题的解作为后续问题的初始解。结果显示，跨所有工厂配置平均而言，工具转移将总拖期平均降低了21.67%（中位数17.55%），完全冗余则实现31.33%的平均降幅（中位数30.08%）。工具转移的收益随工厂数量增加而增加，随作业数量增加而下降并趋于稳定。在两工厂网络中，工具转移几乎达到完全冗余的效果，平均偏差从30个作业起降至4%以下。转移次数随工厂和作业增加，但并非与作业数量成正比，在较大实例中单次转移可服务多个连续作业。

（四）敏感性分析

敏感性分析围绕三个研究问题展开。第一，工具冗余的影响。在四工厂网络中，当每个工具仅有一个单元时，允许工具转移的中位相对偏差为17.24%，而固定分配为67.24%，表明工具转移可减少约50%的拖期。将冗余从1增加到2个单元，工具转移的中位RPD降至2.59%，接近完全冗余的0.44%，说明第二个工具单元即能带来接近最优的性能。固定分配在同样条件下仍有15.08%的偏差。第二个工具单元之后的额外冗余只带来边际改善，但成本预计不成比例增加。第二，工厂邻近性的影响。通过按1.0到2.5的比例因子缩放转移和交付时间，模拟不同程度的地理分散。随着比例因子增加，总拖期和RPD上升，但工具转移相对基线DPFSP-E的拖期减少幅度保持相对稳定，从平均21.6%仅轻微下降至19.8%，表明工具转移在不同地理网络配置下均为有效机制。第三，工具依赖作业比例的影响。工具依赖作业比例从10%升至50%再升至90%时，平均RPD从0.36%增至6.12%再增至48.64%。中等工具利用水平下相对拖期增加仍有限，转移在50%工具依赖下仍将拖期增长限制在约6%。工具依赖机器位于较后阶段时，转移更有利，因为可更好地吸收转移引起的空闲时间。

四、讨论与结论

从方法论角度看，CP模型在中小规模实例上优于MIP，IG算法在大规模实例上显著优于CP。IG算法简单且适应性强，适合总拖期目标，但其运行时间受评价效率制约，传统加速技术不适用于总拖期计算，因此开发先进的加速方法是一个有前景的方向。考虑到DPFSP-TT的高结构复杂度，基于分解的方法如基于逻辑的Benders分解可能有益，但工厂间通过工具转移强耦合使分解设计具有挑战性。从管理角度看，工具转移相对于固定工具分配平均降低21.67%的总拖期，且网络规模越大收益越显著。在低工具冗余下，工具转移可减少高达50%的拖期，提供两个工具单元就足以接近完全冗余表现。转移还通过缩短交付距离带来成本和环境优势。未来研究可考虑将技能劳动力建模为类似工具的资格约束，引入转移工具的安装时间、特定破坏算子以及应对随机扰动的鲁棒与动态方法。本研究为分布式生产网络中的资源共享和交期履行提供了系统的理论支撑与实用算法工具。论文发表于期刊《Computers》。

以上解读严格依据原文内容浓缩而成，未添加任何推测性信息。研究人员通过对理论与实验的深入融合，为分布式置换流水车间调度领域填补了工具转移这一空白，并为工业实践中稀缺资源在多个工厂间的协调调度提供了可操作的决策支持。