科技导报

符号	类型	物理含义
$ {y}_{t} $	0−1变量	任务$ t $是否准时交付
$ {z}_{e} $	0−1变量	链路$ e $是否被启用
$ {g}_{v} $	0−1变量	节点$ v $是否被启用
$ \,{f}_{e}^{\;t} $	连续变量	任务$ t $在链路$ e $上分配的吞吐速率
$ {F}_{w} $	连续变量	子系统$ w $的总吞吐速率

符号	类型	物理含义
$ {y}_{t} $	0−1变量	任务$ t $是否准时交付
$ {z}_{e} $	0−1变量	链路$ e $是否被启用
$ {g}_{v} $	0−1变量	节点$ v $是否被启用
$ \,{f}_{e}^{\;t} $	连续变量	任务$ t $在链路$ e $上分配的吞吐速率
$ {F}_{w} $	连续变量	子系统$ w $的总吞吐速率

参数类别	符号	取值范围/设定值	说明
子系统规模	$ \left\|W\right\| $	$ \left[\mathrm{6,10}\right] $
加工节点规模	$ \left\|A\right\| $	$ \left[\mathrm{500,1000}\right] $
生产任务规模	$ \left\|T\right\| $	$ \left[\mathrm{50,100}\right] $
运行时限	$ cutoff \;$	60 s	单次搜索求解的时间预算

参数类别	符号	取值范围/设定值	说明
子系统规模	$ \left\|W\right\| $	$ \left[\mathrm{6,10}\right] $
加工节点规模	$ \left\|A\right\| $	$ \left[\mathrm{500,1000}\right] $
生产任务规模	$ \left\|T\right\| $	$ \left[\mathrm{50,100}\right] $
运行时限	$ cutoff \;$	60 s	单次搜索求解的时间预算

M	H−LMIP			LNS
1	84	0.895574	48	0.888721	0.820775	2	0.803797
2	85	0.914677	48	0.910181	0.816247	1	0.793829
3	86	0.924229	47	0.920910	0.813983	1	0.788845
4	86	0.929960	47	0.927348	0.812625	1	0.785855
5	86	0.933780	47	0.931640	0.811719	1	0.783861

M	H−LMIP			LNS
1	84	0.895574	48	0.888721	0.820775	2	0.803797
2	85	0.914677	48	0.910181	0.816247	1	0.793829
3	86	0.924229	47	0.920910	0.813983	1	0.788845
4	86	0.929960	47	0.927348	0.812625	1	0.785855
5	86	0.933780	47	0.931640	0.811719	1	0.783861

方法	HV值
H−LMIP	1.055594
Local−MIP	0.993465
LNS	0.799391
NSGA−II	0.652725

方法	HV值
H−LMIP	1.055594
Local−MIP	0.993465
LNS	0.799391
NSGA−II	0.652725

面向大规模定制的异构物流多目标调度优化

预览PDF | 下载PDF

赵晓然 , 江滢怡 , 罗川 ^*

科技导报 | 研究论文 2026,44(18): 159-168

收起

科技导报 |研究论文 2026 , 44 (18) : 159 -168

面向大规模定制的异构物流多目标调度优化

全屏

[Author(id=1324320248492601677, tenantId=1146029695717560320, journalId=1146031591421210625, articleId=1324320244906471742, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=zhaoxiaoran@buaa.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1324320248563904846, tenantId=1146029695717560320, journalId=1146031591421210625, articleId=1324320244906471742, authorId=1324320248492601677, language=EN, stringName=Xiaoran ZHAO, firstName=Xiaoran, middleName=null, lastName=ZHAO, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio=null, bioImg=null, bioContent=null, aboutCorrespAuthor=null), CN=AuthorExt(id=1324320248651985231, tenantId=1146029695717560320, journalId=1146031591421210625, articleId=1324320244906471742, authorId=1324320248492601677, language=CN, stringName=赵晓然, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

赵晓然，博士研究生，研究方向为多目标优化，智能运维，电子信箱：zhaoxiaoran@buaa.edu.cn

"}, bioImg=null, bioContent=

赵晓然，博士研究生，研究方向为多目标优化，智能运维，电子信箱：zhaoxiaoran@buaa.edu.cn

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1324320248714899793, tenantId=1146029695717560320, journalId=1146031591421210625, articleId=1324320244906471742, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=jiangyy25@buaa.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1324320248782008658, tenantId=1146029695717560320, journalId=1146031591421210625, articleId=1324320244906471742, authorId=1324320248714899793, language=EN, stringName=Yingyi JIANG, firstName=Yingyi, middleName=null, lastName=JIANG, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio=null, bioImg=null, bioContent=null, aboutCorrespAuthor=null), CN=AuthorExt(id=1324320248861700435, tenantId=1146029695717560320, journalId=1146031591421210625, articleId=1324320244906471742, authorId=1324320248714899793, language=CN, stringName=江滢怡, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio=null, bioImg=null, bioContent=null, aboutCorrespAuthor=null)}, companyList=null), Author(id=1324320248937197909, tenantId=1146029695717560320, journalId=1146031591421210625, articleId=1324320244906471742, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=chuanluo@buaa.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1324320249004306774, tenantId=1146029695717560320, journalId=1146031591421210625, articleId=1324320244906471742, authorId=1324320248937197909, language=EN, stringName=Chuan LUO, firstName=Chuan, middleName=null, lastName=LUO, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=^*, address=null, bio=null, bioImg=null, bioContent=null, aboutCorrespAuthor=null), CN=AuthorExt(id=1324320249079804247, tenantId=1146029695717560320, journalId=1146031591421210625, articleId=1324320244906471742, authorId=1324320248937197909, language=CN, stringName=罗川, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=^*, address=null, bio=null, bioImg=null, bioContent=null, aboutCorrespAuthor=null)}, companyList=null)]

赵晓然, 江滢怡, 罗川^*

作者信息

北京航空航天大学软件学院，北京 100191‌

通讯作者:

罗川（通信作者），教授，研究方向为组合优化、约束求解，电子信箱：chuanluo@buaa.edu.cn

作者简介:

赵晓然，博士研究生，研究方向为多目标优化，智能运维，电子信箱：zhaoxiaoran@buaa.edu.cn

Multi−objective scheduling optimization for heterogeneous logistics in mass customization

Xiaoran ZHAO, Yingyi JIANG, Chuan LUO^*

Affiliations

School of Software, Beihang University, Beijing 100191, China

出版时间: 2026-09-28 doi: 10.3981/j.issn.1000-7857.2026.06.00095

文章导航

摘要

收起

随着大规模定制化生产模式的演进，柔性制造系统（flexible manufacturing system，FMS）中的物流调度已成为提升工厂效能的关键。针对高度自动化车间中异构搬运子系统（如automated guided vehicle（AGV）、悬挂链、传送带）协同作业时面临的高并发任务、动态资源冲突及复杂物理约束难题，提出了一种层次化局部搜索混合整数规划方案（hierarchical local−MIP，H−LMIP）。首先，该方案将复杂的异构车间环境抽象为具备“吞吐量特征”的有向图拓扑模型，实现了对加工工位、待命资源与输送链路间物理逻辑关系的精确刻画；构建了以最大化准时交付任务数为主要目标，兼顾最小化启用成本、最小化链路启用能耗（低碳目标）及最小化负载不均衡度的层次化多目标优化框架；为破解大规模离散决策空间带来的计算瓶颈，H−LMIP 引入了两阶段动态约束引导机制，通过权重标量化与局部搜索的深度融合，实现了在有限时间预算下对层次化目标的快速搜索与精确权衡。实验表明，所提 H−LMIP方案相较于Local−MIP、LNS和经典 NSGA−II 算法表现出更优的综合求解性能，为智能工厂实现低碳、高效运行提供了有效的决策支撑。

关键词

物流调度 / 多目标优化 / 混合整数规划 / 局部搜索算法

Abstract

收起

With the evolution of large−scale customized production, logistics scheduling in Flexible Manufacturing Systems (FMS) has become a critical factor in improving factory efficiency. In highly automated workshops, heterogeneous material handling subsystems—such as Automated Guided Vehicles (AGVs), overhead conveyors, and ground conveyor systems—face challenges including high−concurrency tasks, dynamic resource conflicts, and complex physical constraints. To address these issues, this paper proposes a Hierarchical Local−search Mixed−Integer Programming approach (Hierarchical Local−MIP, H−LMIP). First, the complex heterogeneous shop−floor environment is abstracted into a directed graph topology with throughput characteristics, enabling an accurate representation of the physical and logical relationships among processing stations, idle resources, and transportation links. Based on this modeling framework, a hierarchical multi−objective optimization model is constructed, where the primary objective is to maximize the number of on−time completed tasks, while secondary objectives include minimizing activation cost, reducing transportation energy consumption (i.e., low−carbon objective), and balancing system load. To overcome the computational challenges caused by large−scale discrete decision spaces, the proposed H−LMIP incorporates a two−stage dynamic constraint−guided mechanism. By integrating weighted scalarization with local search, the method enables efficient exploration and refined trade−offs among hierarchical objectives within limited computational time. Numerical experiments demonstrate that the proposed H−LMIP achieves better overall optimization performance than Local−MIP, LNS, and the classical NSGA−II, providing effective decision support for low−carbon and efficient operations in smart factories.

Key words

material flow scheduling / multi−objective optimization / mixed integer programming / local search algorithm

引用本文

赵晓然, 江滢怡, 罗川. 面向大规模定制的异构物流多目标调度优化. 科技导报, 2026 , 44 (18) : 159 -168 . DOI: 10.3981/j.issn.1000-7857.2026.06.00095

Xiaoran ZHAO, Yingyi JIANG, Chuan LUO. Multi−objective scheduling optimization for heterogeneous logistics in mass customization[J]. Science & Technology Review, 2026 , 44 (18) : 159 -168 . DOI: 10.3981/j.issn.1000-7857.2026.06.00095

正文

收起

随着工业与智能制造的深度融合，科学高效的物流转运已成为保障自动化柔性产线稳定运行的核心支柱^[1]。面对多品种、小批量、个性化的生产模式，基于自动导引车（automated guided vehicle，AGV）、悬挂链及传送带等异构设备的协同配送模式得到广泛应用^[2−3]。然而，高并发物流网络在提升生产弹性的同时，也引发了严峻的资源与能耗危机。伴随全球工业化进程，制造业消耗了近一半的全球能源，温室气体排放日益凸显^[4−5]。据统计，零部件的有效物理加工时间往往仅占总时长的5%~10%，高达90%~95%的时间被严重耗费在物料存储、等待与搬运环节^[6−7]；此外，高达85%的能耗被白白耗费在物流设备的频繁启停与空载待机中^[8]。保障任务的准时交付与降低系统运行能耗之间存在显著的博弈关系：一味追求极致的生产吞吐往往伴随着高强度的资源激活，而过度侧重节能则可能限制系统的实时响应能力。因此，依靠调度算法在“交付效能、运营成本、低碳能耗与负载平衡”之间寻求全局权衡，已成为智能工厂实现低碳、高效运行的关键途径。

针对车间物流路径规划，早期研究多聚焦于底层算法的静态改良，常采用时间窗规则或经典 A* 算法来预防静态死锁^[9−10]。例如，通过引入转弯惩罚成本与提取关键节点，有效提升了单台 AGV 的路径平滑度与搜索效率。然而，在应对高并发与多载荷（multiload）等现代场景时，直接利用传统静态策略极易加剧冲突风险并导致效率下降^[11−12]。为此，现有研究通过预测路径拥堵度来主动重规划路线^[13]，基于设备实时电量设定动态优先级^[14]，结合改进 A* 算法与元胞自动机机制，通过分层决策来实现局部冲突的消解^[15]。但上述策略在异构协同时存在显著局限：一方面，多步前向预测等迭代机制在面对大规模并发任务时会导致计算量剧增^[16]；另一方面，现有方案大多局限于单一平面的纯 AGV 路网，对物理节点的“吞吐量限制”抽象不足，简单的优先级规则极易引发大规模的系统级死锁。

在多资源协同调度求解方面，传统的混合整数线性规划（mixed−integer linear programming，MILP）因 NP−hard 特性极易陷入“维数灾难”^[17−18]。因此，目前大量研究倾向于采用以 NSGA−II 为代表的非支配排序遗传算法来寻求多目标的帕累托最优解^[19−21]。尽管启发式算法提升了求解速度，但当决策搜索空间庞大时，极易陷入盲目变异并产生大量不可行解^[22]。尤其在本文的异构协同场景中，设备间存在着极其严苛的并发能力与网络吞吐量硬约束，传统 NSGA−II 算法不仅面临无效搜索导致的算力浪费，更因其无差别对待目标的特性，难以兼顾真实工业场景中“先保交付、再降成本”这种具有明确绝对优先级的层次化多目标诉求。

为克服严苛物理约束下的搜索盲目性，提出一种层次化局部搜索混合整数规划方案（H−LMIP）。该方案首先将异构车间抽象为具有吞吐量与并发限制的有向图拓扑模型，以规避潜在死锁风险，并构建了涵盖任务交付、运营成本、链路能耗及负载均衡的层次化多目标优化框架；利用候选路径预生成策略降低决策维度，并采用具备双层评分函数与动态权重机制的高效局部搜索求解器 Local−MIP^[23]，通过对目标与约束的层次化引导实现复杂调度解的快速寻优。

1 异构物流调度问题建模

收起

1.1 问题描述

在典型的柔性制造系统（flexible manufacturing system，FMS）中，物流调度是保障高效生产的核心环节。本研究针对一类多资源耦合的复杂车间物流场景，其具体特征描述如下。

1）异构资源组合与网络拓扑。系统由多个异构物流搬运子系统（如自动导引车 AGV、悬挂链、传送带等）构成。车间内空间分布着已预先分配好的加工工位集合，工位之间通过物理（如导轨、皮带）或逻辑（如 AGV 调度路径）连接，形成复杂的输送链路网络。此外，为应对动态生产波动，车间内还存在一批处于待命状态的备用工位，可根据任务负荷按需激活。

2）物流任务特征与流向。系统当前面临若干并发的生产物流任务。这些任务的目标是建立从原料发料口到终点装配线的连续、稳定物料流。由于工位分布及搬运介质的局限性，单个任务往往无法由单一手段完成，需要跨越不同的搬运子系统进行中转与协同。

3）调度核心目标。系统的核心挑战在于：针对海量且复杂的任务流向，如何生成最优的搬运路径规划方案。这不仅涉及各任务流量在物理链路上的时空分配，还涉及对链路激活状态、备用工位启用，以及子系统间负荷均衡的协同决策。

1.2 系统符号定义

为此，将上述问题抽象为有向图

$ G=(V,E) $

。

1）子系统集合：

$ W=\left\{{w}_{1},{w}_{2},\cdots ,{w}_{\left|W\right|}\right\} $

，涵盖AGV、悬挂链、传送带等。

2）节点集合：

$ V=A\cup {A}_{{\mathrm{new}}}\cup S=\{{v}_{1},{v}_{2},\cdots ,{v}_{\left|V\right|}\} $

，其中，

$ A $

为已分配好的加工工位，

$ {A}_{{\mathrm{new}}} $

为待命状态的备用工位，

$ S $

为原料发料口与终点装配线（源节点与汇节点）。

3）链路集合：

$ E=\{{e}_{1},{e}_{2},\cdots ,{e}_{\left|E\right|}\} $

，代表工位间物理或逻辑上的输送链路。

4）任务集合：

$ T=\{{t}_{1},{t}_{2},\cdots ,{t}_{\left|T\right|}\} $

，表示从发料口到装配线的连续物流需求，每个任务

$ t\in T $

需跨越不同的子系统完成传输。

任务

$ t\in T $

的起点与终点分别为

$ start_t和end_t $

，需求速率为

$ {D}_{t} $

，指任务

$ t $

在成功执行时所要求的吞吐速率。

其中，每个子系统

$ w\in W $

具有吞吐速率上限

$ {B}_{w} $

与新增工位对网络产生的扩容代价

$ {C}_{w} $

；每条链路

$ e\in E $

具有吞吐速率上限

$ {B}_{e} $

与启用能耗

$ {P}_{e} $

；每个工位

$ v\in V $

具有吞吐速率上限

$ {B}_{v} $

，待命工位有启用成本

$ {C}_{v} $

。

此外，记

$ \left|w\right| $

为子系统

$ w $

当前已投入使用的工位数量，

$ \left|w\mathrm{_{new}}\right| $

为调度后该子系统实际启用的工位数量（包含新激活的待命工位），

$ \left|w\mathrm{_{max}}\right| $

为该子系统在待命工位全部启用时所能达到的最大工位数量。

1.3 决策变量定义

设置的决策变量如表1所示，主要包括任务准时交付状态、链路与节点启用状态，以及任务在各链路上的吞吐速率和子系统总吞吐速率。变量类型涵盖0−1离散变量与连续变量，用于表示任务调度、资源启用及流量分配等决策。

1.4 多目标优化模型

构建一个分层多目标优化框架，旨在协同优化生产效益、运营成本与环境影响。

1）主要目标：最大化准时交付率

(1)

$ \mathrm{m}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}\;\;ob{j}_{f}=\frac{{\sum }_{t\in T}{y}_{t}}{\left|T\right|} $

式中，

$ ob{j}_{f} $

表示任务准时交付率，即准时交付任务数占任务总数的比例。系统的首要性能指标直接反映了柔性制造系统对客户需求的履约能力。

2）次要目标1：最小化启用成本

(2)

$ \rm{minimize}\; \rm{\mathit{obj}}_1=\frac{\sum_{v\in A_{\text{new}}}^{ }C_vg_v+\sum_{w\in W}^{ }\sum_{m=|w|+1}^{|w_{\text{new}}|}(C_w)^m}{\sum_{v\in A_{\text{new}}}^{ }C_v+\sum_{w\in W}^{ }\sum_{m=|w|+1}^{|w_{\text{max}}|}(C_w)^m} $

式中，

$ ob{j}_{1} $

表示最小化启用成本。包括所有被激活的备用工位节点的固定成本及其接入子系统的扩容代价，该目标旨在避免资源过度配置，在保障产出的前提下实现经济运行。

3）次要目标2：最小化链路启用能耗（低碳）

(3)

$ \mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}\;\;ob{j}_{2}=\frac{{\sum }_{e\in E}{P}_{e}\times {z}_{e}}{{\sum }_{e\in E}{P}_{e}} $

式中，

$ ob{j}_{2} $

表示最小化链路启用能耗。通过最小化链路启用能耗，利用“路径汇聚效应”减少不必要的链路激活。

4）次要目标3：最小化负载不均衡度

(4)

$ \mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}\;\;ob{j}_{3}=\frac{{\sum }_{w\in W}|{\alpha }_{w}-\stackrel-{\alpha }|}{\left|W\right|} $

式中，

$ {\alpha }_{w}=\dfrac{{F}_{w}}{{B}_{w}} $

，为子系统利用率；

$ \stackrel{-}{\alpha }=\dfrac{1}{\left|W\right|}{\sum }_{w\in W}{\alpha }_{w} $

，为系统平均利用率。

避免物料流过度集中于某一特定子系统，预防局部拥堵并减缓设备疲劳，增强系统的整体运行鲁棒性。

1.5 关键约束条件

1）任务完成与需求速率一致性约束。任务完成时，实际速率等于需求速率，未完成时为0

(5)

$ {r}_{t}={D}_{t}{y}_{t},\;\;\forall t\in T $

式中

$ {，r}_{t} $

为任务

$ t $

的实际完成速率。

建立决策变量

$ {y}_{t} $

与物理流量

$ {r}_{t} $

的逻辑关联。若任务被交付（

$ {y}_{t}=1 $

），则其实际速率必须达到额定需求

$ {D}_{t} $

；若任务未完成（

$ {y}_{t}=0 $

），则其实际速率为0。

2）链路容量约束

(6)

$ \sum\limits_{t\in T}{f}_{e}^{\;t}\le {B}_{e}{z}_{e},\;\;\forall e\in E $

该约束具有双重功能：一是限制链路流量不能超过物理带宽

$ {B}_{e} $

；二是通过

$ {z}_{e} $

强制关联链路状态，即只有被激活启用的链路（

$ {z}_{e}=1 $

）才允许承载流量。

3）子系统总吞吐约束

(7)

$ {F}_{w}={\sum }_{e\in {E}_{w}}{\sum }_{t\in T}{f}_{e}^{\;t}\le {B}_{w},\;\;\forall w\in W $

式中

$ {，E}_{w} $

为属于子系统

$ w $

的链路集合。

$ {F}_{w} $

刻画了异构子系统（如整个AGV调度区域）的整体负荷上限。这反映了在多模态物流中，受控制算法、物理空间等因素限制的全局瓶颈效应。

4）工位吞吐上限约束

(8)

$ \sum\nolimits_{t\in T}\left(\sum\nolimits_{e\in\delta^+\left(v\right)}f_e^{\; t}+\sum\nolimits_{e\in\delta^-\left(v\right)}f_e^{\; t}\right)\le B_v,\; \; \forall v\in V $

式中，

$ {\delta }^{+}\left(v\right) $

为工位

$ v $

的出站链路，

$ {\delta }^{-}\left(v\right) $

为工位

$ v $

的进站链路，该约束保障了每个加工或转运工位的进出物料速率不超过其物理操作极限

$ B_v $

，防止工位处发生物料堆积。

2 层次化局部搜索混合整数规划方案

收起

针对柔性制造物流调度中存在的复杂约束及多目标冲突问题，提出一种层次化局部搜索混合整数规划方法（H−LMIP）。该方法通过融合混合整数规划与局部搜索策略，在层次化优化框架下实现对调度问题的高效求解。

2.1 算法整体框架

算法总体流程如图1所示。首先，对输入的车间拓扑与任务需求进行预处理，构建任务流动的扩张图模型。在此基础上，生成任务的候选路径集，将原始大规模调度问题转化为路径索引与流量分配的组合优化问题。随后，建立基于路径集的混合整数规划（MIP）模型，并调用H−LMIP求解引擎进行迭代优化，最终输出各任务的最优搬运路径规划方案。

2.2 候选路径生成策略

为降低在全图范围内进行流量搜索带来的计算复杂度，在由工位节点与子系统链路构成的扩张图上，为每个任务

$ t $

，预先生成一组互异的候选路径集

$ {P}_{\mathrm{t}} $

。其生成过程包含2个阶段：首先基于广度优先搜索（breadth−first search，BFS）生成跳数较少的基础候选路径；随后采用深度受限搜索（depth−first search，DFS）对候选路径集合进行补充，从而在有限候选规模内同时兼顾路径质量与路径多样性。

1）基于BFS的基础路径生成。从任务起点执行广度优先搜索，构建由起点至终点的最短距离层次及相应的前驱关系。在此基础上，从终点沿着前驱关系进行回溯，提取有限数量的互异路径，并对候选路径的最大跳数及生成数量进行限制，从而形成候选路径集

$ {P}_{t} $

的基础部分。

2）基于DFS候选路径扩展。当基于BFS的候选路径数量或多样性不足时，算法进一步从任务起点执行深度受限的深度优先搜索。搜索过程中设置最大搜索深度，并通过限制节点重复访问避免产生简单环路。对于能够到达任务终点且未包含于当前候选集中的路径，将其加入

$ {P}_{t} $

，从而提高候选路径集合的多样性。

得到各任务的候选路径集合

$ {P}_{t} $

之后，引入路径选择变量以描述任务的路径分配。对任意任务

$ t\in T $

及其候选路径

$ p\in {P}_{t} $

，定义0−1变量

$ {x}_{t,p} $

；当任务

$ t $

选用路径

$ p $

时，

$ {x}_{t,p}= $

1；否则，

$ {x}_{t,p} $

=0。记

$ E\left(p\right)\subseteq E $

为路径p所包含的链路集合。基于上述定义，进一步建立路径选择变量与任务交付变量、链路流量变量之间的映射关系。

1）路径选择与任务交付的一致性。对任意任务

$ t, $

至多从候选路径集合

$ {P}_{t} $

中选择一条路径，路径选择变量与任务交付变量满足

(9)

$ \sum\limits_{p\in P_t}{x}_{t,p}={y}_{t},\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\forall t\in T $

2）路径选择与链路流量的映射。设任务

$ t $

的需求速率为

$ {D}_{t} $

。当任务

$ t $

选用路径p时，其需求流量由路径

$ p $

所包含的各条链路承载。因此，任务

$ t $

在链路e上的流量可表示为

(10)

$ {f}_{e}^{\;t}=\sum\limits_{p\in P_t,e\in E\left(p\right)}{D}_{t}\cdot {x}_{t,p},\;\;\forall e\in E,\mathrm{ }\forall t\in T $

基于上述映射关系，链路容量与启用状态约束可表示为

(11)

$ {\sum }_{t\in T}{\sum }_{p\in {P}_{t},e\in E\left(p\right)}{D}_{t}\cdot {x}_{t,p}\le {B}_{e}{z}_{e},\mathrm{ }\forall e\in E$

该约束保证未启用链路不承载任务流量，同时限制已启用链路上的总流量不超过其吞吐上限。

此外，为保证路径选择与链路启用状态的一致性，当候选路径

$ p $

被任务

$ t $

选中时，该路径所包含的链路均须处于启用状态，即

(12)

$ {z}_{e}\ge {x}_{t,p},\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\forall t\in T,\mathrm{ }\forall p\in {P}_{t},\mathrm{ }\forall e\in E\left(p\right) $

3）子系统与工位吞吐约束的路径化表示。基于上述路径选择与链路流量的映射关系，可进一步将子系统吞吐约束与工位吞吐上限约束表示为关于路径选择变量的线性约束。即将

$ {f}_{e}^{\;t} $

代入第1.5节的子系统吞吐约束与工位吞吐上限约束。并据此建立路径选择与链路容量、子系统吞吐及工位吞吐等资源约束之间的对应关系。由此，候选路径生成与前述的数学模型在变量和约束层面实现衔接，后续H−LMIP即在该路径型模型上求解。

2.3 H−LMIP 的动态引导求解策略

在获取候选路径集后，原问题被重构为基于候选路径选择的混合整数线性规划（mixed−integer linear programming, MILP）模型，其中路径选择、任务交付及资源启用等0−1决策具有线性伪布尔（PseudoBoolean）约束结构。所提方法H−LMIP基于Local−MIP，具体求解逻辑如图2所示，其通过在时间预算内循环执行“界限更新−迭代改进”过程实现解的进化。

为解决多目标之间的层次化冲突，设计一种分阶段动态约束引导策略：

1）探索阶段（flexible stage）。在搜索前期，算法将核心算力集中于提升任务交付总数。每次迭代获得更优解时，算法自动更新“最小完成任务数”的下界约束

$ {L}\mathrm{_{min}} $

。

(13)

$ \sum\limits_{t\in T}^{ }y_t\ge{L}_{\mathrm{min}} $

该阶段通过动态抬高主目标的生存门槛，强制搜索进程向高履约率的可行域收敛。此时，对于成本、能耗及负载均衡等次要目标的标量化上界保持宽松，以赋予算法充分的全局探索自由度。

阶段切换机制。为兼顾主目标搜索与次要目标优化，H−LMIP采用时间进度与主目标改进状态相结合的阶段切换规则。具体为：当求解已进入总时间预算的后半段，且主目标在最近一段时间内（取为总时间预算的10%）未获得进一步改善时，算法转入次要目标优化阶段。

2）次要目标优化阶段（fixedtasks stage）。进入该阶段后，已获得的最优交付任务数被锁定为不可再降低的硬约束，算法转而集中改进成本、能耗与负载均衡等次要目标。

该阶段的核心逻辑是：在确保主目标（交付任务数）不退化的前提下，对次要目标进行深度优化。

为有效处理运营成本、链路能耗及负载不均衡之间的复杂博弈，采用标量化（scalarization）方法将多个次要目标转化为单一的综合性能指标

$ S\left(obj\right) $

，即

(14)

$ S\left(obj\right)= {\lambda }_{1}\times ob{j}_{1}+{\lambda }_{2}\times ob{j}_{2}+{\lambda }_{3}\times ob{j}_{3}$

式中，

$ {\lambda }_{i} $

为预设的目标权重系数，用于反映决策者对不同指标的偏好。

在该阶段，算法将下界约束锁定为历史最优交付任务数，同时启动基于标量化指标的上界收紧机制

(15)

$ S\left(obj\right)\le S\mathrm{_{best}}-\varepsilon $

式中

$ ，S\mathrm{_{best}} $

为当前已知的最优标量化得分，

$ \varepsilon $

为搜索步进精度。通过引入权重因子

$ {\lambda }_{1} $

，

$ {\lambda }_{2} $

，

$ {\lambda }_{3} $

，模型成功地将原多维次要目标空间投影为一维搜索方向，从而驱动H−LMIP在保持最高履约率的同时，沿着加权定义的“节能/降本”方向进行定向精炼。

3 实验验证与分析

收起

为全面评估所提算法在处理异构柔性制造调度问题时的求解效率、质量及其在多目标冲突下的权衡能力，开展了数值仿真实验。

3.1 算例构建与实验设置

由于实际工业场景的多样性，为验证所提算法的普适性与鲁棒性，参考典型的柔性加工车间的配置特征，采用随机生成策略构建了一系列不同规模的实验算例（表2）。

1）算例参数规模。算例的拓扑结构与任务负荷涵盖了从低负荷到高拥塞的多种工况。关键参数的取值范围设定见表2。

2）实验环境与评价指标。实验所用的硬件配置如下。

处理器：采用双路 Intel Xeon Gold 6130处理器，每个处理器主频为2.10 GHz，共 64核心，支持128个线程。内存：系统配备1 TB内存。操作系统：使用Ubuntu 22.04.3 LTS 操作系统。

3.2 评估指标

由于本研究问题涉及多个相互冲突的目标，单一维度的指标难以全面客观地反映算法的综合能力。为此，通过平均综合得分R作为核心评价指标，用于定量评价不同算法在各算例上的整体表现。

首先，计算算法

$ i $

在算例

$ j $

上其归一化综合得分S_i,j

(16)

$\begin{split} {S}_{i,j}= &\; \frac{M\times {ob{j}_{f}}_{i,j}+{{\lambda }_{1}}_{j}\times \left(1-{{obj}_{1}}_{i,j}\right)}{M+1}+\\ &\frac{{{\lambda }_{2}}_{j}\times \left(1-{ob{j}_{2}}_{i,j}\right)+{{\lambda }_{3}}_{j}\times \left(1-{ob{j}_{3}}_{i,j}\right)}{M+1}\end{split} $

式中，

$ ob{{j}_{f}}_{i,j},ob{{j}_{1}}_{i,j},ob{{j}_{2}}_{i,j},ob{{j}_{3}}_{i,j} $

分别为算法

$ i $

在算例

$ j $

上求得的交付任务数、启用成本、能耗、负载不均衡度，权重

$ {{\lambda }_{1}}_{j},{{\lambda }_{2}}_{j},{{\lambda }_{3}}_{j} $

为算例

$ j $

给求解器的输入，满足

$ {{\lambda }_{1}}_{j}+{{\lambda }_{2}}_{j}+ {{\lambda }_{3}}_{j}=1 $

，

$ 0\le {{\lambda }_{1}}_{j},{{\lambda }_{2}}_{j},{{\lambda }_{3}}_{j}\le 1 $

，对于每个算例，权重

$ {{\lambda }_{1}}_{j},{{\lambda }_{2}}_{j}, {{\lambda }_{3}}_{j} $

采用随机生成的方式确定。

$ \left|{T}_{j}\right| $

为算例

$ j $

的总任务数，

$ M $

为主目标权重，仅用以评估。

为评估算法在全部测试集上的整体性能，计算算法

$ i $

的平均综合得分

$ {R}_{i} $

(17)

$ {R}_{i}=\frac{1}{n_{\mathrm{inst}}}\sum\limits_{j=1}^{n_{\mathrm{inst}}}{S}_{i,j} $

式中，

$ n_{\mathrm{inst}} $

为测试算例的总数，

$ {R}_{i}\in [0,1] $

，其值越接近1，说明算法在保障高交付率的同时，对系统能耗与成本的控制越优，具有更好的综合权衡能力。

此外，为进一步考察算法在不同工况下获得最优解的概率，引入获胜次数（#win）作为辅助指标，定义为在全部测试算例中，该算法获得最高得分

$ {S}_{i,j} $

的算例总数。该指标用于反映算法在复杂约束环境下的求解稳定性与鲁棒性。

考虑到综合得分R本质上采用标量化方式对多个目标进行的综合评价，为此，进一步引入超体积（hypervolume，HV）指标作为补充评价指标。HV通过计算非支配解集与给定参考点之间所形成的支配区域体积，对算法所得解集的综合质量进行评价，HV值越大，表明所得非支配解集在目标空间中的综合表现越好。

为此，基于4个原始优化目标计算四维HV值。由于任务交付目标

$ {obj}_{f} $

为最大化目标，而其余3个目标均为最小化目标，为统一优化方向，将目标向量表示为

(18)

$ {g=(-obj}_{f},{obj}_{1},{obj}_{2},{obj}_{3}) $

在HV值计算过程中，对各目标维度进行统一的min−max归一化，并采用相同的参考点

$ r=(1.1,1.1, 1.1, 1.1) $

。

对于四维目标空间，采用Monte Carlo方法估计HV值，在区间[0,r]内均匀采样

$ {2\times 10}^{5} $

个点，并根据非支配解集对采样点的支配比例估计超体积。与综合得分R不同，HV直接基于4个原始目标计算，不涉及主目标评价权重M，从而从Pareto前沿角度对不同算法所得非支配解集进行补充评价。

3.3 对比方法

为验证所提H−LMIP算法的有效性，选取Local−MIP、LNS^[24]和NSGA−II 3种方法作为对比算法。其中，Local−MIP作为H−LMIP的消融对比方法，采用与H−LMIP相同的基础求解框架，但不启用第2阶段的任务交付数锁定及次要目标定向优化机制，在整个求解过程中均采用第一阶段的动态下界约束策略，以考察本文所提出的分阶段动态引导策略对算法性能的影响。LNS采用大邻域搜索机制，通过对当前解进行部分破坏与重新优化实现邻域探索。NSGA−II作为经典多目标进化算法，用于从Pareto优化角度提供对比基准。

3.4 结果分析与讨论

选取Local−MIP、LNS 和NSGA−II 3种方法在预设的100组随机算例上进行了对比实验。实验结果如表3所示，其中

$ M $

代表主目标的权重系数，

$ R $

代表对应算法在全体算例上的平均综合得分，#win代表该算法获得最优解的次数。

表3展示了在不同主目标权重M配置下各算法的性能对比结果。实验数据表明，在所有权重设定（

$ M\in $

{1,2,3,4,5}）下，本方法H−LMIP的平均综合得分R和#win均优于Local−MIP、LNS和NSGA−II。随着权重系数M的增大，主目标（交付任务数）的导向作用进一步加强，H−LMIP的综合得分从0.895稳步提升至0.933，且#win由84次增加至86次并保持稳定。Local−MIP的综合得分与H−LMIP较为接近，但其#win仅为47~48次，表明引入两阶段动态约束引导策略后能够进一步改善算法的综合表现。相比之下，LNS和NSGA−II在R和#win指标上的表现均相对较低。总体而言，H−LMIP在不同主目标评价权重下均保持较好的综合性能，体现了其在主目标优先调度需求下的稳定性。

进一步地，为从Pareto前沿角度评价不同算法所得非支配解集的综合质量，表4给出了各算法的HV指标对比结果。H−LMIP取得最高HV值1.055594，相较于Local−MIP、LNS和NSGA−II分别提高约6.25%、32.05%和61.72%。其中，H−LMIP与Local−MIP的HV值相对接近，但仍保持一定优势，表明动态引导策略能够在Local−MIP的基础上进一步改善所得非支配解集的整体质量。LNS和NSGA−II的HV值相对较低，说明其所得解集在四维目标空间中的综合支配范围较小。

同时，通过不同主目标评价权重下的算法收敛曲线进一步比较各方法的求解过程。图3表明，在不同评价权重（M=1~5）下，H−LMIP均表现出较为稳定的收敛趋势。在搜索前期，H−LMIP与Local−MIP的收敛过程较为接近，二者均能够较快获得较高质量的可行解；随着求解过程推进，H−LMIP在中后期仍能对综合评价结果进行进一步改善，而Local−MIP的变化相对有限，这与H−LMIP在后续阶段对主目标进行锁定并进一步优化次要目标的设计相一致。相比之下，LNS和NSGA−II的综合得分整体较低，其中NSGA−II在搜索过程中持续改善，但在给定60 s计算时间内仍未达到H−LMIP的综合评价水平。总体而言，H−LMIP在保持较快前期搜索效率的同时，通过两阶段动态约束引导进一步改善了中后期的综合求解质量。

图4展示了本方法在一典型算例上的动态求解轨迹。为直观呈现多目标的博弈过程，可以看出，算法在搜索初期（前5 s）优先驱动主目标迅速上升，以保障系统极高的任务交付率。随后，在主目标保持稳定的前提下，次要目标呈现出明显的阶梯式优化趋势。这表明在给定权重配置（

$ {\lambda }_{1}=0.063, {\lambda }_{2}=0.372, {\lambda }_{3}=0.565 $

）下，本方法通过分阶段引导策略，能够精准地对成本、能耗与负载均衡进行定向协同精炼。实验轨迹证实，该算法在限定时限内具备持续产生改进解的能力，并能稳健地收敛至兼顾生产效率与绿色运行的最优解域。

4 讨论

收起

采用平均综合得分R、获胜次数（#win）和HV 3个指标对算法性能进行评价。其中，R和#win反映算法在主目标优先的层次化评价下的综合表现，HV则从Pareto前沿角度评价所得非支配解集的整体质量。实验结果表明，H−LMIP在不同评价指标下均表现出较好的综合性能，说明其能够在优先保障任务交付的同时兼顾成本、能耗和负载均衡等次要目标。

与Local−MIP相比，H−LMIP通过引入分阶段动态约束引导机制，在主目标趋于稳定后锁定当前最优任务交付水平，并进一步优化次要目标，从而获得更好的综合性能。与LNS相比，H−LMIP将候选路径选择与资源约束统一纳入局部MIP求解过程，并通过动态约束引导搜索方向，在资源约束高度耦合的情况下表现出更好的求解效果。

与NSGA−II相比，2种方法在多目标处理机制上存在明显差异。NSGA−II通过非支配排序和拥挤距离对多个目标进行并行搜索，而H−LMIP针对本文问题中任务交付优先的层次化特征，采用2阶段动态约束引导机制，首先改善主目标，再在保持任务交付水平的基础上进一步优化次要目标。因此，在本文给定的测试实例和计算预算下，H−LMIP表现出更好的综合优化性能。

此外，所构建的局部搜索框架具有较高的计算效率。通过候选路径的预生成，有效降低了决策空间的规模，使局部搜索能够在较短时间内收敛至高质量解。本文方法适用于主目标优先级明确且约束关系高度耦合的调度优化问题。

5 结论

收起

本研究所提出的H−LMIP算法，通过构建资源冲突模型并引入2阶段动态约束引导策略，实现了生产交付与资源能效之间的协同优化。实验结果表明，H−LMIP相较于Local−MIP、LNS和NSGA−II均表现出更好的综合求解性能。其中，与Local−MIP的对比验证了2阶段动态约束引导策略对改善解质量的有效性；相较于LNS，H−LMIP在复杂资源约束下表现出更好的综合优化能力；相较于NSGA−II，H−LMIP更能体现主目标优先的层次化优化特征。实验表明，该算法采用的主目标优先、次要目标协同优化机制能精准适配智能工厂低碳、高效的层次化运行需求，为复杂环境下的物流调度提供了可靠的解决方案。

基金

收起

国家重点研发计划项目(2023YFB3307500)
国家自然科学基金项目(62522201)

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

葛茂根, 万里, 凌琳, 等. 计及物料运输工装回收的制造车间物料配送路径优化[J]. 机械工程学报, 2025, 61(14): 397-409.

[2]

Zhang L X, Yan Y, Hu Y G. Integrated scheduling of flexible job shop and energy−efficient automated guided vehicles[C]//Proceedings of International Conference on Advanced Robotics and Mechatronics (ICARM). Piscataway, NJ: IEEE, 2023: 493−498.

[3]

Kiesel

, Henke

, Mann

, et al. Techno−economic evaluation of 5G technology for automated guided vehicles in production[J]. Electronics, 2022, 11(2): 192.

[4]

Zhao

Y L

, Liu

X P

, Wang

, et al. Dynamic resource reservation based collision and deadlock prevention for multi−AGVs[J]. IEEE Access, 2020, 8: 82120-82130.

[5]

Yin

L J

, Li

X Y

, Gao

, et al. A novel mathematical model and multi−objective method for the low−carbon flexible job shop scheduling problem[J]. Sustainable Computing: Informatics and Systems, 2017, 13: 15-30.

[6]

Hu B, Seragiotto C, Prandtstetter M, et al. Guiding autonomous vehicles past obstacles–theory and practice[M]//Computer Aided Systems Theory–EUROCAST 2019. Cham: Springer International Publishing, 2020: 271−278.

[7]

李峥峰, 刘阳阳. 考虑充电的多AGV的作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(10): 2872-2879.

[8]

Zhang

, Li

G X

, et al. Emission reduction effect and carbon market efficiency of carbon emissions trading policy in China[J]. Energy, 2020, 196: 117117.

[9]

Pratissoli

, Brugioni

, Battilani

, et al. Hierarchical traffic management of multi−AGV systems with deadlock prevention applied to industrial environments[J]. IEEE Transactions on Automation Science and Engineering, 2024, 21(3): 3155-3169.

[10]

Xiao

H N

, Zhao

, Zhang

, et al. Multi−load AGVS deadlock prevention task scheduling method based on improved imperialist competition algorithm[J]. Complex & Intelligent Systems, 2025, 11(12): 471.

[11]

Meng F C, Meng F H, Lv W G, et al. Large−scale multi−load AGVs conflict−free scheduling based on intelligent e−commerce warehouse[C]//Proceedings of IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA). Piscataway, NJ: IEEE, 2025: 518−525.

[12]

, Yang

H B

, Huang

. Conflict−free scheduling of large−scale multi−load AGVs in material transportation network[J]. Transportation Research Part E: Logistics and Transportation Review, 2022, 158: 102623.

[13]

袁洋, 叶峰, 赖乙宗, 等. 结合负载均衡与 A* 算法的多 AGV 路径规划[J]. 计算机工程与应用, 2020, 56(5): 251-256.

[14]

Tian

, Fan

. Multi−AGV path planning for express distribution center under dynamic priority strategy[J]. Journal of Computer Engineering & Applications, 2023, 59(14): 275.

[15]

Tang

H T

, He

J J

, Zhang

X W

, et al. Hierarchical conflict resolution for multiload AGV path planning[J]. Robotic Intelligence and Automation, 2026, 46(1): 94-105.

[16]

于赫年, 白桦, 李超. 仓储式多 AGV 系统的路径规划研究及仿真[J]. 计算机工程与应用, 2020, 56(2): 233-241.

[17]

Qian Z X, Shi Q S, Wang D, et al. A multi−AGV task scheduling method based on a hybrid adaptive nearest neighbor heuristic algorithm and genetic algorithm[C]//Proceedings of the 2024 3rd International Conference on Artificial Intelligence and Intelligent Information Processing. New York: ACM, 2024: 58−64.

[18]

Yang

S M

, Meng

L L

, Ullah

, et al. MILP modeling and optimization of multi−objective three−stage flexible job shop scheduling problem with assembly and AGV transportation[J]. IEEE Access, 2025, 13: 25369-25386.

[19]

J Q

, Zhang

W M

, Li

J K

. Solving multi−objective energy−efficient flexible job shop problems by a dual−level NSGA−II algorithm[J]. Memetic Computing, 2025, 17(2): 10.

[20]

Deb

, Pratap

, Agarwal

, et al. A fast and elitist multiobjective genetic algorithm: NSGA−II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

[21]

Liu

Q H

, Li

X Y

, Gao

, et al. A multiobjective memetic algorithm for integrated process planning and scheduling problem in distributed heterogeneous manufacturing systems[J]. Memetic Computing, 2022, 14(2): 193-209.

[22]

Coello

Coello C A

. Theoretical and numerical constraint−handling techniques used with evolutionary algorithms: A survey of the state of the art[J]. Computer Methods in Applied Mechanics and Engineering, 2002, 191(11/12): 1245-1287.

[23]

Lin P X, Zou M C, Cai S W. An efficient local search solver for mixed integer programming[C]//Proceedings of International Conference on Principles and Practice of Constraint Programming, 2024.

[24]

Wouda

N A

, Lan

. ALNS: a Python implementation of the adaptive large neighbourhood search metaheuristic[J]. Journal of Open Source Software, 2023, 8(81): 5028.

2026年第44卷第18期

预览PDF | 下载PDF

194

引用本文

BibTeX

文章信息

doi: 10.3981/j.issn.1000-7857.2026.06.00095

接收时间：2026-06-30
首发时间：2026-11-03
出版时间：2026-09-28

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2026-06-30
修回日期：2026-08-14

基金

国家重点研发计划项目(2023YFB3307500)

国家自然科学基金项目(62522201)

作者信息

北京航空航天大学软件学院，北京 100191‌

通讯作者:

罗川（通信作者），教授，研究方向为组合优化、约束求解，电子信箱：chuanluo@buaa.edu.cn

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/kjdb/CN/10.3981/j.issn.1000-7857.2026.06.00095

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT

符号	类型	物理含义
$ {y}_{t} $	0−1变量	任务$ t $是否准时交付
$ {z}_{e} $	0−1变量	链路$ e $是否被启用
$ {g}_{v} $	0−1变量	节点$ v $是否被启用
$ \,{f}_{e}^{\;t} $	连续变量	任务$ t $在链路$ e $上分配的吞吐速率
$ {F}_{w} $	连续变量	子系统$ w $的总吞吐速率

符号

类型

物理含义

$ {y}_{t} $

0−1变量

任务

$ t $

是否准时交付

$ {z}_{e} $

0−1变量

链路

$ e $

是否被启用

$ {g}_{v} $

0−1变量

节点

$ v $

是否被启用

$ \,{f}_{e}^{\;t} $

连续变量

任务

$ t $

在链路

$ e $

上分配的吞吐速率

$ {F}_{w} $

连续变量

子系统

$ w $

的总吞吐速率

参数类别	符号	取值范围/设定值	说明
子系统规模	$ \left\|W\right\| $	$ \left[\mathrm{6,10}\right] $
加工节点规模	$ \left\|A\right\| $	$ \left[\mathrm{500,1000}\right] $
生产任务规模	$ \left\|T\right\| $	$ \left[\mathrm{50,100}\right] $
运行时限	$ cutoff \;$	60 s	单次搜索求解的时间预算

参数类别

符号

取值范围/设定值

说明

子系统规模

$ \left|W\right| $

$ \left[\mathrm{6,10}\right] $

加工节点规模

$ \left|A\right| $

$ \left[\mathrm{500,1000}\right] $

生产任务规模

$ \left|T\right| $

$ \left[\mathrm{50,100}\right] $

运行时限

$ cutoff \;$

60 s

单次搜索求解的
时间预算

M	H−LMIP			LNS
1	84	0.895574	48	0.888721	0.820775	2	0.803797
2	85	0.914677	48	0.910181	0.816247	1	0.793829
3	86	0.924229	47	0.920910	0.813983	1	0.788845
4	86	0.929960	47	0.927348	0.812625	1	0.785855
5	86	0.933780	47	0.931640	0.811719	1	0.783861

H−LMIP

Local−MIP

LNS

NSGA− II

#win

0.895574

0.888721

0.820775

0.803797

0.914677

0.910181

0.816247

0.793829

0.924229

0.920910

0.813983

0.788845

0.929960

0.927348

0.812625

0.785855

0.933780

0.931640

0.811719

0.783861

方法	HV值
H−LMIP	1.055594
Local−MIP	0.993465
LNS	0.799391
NSGA−II	0.652725

方法

HV值

H−LMIP

1.055594

Local−MIP

0.993465

LNS

0.799391

NSGA−II

0.652725