考虑制造资源竞拍方案组合的平台订单接收与调度优化

Optimization of Platform Order Acceptance and Scheduling Considering the Portfolio of Manufacturing Service Resource Bidding Options

摘要

针对制造平台竞拍机制下的订单接收与调度问题，提出一种考虑制造资源竞拍方案组合的优化方法。以制造资源提交的子任务竞拍方案集为输入，以子任务间的工艺关联关系、同一制造资源的任务调度等为约束，构建了考虑平台收益和行业用户满意度的订单接收与调度混合整数线性规划模型。提出了自适应大规模邻域搜索算法，设计了三层染色体编码结构、邻域关联移除算子、基于笛卡儿积搜索策略的修复算子以及制造资源调度方案的可行解修复策略。人工算例和汽车燃油箱制造案例验证了模型与算法的有效性。相比于平台当前采用的两种规则型方法，所提方法使平台收益分别提高9.83%和61.06%，用户满意度分别提高29.23%和61.54%。

Abstract

This paper addresses the order acceptance and scheduling problem under a combinatorial auction mechanism on a manufacturing platform. Taking the set of subtask bidding schemes submitted by manufacturing resources as input， and considering both the process correlation constraints among subtasks and the scheduling constraints within each resource， a mixed-integer linear programming model is formulated to maximize platform revenue and user satisfaction. An adaptive large neighborhood search algorithm is developed， featuring a three-layer chromosome encoding structure， a neighborhood correlation removal operator， a repair operator based on the Cartesian product search strategy， and a repair strategy for resource scheduling feasibility. The effectiveness of the proposed model and algorithm is validated through artificial instances and a real-world case of automotive fuel tank manufacturing. The results show that， compared with two rule-based methods currently used by the platform， the proposed method increases platform revenue by 9.83% and 61.06%， and improves user satisfaction by 29.23% and 61.54%， respectively.

Graphical abstract

关键词

制造资源 / 竞拍方案组合 / 制造平台 / 订单接收与调度 / 自适应大规模邻域搜索

Key words

manufacturing resources / combinatorial auctions / manufacturing platform / order acceptance and scheduling / adaptive large neighborhood search

0 引言

我国制造业具有区域产业集中、中小企业多且单独应对产业升级能力弱等特点。制造平台将中小企业制造能力服务化，实现制造资源的共享与交易，能提高生产资源利用率，降低中小企业生产与交易的成本，推动 “产品交付”向“服务交付”的范式转变^［1-2］。MFG、Protolabs、择幂科技、海智在线等制造平台均按这种价值主导逻辑构建核心业务能力。作为一种平台化制造服务模式，行业用户需求的多样性与随机性、制造资源服务能力的不可知性与难预测性使平台运营在供需匹配与调度上面临难题^［3］。

从平台是否事先掌握制造资源服务能力的角度出发，可将该供需匹配与调度问题分为“订单选制造资源”的单向匹配和“订单与制造资源互选”的双向匹配^［4-5］。针对单向匹配问题，龚小容等^［6］提出一种基于贝叶斯网络的机床装备资源优化选择方法，ZHANG等^［7］开发了一种考虑服务能力时间窗约束和订单可拆分的服务匹配方法，罗遵昊等^［8］构建了任务服务时间不确定的云制造任务调度模型。双向匹配同时权衡服务供需双方的满意度及行为。任磊等^［9］运用期望效用理论计算供需双方满意度，文献［10-11］将主体偏好纳入双边匹配模型，王莉静等^［12］综合考虑平台佣金、供需双方满意度，构建了共享制造供需匹配模型。

竞价拍卖是刻画主体行为的一种有效方法^［13-14］。在反向拍卖领域，MA等^［15］提出了基于保证金竞价的多属性逆向拍卖模型；在拍卖与优化决策融合方面，王雅娟等^［16］设计了考虑交易成本的多属性在线双边拍卖机制；在双重拍卖与多属性协商层面，CHENG等^［14］提出了基于双重拍卖的供需匹配方法，KANG等^［17］针对制造服务分配问题设计了多属性协商机制。上述竞拍方法主要针对独立型任务，即任务之间没有强工艺关联约束。现实情况是行业用户提交的需求往往是复杂产品，需要分解为具有严格工艺约束的多个子制造任务后才能通过竞拍机制匹配最优的制造资源^［18］。工艺约束使得平台在组织竞拍时除了关注制造资源的最优投标决策外还需对竞拍方案进行组合优化才能确定最终的获胜方案。方案组合的可行性最终决定了行业用户提交的需求订单能否被选择并服务，由此催生了一类新的订单接收与调度问题——考虑制造资源竞拍方案组合的订单接收与调度（order acceptance and scheduling considering biding portfolio of manufacturing servicers， OAS-BPS）。

本文针对OAS-BPS问题，构建数学规划模型并设计求解算法。研究的理论贡献如下：①结合制造平台通过竞拍实现供需匹配的现实场景，提出一种新的订单接收与调度（OAS）问题；②构建综合考虑平台收益和用户满意度的OAS-BPS混合整数线性规划模型；③开发自适应大规模邻域搜索（adaptive large neighborhood search， ALNS）算法进行求解，并通过人工算例和现实案例验证算法有效性。

1 问题描述与模型构建

1.1 问题描述

基于竞拍的平台制造服务供需匹配实现流程如图1所示，具体包括如下5步：

1）行业用户根据加工需求向平台提交包含产品需求量、价格等信息的加工订单（manufacturing order，MO）。

2）平台收到MO后，根据产品的工艺结构将订单分解成多个具有工艺关系约束且能发包给制造资源的制造任务（manufacturing task，MT）。

3）平台根据分解后的MT信息为每个MT筛选候选制造资源集，并将具体的MT加工要求广播给对应的候选制造资源。

4）每个候选制造资源根据接收到的任务广播信息，结合自身产能状态，自主确定并向平台提交包含服务价格、服务时间窗的竞拍方案。

5）平台汇集制造资源提交的竞拍方案，并根据MT的工艺要求确定最优的竞拍方案组合、MT完成时间及对应的订单接收方案。

本文提出的OAS-BPS聚焦步骤5），以制造资源提交的竞拍方案为基础信息，构建OAS模型。模型的输出为订单接收方案、订单对应子任务的制造资源匹配方案及其完成时间。假设平台收到的来自行业用户的制造订单号集合为Ω，其中，第i（i∈Ω）个制造订单可分解成一个MT，第i个制造订单所有MT的编号集合为γ_i，所有MO分解后将形成最终的MT，这些MT编号全集为γ（\gamma =\underset{i\in \Omega }{\cup }{\gamma }_i）。制造资源根据平台广播的子任务信息，结合加工工艺属性和生产状态，确定最优竞拍方案

\begin{array}{cc}{\Gamma }_{jr}=\{p_{jr},T_{jr}^{\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{s}\mathrm{t}},T_{jr}^{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{t}}\}& j\in \gamma ,r\in R\end{array}

其中，p_jr、T_{jr}^{\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{s}\mathrm{t}}、T_{jr}^{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{t}}分别为制造资源r对任务j的竞拍价格、承诺的最早交付时间和最迟交付时间，均为已知的决策信息；R为制造资源集合。基于此，OAS-BPS可描述为：考虑订单i与任务j的对应关系和任务之间的工艺约束关系，对制造资源提供的竞拍方案进行组合优化，以确定最优的OAS决策。若竞拍方案能组合形成一条面向订单i的服务路径，则平台接收订单i，同时，将订单对应的子任务分配给对应的制造资源，并根据服务时间窗确定最优的服务完成时间。竞拍方案组合考虑两类约束：同一订单多个子任务的工艺关系约束；一个制造资源的多个最终获胜竞拍方案之间的调度冲突约束。为方便后续模型构建，提出如下假设：

假设1　每个订单只对应一类产品。一个订单包含多个产品只会增加子任务分解的难度，不会影响OAS-BPS模型的通用性。

假设2　一个订单分解出的每个子任务不能被分割且只能确定一个获胜的制造资源。若某个子任务的加工量较大，需分配多个制造资源，则只需将该子任务进一步分割成多个相互独立的子任务并为其选择一个制造资源。

假设3　一个制造资源可同时承接多个类型的制造任务。

假设4　一个制造资源只能按顺序完成竞拍获胜的制造任务。一个制造资源若有可并行处理不同制造任务的多类型生产资源，则将这些资源视为独立的制造资源。

假设5　制造资源提交的竞拍方案事先可知。制造资源如何根据平台广播的制造任务信息确定最优的投标方案已有大量研究^［16-17］，本文不将该问题作为研究重点。

假设6　制造服务资源之间的物流成本忽略不计。相比于订单的加工成本，物流服务成本占比较小，可忽略不计^［4］。

1.2 模型构建

结合现有OAS决策目标和平台型企业的实地调研，将平台OAS的决策目标分解为接收订单的收益最大化与行业用户满意度最大化。行业用户满意度是衡量平台战略客户关系维护水平的核心指标。平台为每个订单赋权以表征其对行业用户的重视程度，并将最大化的接收订单权重和作为行业用户满意度最大化的量化指标。

基于上述目标函数和给出的约束条件，建立面向OAS-BPS的数学规划模型：

\mathrm{m}\mathrm{a}\mathrm{x}{F}_{\mathrm{1}}=\sum _{i\in \Omega }{w}_i{x}_i（1）

\mathrm{m}\mathrm{a}\mathrm{x}{F}_{\mathrm{2}}=\sum _{i\in \Omega }{\rho }_i{x}_i-\sum _{j\in \gamma }\sum _{r\in R}{p}_{jr}{y}_{jr}（2）

s.t.　 \begin{array}{cc}\sum _{r\in R}{y}_{jr}=x_i& \forall i\in \Omega ,j\in {\gamma }_i,r\in R\end{array}（3）

\begin{array}{cc}{T}_{jr}^{\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{s}\mathrm{t}}{y}_{jr}\le C_{jr}\le T_{jr}^{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{t}}{y}_{jr}& \forall j\in {\gamma }_i,r\in R\end{array}（4）

C_{j^{\text{'}}{r}^{\text{'}}}-t_{j^{\text{'}}{r}^{\text{'}}}^{\mathrm{p}\mathrm{r}\mathrm{o}}{y}_{j^{\text{'}}{r}^{\text{'}}}\ge C_{jr}+t_{r{r}^{\text{'}}}^{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}}+M[m_{j{j}^{\text{'}}}(y_{jr}+y_{j^{\text{'}}{r}^{\text{'}}}-\mathrm{1})-\mathrm{1}]（5）

∀r，r′\inR；j，j′\in\gamma且j≠j′

\begin{array}{cc}\underset{j\in \gamma ,r\in R}{\mathrm{m}\mathrm{a}\mathrm{x}}\{C_{jr}\}\le T_i& \forall i\in \Omega \end{array}（6）

C_{j^{\text{'}}{r}^{\text{'}}}-t_{j^{\text{'}}{r}^{\text{'}}}^{\mathrm{p}\mathrm{r}\mathrm{o}}{y}_{j^{\text{'}}{r}^{\text{'}}}\ge C_{jr}+t_{r{r}^{\text{'}}}^{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}}+M[m_{j{j}^{\text{'}}}(y_{jr}+y_{j^{\text{'}}{r}^{\text{'}}}-\mathrm{1})-\mathrm{1}]（7）

\begin{array}{ccccc}{x}_i,y_{jr}\in \{\mathrm{0,1}\}& C_{jr}\in {\mathbb{R}}^{+}& i\in \Omega & j\in \gamma & r\in R\end{array}

式（1）表示由接收订单权重和决定的最大化客户满意度，其中，w_i 为订单i的权重；x_i 为0-1决策变量，若订单i被接收，则x_i =1，否则x_i =0。式（2）表示最大化平台订单接收的收益（由新接收的订单价格ρ_i 、制造资源的竞拍价格即平台支付给制造资源的费用p_jr 决定），其中，y_jr 为0-1决策变量，若选择制造资源r面向任务j的竞拍方案，则y_jr =1，否则y_jr =0。式（3）表示订单和子任务的关系约束，即若订单i被接收，则订单i的子任务j必须分配且仅能分配给一个制造资源。对所有订单的子任务按顺序编号，若存在5个订单，每个订单包含3类子任务则有γ₁=｛j₁，j₂，j₃｝，γ₂=｛j₄，j₅，j₆｝，…，γ₅=｛j₁₃，j₁₄，j₁₅｝，以保证式（3）所示约束的正确性。式（4）表示任务服务完成的时间窗约束，即子任务j由制造资源r的实际服务完成时间C_jr 必须不早于竞拍方案约定的最早交付时间，且不晚于约定的最迟交付时间。式（5）表示一个订单内子任务间的服务时间约束，即紧后任务的服务启动时间不早于紧前任务的服务完成时间与运输时间之和，其中，t_{jr}^{\mathrm{p}\mathrm{r}\mathrm{o}}为制造资源r完成子任务j需要的时间；t_{r{r}^{\text{'}}}^{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}}为制造资源r到r′的物流运输时间；m_jj′ 为子任务的关联参数，若子任务j是子任务j′的紧前任务，则m_jj′ =1，否则m_jj′ =0；M为一个无限大的实数。式（6）表示订单交付时间窗约束，即订单i的子任务完成时间必须在订单要求的交付时间T_i 之前。式（7）表示一个制造资源内的子任务调度时间约束，即一个制造资源只有完成当前任务后才能启动下一个任务。

本文构建的优化模型属于多目标优化问题，解决这类问题的一种通用方法是将其转化为单目标优化^{［10，18］}。这种转化的合理性在于加权和法得到的每个最优解均为原多目标问题的帕累托最优解，能在简化模型的同时保证解的有效性^［19］。目前，将多目标转化为单目标的方法主要有线性加权法、优先级法，但线性加权法使用最广泛^［20］。决策目标均为最大化目标函数（式（1）、式（2）），可采用归一化并线性加权的方式将多目标优化问题转化为单目标优化问题，转化后的单目标为

\mathrm{m}\mathrm{a}\mathrm{x}F={\alpha }_{\mathrm{1}}\frac{\sum _{i\in \Omega }{w}_i{x}_i}{\sum _{i\in \Omega }{w}_i}+{\alpha }_{\mathrm{2}}\frac{\sum _{i\in \Omega }{\rho }_i{x}_i-\sum _{j\in \gamma }\sum _{r\in R}{p}_{jr}{y}_{jr}}{\sum _{i\in \Omega }{\rho }_i-\sum _{j\in \gamma }\underset{r\in R}{\mathrm{m}\mathrm{i}\mathrm{n}}\{p_{jr}\}}（8）

式中：α₁、α₂分别为决策目标1和目标2的权重，α₁+α₂=1。

所提规划模型存在非线性约束（式（6）），为方便求解，对其进行线性变化

\begin{array}{cc}{C}_i^{\mathrm{m}\mathrm{a}\mathrm{x}}\le T_i& \forall i\in \Omega \end{array}（9）

\begin{array}{cc}{C}_{jr}\le C_i^{\mathrm{m}\mathrm{a}\mathrm{x}}& \forall j\in {\gamma }_i,r\in R,i\in \Omega \end{array}（10）

式中：C_i^{\mathrm{m}\mathrm{a}\mathrm{x}}为中间变量。

2 自适应大规模邻域搜索算法

OAS与竞拍方案的优化均是典型的NP-hard问题^［21-22］，结合二者的OAS-BPS问题同样具有NP-hard特征，需开发高效的启发式算法求解大规模实例。ALNS作为自启发式优化算法，通过动态评估算子性能并自适应调整算子选择概率，实现解空间探索深度与局部最优解利用强度的平衡。

2.1 初始解生成

采用图2所示的三层编码结构对可行解进行编码。解结构的第一层（订单层）采用二进制编码，即用数值1表示接受订单，0表示不接收订单。第二层（任务层）采用整数编码，其中，元素序号对应任务编号，元素值对应制造资源编号。第三层为任务服务完成时间层，其中，元素序号对应任务编号，元素值对应任务的实际服务完成时间。

初始解的生成分为4个步骤，具体过程如图3所示。

（1）订单接收方案初始化。初始默认接收全部订单，即订单层所有元素的值均设为1，任务层与交付时间层所有元素的值均为0，如图3a所示。

（2）随机分配制造资源与计算服务完成时间。遍历任务集，依次为每个子任务随机匹配一个候选制造资源，若子任务为第一个任务，则将对应制造资源竞拍方案给出的最早交付时间作为该任务的服务完成时间；否则向前遍历，并将订单内和制造资源内的紧前任务服务完成时间的最大值作为该子任务的最终完成时间。判断该完成时间是否满足竞拍方案服务时间窗约束，若不满足，则该分配方案不可行，对应订单不接收，其余子任务不被分配，结束对该订单任务的搜索，然后搜索下一个订单任务，直至遍历所有订单任务。

（3）判定约束与修复可行解。检查订单对应的所有子任务是否满足工艺关系约束，若不满足，则不接收该订单，并将对应的任务层和任务服务完成时间层的元素值均调整为0。逐一检查子任务，考察子任务分配给对应制造资源后的任务完成时间是否会与该制造资源现有任务的服务时间冲突。若出现冲突且无法调整，则该任务对应的订单不被接收，并将任务层和任务服务完成时间层的元素值均调整为0。

（4）分析时间复杂度。修复可行解主要包括工艺关系约束检查和资源调度冲突检查。假设订单数量为I，第i个订单包含J_i （J_i ≥3）个子任务，第i个订单的第j个子任务在制造资源r中的调度位置为S_ijr，则工艺关系约束检查的时间复杂度为\sum _{i\in \Omega }\frac{J_i(J_i+\mathrm{1})}{\mathrm{2}}，资源调度冲突检查最坏情况下的时间复杂度为\sum _{r\in R}\sum _{i\in \Omega }\sum _{j\in {\gamma }_i}{y}_{jr}(S_{ijr}-\mathrm{1})。

2.2 设计破坏-修复算子

2.2.1 设计破坏算子

（1）移除未接收订单。破坏算子将未接收的订单移入待接收订单集，并等待新的订单接收和任务调度决策。

（2）破坏邻域关联。针对制造资源重叠（交付时间相近的任务对同一资源的需求导致资源供应出现冲突）的特征，对未接收订单进行联动破坏。采用逆向路径搜索策略搜索未分配订单，配对提取每个未分配订单及其在序列中的后继订单，由此构建待接收订单集。

2.2.2 笛卡儿积搜索组合策略

笛卡儿积搜索组合策略基于破坏算子生成的破坏订单集合，为修复算子预先确定满足订单中子任务工序约束的制造资源组合集及其对应的任务服务完成时间组合集，如图4所示，其中，实体方块表示制造资源对任务j的服务时间窗，虚线方块表示紧前任务j′在计算后的理论时间窗。具体步骤如下：

1）生成紧前任务列表。从订单子任务链的末端开始逆向查找，得到与任务具有紧前关系的任务列表。如图4所示，若任务4、5、6为并行关系，且三者均完成后才能开始任务7，则任务7的紧前任务列表为｛4，5，6｝；若任务4、5、6、7为串行关系，则任务7的紧前任务列表为｛6｝。

2）可行资源搜索。反向搜索任务j的紧前任务序列，记录满足任务j工艺约束的制造资源r和最迟服务完成时间C_jr，以及任务满足j′工艺约束的制造资源r′和最迟服务完成时间C_j′r′。若订单1中编号为1、2、3的子任务需按顺序依次加工，则将制造资源的最迟服务完成时间T_{\mathrm{35}}^{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{t}}、T_{\mathrm{36}}^{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{t}}设为任务3的服务完成时间，即C_{\mathrm{35}}=T_{\mathrm{35}}^{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{t}}，C_{\mathrm{36}}=T_{\mathrm{36}}^{\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{t}}，其中，任务3的制造资源集合R₃=｛5，6｝，任务2的制造资源集合R₂=｛4，7｝。

3）可行资源组合。通过笛卡儿积组合搜索出可行制造资源，进而得到相应的服务完成时间组合的集合。对于步骤2）中的可行资源，先将任务3的制造资源加入资源组合的集合｛｛5｝，｛6｝｝，对应的服务完成时间组合的集合为｛｛C₃₅｝，｛C₃₆｝｝，然后将任务3与任务2的制造资源组合更新为｛｛4，5｝，｛4，6｝，｛7，5｝，｛7，6｝｝，同时根据资源组合与完成时间的对应关系更新服务完成时间组合的集合。重复上述笛卡儿积组合操作，直至遍历该订单的全部任务。

（4）选择资源组合方案，计算服务完成时间。若无法在制造资源r为任务j、资源r′为任务j′提供的服务时间窗内安排出符合工序约束的服务完成时间组合，则删除相应的制造资源组合和任务服务完成时间组合；否则更新并记录内最终的可行资源组合和相应的时间组合。如图4所示，为订单1中的编号为1、2和3的子任务的制造资源组合｛1，4，5｝、｛2，4，6｝选择资源组合方案、计算服务完成时间。对整条资源链检查每个任务的资源可用时间窗是否与紧前任务确定的理论可开始时间窗重叠，若所有任务均满足重叠条件，则该资源链可行，并将每个时间重合部分的最迟时间作为最迟服务完成时间。图4所示的任务1、2、3的资源组合集合中，资源组合｛1，4，5｝对应可行交付时间组合｛5，9，14｝；组合｛2，4，6｝中的资源2与资源4的可行时间窗无重叠，导致时间链断裂，故该组合不可行，应从集合中删除。

2.2.3 设计修复算子

破坏算子引入扰动后，算法基于笛卡儿积搜索组合策略生成的资源组合集合，设计如下两种修复算子，以有效修复解、探索新解空间、提升解的质量。

1）随机修复算子。从笛卡儿积搜索组合策略生成的资源组合集中随机选择一个满足订单内所有子任务关系约束的制造资源组合，并将其作为新的可行解。

2）贪婪修复算子。为获得最大利润，采用贪心原则从笛卡儿积搜索组合策略生成的资源组合集中选择总投标价格最低的制造资源组合，并将其作为新的可行解。

2.3 制造资源调度方案的可行解修复策略

为保障制造资源内的任务调度在任务分配后满足时间约束，提出了基于逆序搜索的制造资源调度可行解修复策略。采用逆序搜索策略，逐项比对每个子任务的所有前序任务。两个子任务使用同一制造资源时，若交付时间不满足调度时间约束，则通过时间窗滑动策略搜索可行时间。可行时间晚于竞拍方案中任务的最迟交付时间的情况下，若两个子任务来自同一个订单，则拒绝接收该订单；若两个子任务来自不同订单，则不接收前序任务对应的订单。

ALNS算法涉及的权重更新机制、轮盘赌选择机制、模拟退火接受准则参考文献［23-24］，不再赘述。

3 算例分析

为全面评估ALNS性能，笔者参考文献［25］设计了2个单邻域基准算法（“关联破坏+随机修复”（简称单邻域1）、“关联破坏+贪心修复”（简称单邻域2））、1个两邻域精简算法（“关联破坏配合自适应选择修复”）。本文采用三种规模的人工算例测试算法性能，采用现实案例说明算法的有效性。

人工算例中，订单数量设为10、30、40、60和70，制造资源数量定为8、9和10，两者交叉组合形成不同规模的人工算例。每组算例中的子任务均存在一定的工艺约束关系。算例的对比项为使用对应求解算法运行5次所得结果的均值与最大值，以及运行时间均值。

3.1 算法参数调优

参考文献［26］，对ALNS算法的算子表现增加分数、权重更新参数与降温率进行参数调优。采用L₉（3³）正交表进行三因素三水平的田口正交试验。每个参数组合在3个规模的问题上独立运行5次，先采用最小-最大标准化方法处理原始结果，再将各组合的“整体标准化均值”作为性能评价指标。调优后的算子表现增加分数为［1，4，16］，权重更新参数为0.1，降温率为0.9975，其中，［1，4，16］表示对于每次迭代中使用的算子生成解，若该解劣于当前解但被接受准则接受，则算子加1分；若该解优于当前解但未达到全局最优，则算子加4分；若该解成为新的全局最优解，则算子加16分。需要注意的是，算子表现的初始分数为0。

3.2 算法性能对比分析结果

设置算法的终止条件为迭代5000次，在此条件下分析ALNS算法与对比算法的性能差异。如表1所示， ALNS算法在中小规模（订单规模不超过40）下具备优异的求解性能，ALNS算法的目标函数均值与CBC精确解的偏差小于0.783%；在订单数-制造资源数为40-10、60-10及订单数为70的算例下，CBC因计算复杂度呈指数增长而无法求解，ALNS算法能稳定输出近似最优解；迭代5000次时，ALNS算法的计算时间较两邻域算法平均缩短21.6%~31.07%，具有更好的搜索性能。

3.3 权重灵敏度分析

为探究订单接收的收益权重α₁与用户满意度权重α₂对决策结果的影响，设计了权重敏感性实验。如表2所示，α₁从0.30增至0.45时，收益提高27.03%且收益对权重调整高度敏感，但满意度保持稳定；α₁从0.45增至0.95时，收益增大8.92%，满意度降低35.48%；α₁从0.3减至0.05时，满意度大幅增大，收益变为大幅亏损。实验数据证明ALNS算法在价格-权重多属性决策中的适应性，即通过调节权重，平台可灵活制定“收益优先”“用户维系”或“均衡发展”策略。

3.4 现实案例结果分析

选择某平台通过竞拍生产汽车燃油箱的实例来验证模型和算法在真实工业场景中的有效性。

3.4.1 案例描述

平台接收用户发布的8个订单，每个订单均包含7项子任务，其中，前6项为并行子任务，第7项为装配任务。订单信息发布后，10家企业参与竞拍，并给出具体的服务时间窗、服务价格等参数。

3.4.2 结果分析

迭代5000次的求解结果如表3所示，对于目标函数均值，ALNS与CBC的相对误差为3.81%；对于算法运行时间的均值，两邻域搜索是ALNS的2.22倍。

平台当前主要采用的两种规则型决策方法：①规则1，优先接收高价值订单，即倾向选择报价低的制造资源；②规则2，侧重高满意度订单，即倾向选择交付快的制造资源。如表4所示，对于目标函数值，ALNS比规则1、规则2分别提高19.7%和61.3%，突破了单一规则无法兼顾多目标的局限，在收益和满意度上实现同步优化。更重要的是，ALNS接收全部订单，解决了规则1漏接订单1、6与规则2漏接订单3、5、6的问题，实现了全局资源的优化配置。

4 结语

制造平台通过竞拍机制接收订单与优化调度时，面临多源任务工艺约束、竞拍方案组合复杂、跨订单资源调度冲突等挑战，提出一种考虑竞拍方案组合的OAS优化框架。为支撑平台化制造环境下的OAS决策，构建了以平台收益和用户满意度为核心目标的混合整数线性规划模型，并针对模型的NP-hard特性，设计了由三层染色体编码结构、邻域关联移除算子与笛卡儿积搜索策略等组成的ALNS算法。人工算例与真实案例验证了模型和算法的有效性。后续研究可考虑任务在制造网络之间的物流成本，形成订单接收、任务分配与调度、物流路径规划等联合决策优化模型。此外，本文假设所有制造服务资源的竞拍方案事先给出，未来可将制造资源竞拍与OAS-BPS联合，构建分层优化方法，以实现上层平台订单接收、下层制造资源竞拍决策的联合优化。

参考文献

[1] CHAUDHURI A， DATTA P P， FERNANDES K J， et al. Optimal Pricing Strategies for Manufacturing-as-a Service Platforms to Ensure Business Sustainability［J］. International Journal of Production Economics， 2021， 234： 108065.

[2] 杨涛， 蒋芳. 基于R-GRA的云制造协同服务主体评价研究［J］. 中国机械工程， 2025， 36（9）： 2097-2107.

[3] YANG Tao， JIANG Fang. Research on Evaluations of Cloud Manufacturing Collaborative Service Entities Based on R-GRA［J］. China Mechanical Engineering， 2025， 36（9）： 2097-2107.

[4] BAO Yuguang， MING Xinguo， ZHANG Xianyu， et al. Platform-based Task Assignment for Social Manufacturing （PBTA4SM）： State-of-the-art Review and Future Directions［J］. Journal of Manufacturing Systems， 2025， 78： 328-350.

[5] LIU Zhaohui， WANG Zhongjie， YANG Chen. Multi-objective Resource Optimization Scheduling Based on Iterative Double Auction in Cloud Manufacturing［J］. Advances in Manufacturing， 2019， 7（4）： 374-388.

[6] 晏鹏宇， 杨柳， 车阿大. 共享制造平台供需匹配与调度研究综述［J］. 系统工程理论与实践， 2022， 42（3）： 811-832.

[7] YAN Pengyu， YANG Liu， CHE Ada. Review of Supply-demand Matching and Scheduling in Shared Manufacturing［J］. Systems Engineering-Theory & Practice， 2022， 42（3）： 811-832.

[8] 龚小容， 李孝斌， 尹超. 云制造环境下基于贝叶斯网络的机床装备资源优化决策方法［J］. 中国机械工程， 2018， 29（20）： 2438-2445.

[9] GONG Xiaorong， LI Xiaobin， YIN Chao. Optimization Decision Method of Machine Tool Resources Based on Bayesian Network under Cloud Manufacturing Environments［J］. China Mechanical Engineering， 2018， 29（20）： 2438-2445.

[10] ZHANG Xumei， CAO Duanyang， DAN Bin， et al. The Capacity Matching Problem of the Third-party Shared Manufacturing Platform with Capacity Time Windows and Order Splitting［J］. International Journal of Production Research， 2024， 62（17）： 6167-6185.

[11] 罗遵昊， 余乐安， 王杜娟， 等. 任务服务时间不确定下基于事件关联的云制造任务调度研究［J/OL］. 系统工程理论与实践， 2025： 10.12011/SETP2024-1746. （2025-05-15）.

[12] LUO Zunhao， YU Lean， WANG Dujuan， et al. Event Correlation-based Task Scheduling in Cloud Manufacturing with Uncertain Service Time［J/OL］. Systems Engineering⁃Theory & Practice， 2025： 10.12011/SETP2024-1746. （2025-05-15）.

[13] 任磊， 任明仑. 基于竞争与协同效应的复杂制造任务一对多双边匹配模型［J］. 计算机集成制造系统， 2018， 24（5）： 1110-1123.

[14] REN Lei， REN Minglun. One-to-many Two-sided Matching Method of Wisdom Manufacturing Task Based on Competition and Synergy Effect［J］. Computer Integrated Manufacturing Systems， 2018， 24（5）： 1110-1123.

[15] LI Baodong， YANG Yu， SU Jiafu， et al. Two-sided Matching Model for Complex Product Manufacturing Tasks Based on Dual Hesitant Fuzzy Preference Information［J］. Knowledge-Based Systems， 2019， 186： 104989.

[16] LIU Peng， ZOU Ying. Two-sided Matching Model of Shared Manufacturing Resources Considering Psychological Behavior of Agents［J］. Discrete Dynamics in Nature and Society， 2021， 2021（1）： 7491913.

[17] 王莉静， 马志鑫， 徐梦杰. 考虑全局满意度的共享制造平台供需双边匹配模型［J］. 计算机集成制造系统， 2025， 31（11）： 4313-4323.

[18] WANG Lijing， MA Zhixin， XU Mengjie. Supply-demand Bilateral Matching Model of Shared Manufacturing Platform Considering Global Satisfaction［J］. Computer Integrated Manufacturing Systems， 2025， 31（11）： 4313-4323.

[19] 彭云龙， 肖勇波. 基于优先权拍卖的产能分配机制研究［J］. 中国管理科学， 2021， 29（12）： 105-114.

[20] PENG Yunlong， XIAO Yongbo. Capacity Allocation Mechanism Based on Priority Auctions［J］. Chinese Journal of Management Science， 2021， 29（12）： 105-114.

[21] CHENG Yuxin， YU Chunxia， XU Suxiu， et al. A Novel Supply-demand Matching Model for Shared Manufacturing Resources［J］. International Journal of Computer Integrated Manufacturing， 2025， 38（10）： 1399-1423.

[22] MA Benjiang， ZHOU Zhongmin， BASHIR M F， et al. A Multi-attribute Reverse Auction Model on Margin Bidding［J］. Asia-Pacific Journal of Operational Research， 2020， 37（6）： 2050032.

[23] 王雅娟， 聂炎炎， 王先甲. 基于多属性在线双边拍卖的冷链物流运输服务采购机制［J］. 中国管理科学， 2025， 33（7）： 253-261.

[24] WANG Yajuan， NIE Yanyan， WANG Xianjia. Transportation Service Procurement Mechanism for Cold Chain Logistics Based on Multi-attribute Online Double Auction［J］. Chinese Journal of Management Science， 2025， 33（7）： 253-261.

[25] KANG K， TAN B Q， ZHONG R Y. Multi-attribute negotiation mechanism for manufacturing service allocation in smart manufacturing［J］. Advanced Engineering Informatics， 2022， 52： 101523.

[26] YANG Dong， LIU Qidong， LI Jia， et al. Multi-objective Optimization of Service Selection and Scheduling in Cloud Manufacturing Considering Environmental Sustainability［J］. Sustainability， 2020， 12（18）： 7733.

[27] LIU Xin， REYNOLDS A C. Gradient-based Multi-objective Optimization with Applications to Waterflooding Optimization［J］. Computational Geosciences， 2016， 20（3）： 677-693.

[28] HUANG La， CHEN Jiawei. Weighted Robust Optimality of Convex Optimization Problems with Data Uncertainty［J］. Optimization Letters， 2020， 14（5）： 1089-1105.

[29] KUMAR R A， KARTHEEBAN K. Resource Allocation Using Dynamic Pricing Auction Mechanism for Supporting Emergency Demands in Cloud Computing［J］. Journal of Parallel and Distributed Computing， 2021， 158： 213-226.

[30] ZHU Qinghua， TANG Huan， HUANG Jiajie， et al. Task Scheduling for Multi-cloud Computing Subject to Security and Reliability Constraints［J］. IEEE/CAA Journal of Automatica Sinica， 2021， 8（4）： 848-865.

[31] SUN Hao， WU Tingying， BAI Qinyang， et al. Improved Adaptive Large-scale Neighborhood Search Algorithm for Electric Vehicle Routing Problem with Soft Time Windows and Linear Weight-related Discharging［J］. Expert Systems with Applications， 2025， 280： 127344.

[32] YANG Senyan， ZHANG Ruiyan， MA Ying， et al. Adaptive Large Neighborhood Search Incorporating Mixed-integer Linear Programming for Electric Vehicle Routing Problem with Mobile Charging and Nonlinear Battery Degradation［J］. Applied Soft Computing， 2025， 175： 112988.

[33] HE Pengfei， CHEN Wenchong， WU Qinghua， et al. Capacitated Profitable Tour Problem with Cross-docking［J］. Computers & Operations Research， 2025， 181： 107077.

[34] HE Lei， GUIJT A， de WEERDT M， et al. Order Acceptance and Scheduling with Sequence-dependent Setup Times： a New Memetic Algorithm and Benchmark of the State of the Art［J］. Computers & Industrial Engineering， 2019， 138： 106102.

基金资助

浙江省哲学社会科学规划课题(23NDJC156YB)

国家自然科学基金(72201082)