关键词：分布式制造；任务分配；装配线平衡；蚁群算法；模拟退火算法
中图分类号：C931.文献标识码：A
0.引言
随着经济全球化趋势的不断延伸，敏捷制造与制造全球化已引起制造领域的普遍关注，原有的集中式制造系统正逐步被分布式制造系统（DMS）所取代。分布式制造是一种典型的联盟制造方式，分布式制造系统由分散的若干个节点企业所组成，每个节点具有制造系统中的一项或几项功能与资源，通过联盟服务密切协调与合作，共同完成一个或几个制造过程。DMC成员企业可以通过利用已有的、分散各地的设计制造资源，缩短项目设计制造时间，保证产品的质量，降低成本，实现企业间共同盈利。有一种按单生产（MTO）的多级分布式制造系统（MDMS），它的经营特点是产品品种规格多、生产批量小、客户个性化要求高、不适合流水生产作业。因此订单的履行过程通常如下：（1）订单按照一定的规则被分解成很多加工任务，这些加工任务被分配到成员企业执行；（2）加工任务完成后进行统一的装配和包装，并交付客户。
从MTO型生产的订单履行过程可以看出，此种分布式制造系统的生产计划要解决任务分配和装配线平衡两类问题。任务分配问题和装配线平衡问题都属于组合优化问题中的NP-hard问题，如果任务数量巨大，一般的启发式算法难以取得理想的结果。近年来，一些智能算法，如：模拟退火算法、遗传算法、神经网络、禁忌搜索算法以及蚁群算法等被广泛应用于此类组合优化问题的求解。本文将结合实际将这两类问题统一到一个多目标规划模型中。因此，已经被广泛研究的经典模型需要进一步扩展，才能应用于本文MDMS的生产计划的求解。基于模型，设计基于蚁群算法和模拟退火算法改进的智能算法进行求解，最后通过仿真实例证明了算法的有效性。
1.一种典型的多级分布式制造系统
一种典型的MDMS，由若干地理上分散的多个零部件制造公司（CMC）和一个产品装配公司（PAC）组成，产品装配公司内部又有若干条装配线（AL）。各公司之间既是竞争性伙伴（希望合作，但总是力争使自己获益最大），又存在相互依赖（零部件制造公司为产品装配公司提供所需的 零部件）。在此MDMS中，发起合作制造的企业称为项目主企业，其他参与该项目合作制造的企业称为项目伙伴企业。
此MDMS由制造级和装配级两级组成。产品装配级为用户提供最终的产品/服务方案，对用户负责。产品装配级由若干装配线组成，他们承担装配级下达的装配任务，对装配级负责。零部件制造级由一些CMC组成，为产品装配级提供满足产品要求的零部件，对制造级和产品装配线负责。制造级和装配级的生产计划分别由分配模型和装配模型负责。
2.问题描述与模型
2.1.问题描述
某MDMS是一个如图1所示的二级分布式制造系统，在一个生产周期内接到一批订单，MDMS对订单按照一定的规则分解为加工任务，有闲置资源的成员企业对其中的某些或全部加工任务竞标，并向MDMS提交其制造资源的约束状况，由于成员企业地理位置上的分散，将考虑加工任务的产出品从不同的CMC到PAC的运输时间。根据竞标价格和资源约束建立任务分配模型将加工任务分配到具体的CMC，当所有的加工任务完成后统一运送到PAC按照不同订单的需求进行装配，并在本批次订单的交货期之前交付客户。根据上述对订单履行过程的描述和企业的实际情况，建立如下基于任务分配和装配线平衡的多目标生产计划模型。
2.2.MDMS生产计划模型
MDMS任务分配问题有以下特点：（1）加工任务在不同的成员企业完成的时间不尽相同，生产报价也不相同；（2）每个成员企业在同一时刻不能同时完成不同加工任务，同一加工任务也不能被分解成更小的加工任务，而且加工任务一旦开始生产不能中断；（3）成员企业并非对所有的加工任务都有能力生产，部分加工任务仅有部分成员企业可以完成；（4）由于成员企业可能要承担除本期加工任务以外的其他加工任务，因此每个成员企业会提交给项目主企业可进行本次任务的起始时间和总的可用时间，而且总的可用时间是连续的；（5）所有加工任务必须在给定的时间前运送到PCA；（6）零部件从CMC到PAC的运输过程需要时间；（7）任务分配的目标产生一个任务分配方案最小化项目主企业的总成本。
MDMS装配问题有以下特点：（1）装配线（AL）是同质的；（2）每条装配线在同一时刻不能同时完成不同的订单，一个订单也只允许有一条装配线来完成，而且装配任务一旦开始不能中断；（3）对与装配问题的目标有两种类型：Ⅰ给定了装配线节拍，目标是最小化所需的装配线的数量；Ⅱ给定了装配线的数量，目标是最小化装配线节拍。从本质上讲两者的目标都是使得生产率最大化。
3.基本算法介绍
3.1.模拟退火算法（SA）
模拟退火算法（Simulated Annealing Algorithm，SA）是一种适合于解大规模组合优化问题，特别是NP-hard问题的通用有效近似算法。由Boltzmann有序性原理可知，固体退火过程遵循热平衡封闭系统的热力学定律——自由能减少定律：对于与周围环境交换热量而温度保持不变的封闭系统，系统状态的自发变化总是朝着自由能减少的方向进行，当自由能达到最小值时，系统达到平衡态。 算法持续进行 “产生新解-判断-接受/舍弃”的迭代过程就是对应着固体在某一恒定温度下趋于热平衡的过程，也就是执行了一次 Metropolis算法来产生组合优化问题的解，其对应的转移概率为：
（9）
在根据旧解搜索得到新解时，如果新解的函数值小于旧解，则接受新解为当前解；否则根据与一个随机数的比较来确定是否接受新解。式中（温度）表示控制参数。开始让取较大的值，使的值较大，进而新解被接受的概率也较大，在此下达到热平衡后，再缓慢降低的值，如此重复，随着值得变小，也随之变小，从而新解被接受的概率也变小，当满足停机规则时，一般能收敛到一个全局近似最优解。
3.2.蚁群算法（ACA）
蚁群算法是20世纪90年代由意大利学者M-Dorigo等人首先提出的一种新型的模拟进化算法。蚁群算法的基本原理是：当蚂蚁在搜索食物源的过程当中，会在其所走过的路径上释放一种特殊的分泌物——信息素，一定范围内的蚂蚁在寻找食物的过程中都会受到这种信息素的影响。当某些路径上走过的蚂蚁越来越多，留下的这种信息素也越多，以致后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的吸引强度。利用这种正反馈机制，最终蚂蚁群体能够在食物源与蚁巢之间找到一条最短的最优路径。
在蚁群算法中，首先每只蚂蚁根据状态转移方程构造一个完整的解，然后再根据解的情况更新信息素的数值，如此重复便能够收敛到一个全局近似的最优解。
4.MDMS生产计划模型算法设计与流程
4.1.算法设计
1．装配问题的模拟退火算法
在模拟退火算法中，有三个主要的因素需要解决，它们分别是（1）解的编码和译码（2）新解的产生方式（3）冷却进度的控制。
Ⅰ类装配问题的模拟退火算法
Ⅰ类装配问题是给定了装配线节拍，目标是最小化所需的装配线的数量。
（1）编码和译码
采用订单序列编码方式，按订单分派至装配线的先后顺序，将订单排成一行，称为编码。然后根据编码表示的装配顺序，将订单依次分配到每条装配线，满足一条装配线的所有订单处理时间之和不超过节拍时间，称为译码。例如，若给定订单数目为9，节拍时间为10，译码后问题的解为{2，3，5，6}，{1，9，7}，{8，4}，装配时间分别为10，10，8。
（2）新解的产生方式
新解采用随机交换方式产生，随机交换方式是指从一个解（编码）中任取两点，将两点互换位置后形成新的解（编码）。
（1）编码和译码
采用订单补码序列编码方式，在原有订单数目的基础上增加相同数目的虚拟订单，并做适当处理，使得补码后的订单数目能被给定装配线条数整除。按补码订单分派至装配线的先后顺序，将订单排成一行，称为编码。然后根据编码表示的装配顺序，将订单依次分配到每条装配线，一条装配线分配的订单数为补码后的订单数目与装配线条数的商，称为译码。例如，若给定订单数目为4，装配线条数为3，译码后问题的解为{2，3，5}，{6，1，9}，{7，8，4}，装配时间分别为4，5，2。
（2）新解的产生方式
新解采用2变换邻域方式产生，2变换邻域是指从一个解（编码）中任取两点，将两点间的路径反向后形成新的解（编码）。
（3）冷却进度控制
与Ⅰ类装配问题的模拟退火算法的冷却进度控制相同。
