基于蚁群算法的紧急定制型供应链订单调度研究

刘 亮，李宏娟，于来源（中国航天科工飞航技术研究院物资供应站，北京 100074）

0 引 言

目前各企业面对紧急或变更的定制型订单，采取的方法只能是被动地打乱原来生产计划，进行插单式生产，而不能做到对企业订单和生产资源的系统统筹规划。由于紧急定制订单的动态不易操控性、不确定性、柔性等特征的存在及其研究对企业实际指导的实用性，人们对其进行了大量的研究[1-2]。国内主流的优化思想是“延迟策略”，它是通过寻找不同定制产品所包含的相似点和差异点——用户订单解耦点（CODP），使不同产品的相同程序尽可能最大化，然后利用模块化的思想，采用模块、标准化的零部件以及标准的环节，以延迟对客户个性化需求那部分的处理[3-4]。

但从现有文献看，具体对紧急定制型供应链的研究主要集中在信息集成和管理层面，缺乏指导供应链运作的研究[5]。所以本文选取在供应链环境下有定制要求的紧急订单为研究对象，着重分析紧急定制订单的典型特征，从中挖掘出其在调度过程中存在的主要瓶颈问题，在“特征—瓶颈—解决思路”的分析过程中，形成了紧急定制订单的供应链调度优化模型及优化方法，并将瓶颈问题的解决思路以优化目标和约束条件的方式引入供应链调度优化模型及其求解过程中。

1 紧急定制供应链调度的特征分析及瓶颈优化

1.1 基本特征分析。定制生产的优化目标是旨在以大批量的生产效率满足不同客户个性化需求[6]。而紧急定制是定制型生产的一种，是具有严格交付时间限制的定制型生产方式，最显著的特点表现在时间的紧迫性。和常规订单相比，紧急订单具有较高的全局优先级，即为了满足紧急订单的按时交付，它有权在到达生产企业时，首先进行排产，造成插单生产，打乱了原有的生产计划，同时更增加了企业的生产成本。

“供应链调度”作为一个专业术语，在近5年的供应链管理文献中频频出现，这里引用马士华教授对供应链调度的定义，他认为供应链调度是供应链各成员在信息共享的基础上，为了达到缩短产品交货期，降低整条供应链运作成本的目标，实行联合（或协同）的调度[7]。在紧急定制的情况下，供应链调度体现出很多新的特点：首先紧急定制模式下的供应链是动态型供应链，而非稳定型供应链。其次它是一种阶段性平衡和阶段性倾斜交替的供应链体系。再者紧急定制模型下的供应链体系是一种能适应一定交货期时间要求和定制需求的体现快速响应能力的反应型供应链。

1.2 紧急定制供应链调度的瓶颈优化。通过对上述特征的剖析，发现了影响和制约调度过程顺利有效进行的关键问题，即三大瓶颈：一是“紧急需求同定制延迟策略作用发挥之间的矛盾”。这是因为定制产品优化的效果很大程度上取决于标准化和模块化程度实现的水平，这一点毋庸置疑。但是模块化实现的最大前提条件是“成组生产技术”，而“成组生产”的生产条件是企业具有多个生产任务同时进行，单一产品的生产显然谈不到成组。想要实现成组技术，必须要等到多个订单任务的集中生产，而多个生产任务的集中必须具有一定的等待时间，但紧急订单要求在很短的交货期，这一点是矛盾问题的关键。二是“紧急定制需求同供应链生产能力约束之间的矛盾”。紧急订单是随机无规律的，企业不能对紧急订单进行提前预测以及预留产能。再者紧急订单的交货期短。但是供应链要及时交付订单，就需各阶段节点企业都在紧急订单调度时刻，有能够满足订单所需的可用生产能力。而实际中，每个企业的生产能力都是有限的。三是“紧急订单收益同额外支出之间的矛盾”。这里的额外支出包含两方面内容，一是以额外库存成本的形式的支出，另一个是以增加的生产成本形式的支出。

对于第一种瓶颈问题，本文采用“订单二级分类”的方法将其弱化。具体研究思路是，先对客户定制化订单进行基本需求信息状况的分析，然后将不同订单的相似部分进行重新组合，弱化原有不同订单的相互排斥性。矛盾转化后，基于相似性重新组合的订单，延迟策略在紧急定制供应链体系中就可以比较有效地发挥作用。本文客户订单的初级分类是以交货期（T）为标准，二级分类以产品的定制程度（D）为依据。分类后如表1所示：

表1 客户订单按定制程度分类类别

按照客户订单的特点将订单划分为如上表11类。为了在订单信息系统进行订单信息处理时简化信息操作作业，本文采用字母标注。d表示需要定制生产的零件，t代表零件是通用型。对于订单的划分类型说明如下：以Dd-t-Dt-t型为例，该类订单指，成品是定制型产品，且由定制部件装配而成，其中定制部件，一部分是由定制型零件与通用型零件组成，一部分是由通用型零件组成。

在上述瓶颈二和瓶颈三的分析过程中不难发现，这两个瓶颈是在同一个逻辑过程中先后诞生的。所以，对这两个瓶颈问题的缓解也放在同一调度分析过程中。这里选取链上任一节点企业A作为研究对象，引入时间成本因子θ这一变量。

由图1得：ΔC=C-CSΔT=Ti=TS-T=t-ts

式中，K（t）是以比例系数，随着时间t动态变化。

这里设θ（t）=-K（t）c（t）ts（t）

通过以上的推导过程可得，额外支出的生产成本ΔC（t）随着紧急订单空余生产时间的增加而增大，即两者呈正比关系，这也恰印证了实际情况，指出了ΔC（t）的实际意义——它是紧急订单在该阶段该企业的生产时间t（t）与由于压缩原定生产导致的生产成本 ΔC（t）增加的一个量度，所以我们称之为时间成本因子。这里我们就通过Δ（t）的引入，将由于压缩原定生产所导致的额外生产成本支出实现了定量化和显化。

2 紧急定制供应链调度优化模型的构建及蚁群算法

2.1 紧急定制供应链调度优化模型构建。通过以上分析，构建调度非线性规划模型如下：

模型涉及的建模符号及含义说明如下：

表2 紧急定制模型下供应链调度优化模型参数及变量说明

下面对优化模型各式进行详细分析说明：

式（1）：紧急定制订单的交货期最短优化函数，是实现客户满意度的基本条件。

式（2）：基于本文对研究对象的选定（即非暴利订单），目的是优化定制产品的生产成本。

式（3）：动态空余生产能力约束关系，保证了在供应链中每一阶段中所有节点的空余生产能力之和必须大于该时刻在该阶段生产的所有定制任务所需的生产能力总和。

式（4）：节点企业收益约束。是参与调度的协助节点企业在接受订单任务时，对自己收益的核算，即企业自身也要盈利。

式（5）：定制产品生产的归属唯一性约束，即保证了每一生产任务都由其对应的协作企业完成，不会出现重复生产的现象。

2.2 紧急定制供应链调度的蚁群优化算法。蚁群算法是对自然界蚂蚁寻找路径的方式进行模拟而得出的一种仿生算法。蚂蚁在搜寻食物的过程中，蚁群总能找到一条从食物到蚁穴之间的最优路径。

下表给出紧急定制供应链调度同蚁群算法的具体对应描述。

表3 紧急定制供应链调度同蚁群算法的对应类比

为了直观说明蚁群算法的设计过程，首先给出了供应链网络的一个示意图。

（1）蚂蚁的构造

单程蚂蚁：为了切合本文研究，本文构造的蚂蚁为单程蚂蚁。

蚂蚁分类：按照第二章的订单分类法，每一类订单对应一类蚂蚁。

蚂蚁可行域：由于单个企业的收益喜好和紧急订单对生产能力的要求，不是全部的企业都可以参与调度，可以参与调度的节点企业构成了蚂蚁的可行域。

（2）蚂蚁选择路径概率

1）吸引概率

表4 路径对蚂蚁的吸引信息素及概率

2）排斥概率（见表5）

3）蚂蚁选择路径的概率

通过以上关于路径对蚂蚁的吸引概率和排斥概率的分析，分别得出两个目标函数（生产时间、生产成本）中蚂蚁对路径的选择概率为：

关于生产时间优化目标：

表5 排斥信息素量和排斥概率

关于生产成本优化目标：

信息素的更新规则

由于本文构造的蚂蚁属单程蚂蚁，所以，对于节点企业信息素的更新就不能依靠蚂蚁自行完成，需设定一个信息素的更新原则，由算法完成。

吸引信息素（π）的更新规则：

排斥信息素（Ψ）的更新规则：

算法具体运行步骤如下：（1）供应链接收客户订单，确定调度时刻。（2）对订单进行分类，根据订单类别构造相应的蚂蚁类别。（3）根据各企业的基础生产数据（可用空余生产能力、生产时间等）确定蚂蚁运行的可行域；蚂蚁遗留的信息素量，不同节点的吸引/排斥概率。（4）通过历史经验，给出算法中各优化指标的期望满意水平——算法收敛依据。（5）根据实际设定和调整α、β、γ、ε参数的值。（6）在源点随机产生t批蚂蚁，每批包含各类蚂蚁，每类蚂蚁每次为30只。（7）按更新规则，对可行域内每条路径上的信息素进行更新。（8）当t批蚂蚁跑过后，记录通过各节点的蚂蚁数量。（9）蚂蚁再加一批，即t=t＋1，重复第8步骤，直到每个节点的蚂蚁数量稳定。（10）稳定后，计算优化指标值，判断是否达到期望值，如没有，转到步骤5。如果一直达不到期望值，则转到步骤4重新审视期望值，对其进行修正。（11）按结果中各类蚂蚁的分配数量分配生产任务，进行供应链订单调度。

3 紧急定制供应链调度优化算例

算例给出供应链结构如图3所示：

图3 热传输复合铝制品及其供应链结构

该供应链某段时间内接到客户订单情况。（见表6）

仿真之前，根据供应链实际情况，核心企业设定，算法中随机生产蚂蚁数为每批30个，运行50批。如前分析α代表路径对蚂蚁的吸引系数，β表示不同类蚂蚁间排斥系数，γ指同类蚂蚁间的排斥系数，因此，核心企业取值αT=αC=0.7，γT=γC=0.2，βT=βC=0，关于两个优化目标，我们给出期望满意值为：生产成本＜15 000元/吨，交货期＜9天，这里设定的交货期比较严格，反映了该验证模型中对交货的准时性方面的限定性。（见图4）

在上述算法基本参数设定的基础上，按照上一章蚁群优化算法的步骤，运用MATLAB7.0执行算法，关于选择企业收敛性、规模生产效益收敛性、生产成本及交货期收敛性的运行结果和对结果分析如下：

图5为蚂蚁选择协作成员的分布情况及收敛状况，可以看出，算法开始时，各个路径上（企业）都有蚂蚁经过，但随着算法的进行，越来越多的蚂蚁选择了供应商L2、L4，放弃了L1、L3（表示订单主要集中在其中两家生产），且路径上（企业）蚂蚁数量都趋于稳定，说明蚂蚁选择企业具有收敛性。蚂蚁选择其中两家企业来分配订单生产，实现了定制产品的规模效益。在4家供应商中，由于L2生产时间较少，L4虽然生产时间稍高，但具有很大的成本优势，所以，蚂蚁在交货期要求严格的情况下，大量选择了L2进行生产，但考虑到生产成本的约束，在交货期允许的情况下，也选择了L4进行生产，以上说明仿真结果也是符合实际生产经验的。

规模生产效益已经在图5中蚂蚁的收敛性上得到了体现，为了更加清晰地说明模型算法的规模效益，本文分别以规模效益满意水平和交换期满意水平为考虑目标，用优化算法进行仿真，如图6。图上反映了铝锭生产的规模效益和交货期满意水平变动情况，从图中可以清晰看出，随着算法的进行，当各批次蚂蚁数目达到稳定状态时，规模效益及交货期满意水平也趋于稳定，且各自逐渐收敛接近100%和80%。

以上结果从企业选择、规模效益、生产成本和交货期四个方面验证了算法的可收敛性，通过上述分析可以看出，各项目标均达到了算法可行性的验证。

表6 热传导铝产品供应链在某段时间内接到的客户订单情况

4 结 论

本文在前人研究的基础上，以制造业的紧急定制生产为研究目标，在这一方面进行了一些基础性的研究，主要的创新是从紧急定制订单表现出来的基本特征出发，挖掘出影响紧急订单及时交货的3个主要“瓶颈”问题，并在这些瓶颈问题深入分析的基础上，针对本文的研究侧重点，给出了化解或解决这些瓶颈问题的有效方法，最后通过算例验证了模型和算法具有很强的实用性和有效性。

[1]G J Stalk.Time-the next source of competitive advantage[J].Harvard Business Review,1988,66(4):41-51.

[2]G J Stalk,T M Hout.Competing against time:How time-based competition is reshaping global markets[M].New York:Free Press,1990.

[3]顾新建，祁国宁，徐福缘.大批量定制生产模式的定量分析算法[J].中国机械工程，2001(3):312-315.

[4]李仁旺，祁国宁，顾新建.大批量定制生产及其实施方法初探[J].中国机械工程，2001(4):405-408.

[5]姚建明，蒲云.MC模式下供应链调度的优化模型[J].系统工程，2005(8):36-41.

[6]Jiaojianxin,Maqinhai,Tseng motchell M..Towards High Value-added Products and Services:Mass Customization and Beyond[J].Tecjmpvatopm,2003,23:809-821.

[7]马士华.供应链管理[M].北京：机械工业出版社，2000.