面向整车混流装配线客户订单的优化分配排序

李苏珂 刘盛强 喻道远 张三强 史登松 何世林

1．华中科技大学数字制造装备与技术国家重点实验室，武汉，430074 2．中国重型汽车集团有限公司，济南，250022

0 引言

混流装配线有时也特指混合车型组装线，其特点是在一定时间内，在一条生产线上生产出多种不同型号的产品，产品的品种可以随顾客需求的变化而变化［1－2］。作为当前离散制造业普遍采用的一种生产方式，混流装配生产涉及不同的产品、复杂的装配过程及品种繁多的物料，因而其计划排序与执行管理问题比一般的流水生产更为复杂［3］。以往的研究主要集中在单一生产线混流装配排产顺序优化方面，常用的优化目标有两个：基于生产负荷平衡的目标和基于物流平顺化的目标［3］。随着国内区域经济的不平衡发展，经济发达地区的制造型企业为了节约生产本，产品制造基地逐渐向经济欠发达的地区转移。而处于不同地域的产品制造基地的生产能力、人力和资源成本各不相同，这种跨地域的混流生产模式给制造型企业带来了巨大的挑战。因此，探索如何在充分利用产能的情况下，对订单进行合理分配和排序，使处于不同地域拥有不同生产能力和特点的生产线制造出总成本最低的产品，具有很强的实际意义。

1 问题描述和数学模型

考虑一个大型的汽车制造集团在不同地方共设有M条生产线，能够生产N种型号的汽车，但各条生产线能够生产的汽车型号不尽相同，集团一共拥有K个客户，所有的客户订单由企业的计划部统一接收并分配到各条生产线，在这里为了保证订单的完整性，所有订单不做合并或者拆分处理。根据调研得到集团订单的分配原则：

（1）考虑资源约束，在生产线产能得到充分利用的情况下，将每一计划期内的订单合理地分配到各条生产线，使得在销售淡季时能够将少量订单集中在一条或几条生产线生产，在销售旺季时能够发挥各条生产线的优势，避免订单流失，提升集团的市场占有率。

（2）由于各条生产线所在地域和构造存在差异，导致即使生产同种车型，其生产节拍、生产成本、物流成本、人力成本等都可能不一样。因此在追求成本最低、交货期最短的目标下，尽量将订单分配给生产时间短、成本低的生产线。

（3）在生产订单少、不能满负荷生产的情况下，应该兼顾各条生产线的利益，尽量平衡工人间的收入。

（4）各条生产线的生产负荷尽可能达到均衡。

企业每隔一定周期发布生产计划，每个计划发布周期包含T个时间段，每个时间段内客户的订单需求都必须尽量得到满足，如果超过交货日期，企业将会付出相应的惩罚成本。因此，企业的优化目标是：在产能允许和产能得到充分利用的情况下，依照客户需求，合理地安排客户订单的生产地点和上线顺序，按时交货，最终使产品制造总成本得到降低。综上所述，对该问题建立如下数学模型：

目标函数1 制造总成本最低：

式中，Anm为生产线m生产车型n的约束；Pnmt为生产线m在t时间段内生产订单n超期的罚金；Cnm为生产线m生产车型n的单位生产费用；Qnmt为生产线m在t时间段生产车型n的数量；Mnm为生产线m生产车型n的单位物料成本；Tnm为生产线m生产车型n的单位运输费用；Lm为当前企业的生产负荷率；DLTn为车型n的订单交货期；Rnmt为生产线m在t时间段内生产车型n的实际生产能力；R′nmt为生产线m在t时间段内生产车型n的理论产能；Dnkt为在t时间段内客户k对车型n的需求。

目标式（1）使所有订单的惩罚费用、生产费用、物料成本、运输费用之和最小；目标式（2）使各条生产线生产负荷尽可能均衡；约束式（3）使得生产量为非负，并且限制在生产线产能之内；约束式（4）表示准时制生产，生产量等于需求量；约束式（5）表示约束A是0或1的调整变量；约束式（6）表示订单不可拆分。

2 求解算法

本文所求解的问题是一类典型的NP－har d难题，目前针对此类问题主要有以下三类算法［4］：①最优解算法，如分支定界法、整数规划法、动态规划法；②试探算法，如目标追随法；③循环改进法，如模拟退火算法、遗传算法等。其中，遗传算法自其被提出以来已经在调度领域得到了广泛的应用，但是它也存在容易陷入早熟、爬山能力差的弱点，所以许多学者提出了改进的遗传算法，禁忌遗传算法（TSGA）和递阶遗传算法［5］就是其中两种重要的方法。禁忌搜索能够有效克服最优解陷入局部最优的问题，它主要针对遗传算子进行改进，不需要改变编码的结构，而递阶遗传算法不对遗传算子进行更改，它通过改善编码结构来克服早熟的问题，所以二者存在较强的互补性。基于以上思想，本文采用禁忌 — 递阶遗传算法［6］（THGA）来求解本文的问题。

2．1 编码

THGA的染色体由控制基因（CG）和参数基因（PG）两部分组成，其中基因是一串二进制数，控制基因中的1表示被其控制的基因处于激活状态，0表示被其控制的基因处于失活状态，它们分别模拟了生物进化过程中染色体上的显性和隐形基因。在遗传的过程中，显性基因有可能成为隐形基因，而隐性基因亦有可能成为显性基因。参数基因的有效性由控制基因决定。图1为T HGA染色体编码示意图。

图1 THGA染色体编码示意图

2．2 适应度函数

目标函数要通过标定来映射为适值函数，合适的标定可以防止早熟的发生，常用的标定方法有动态线性标定、幂率标定、对数标定等。本文使用正规化技术进行标定，它通过将目标函数f映射到（0，1）区间，从而抑制超级染色体。对于本文的最小化问题标定如下：

2．3 选择策略

当完成个体的适应值计算后，将由选择策略完成对这一代个体的选择工作，赌轮法和排序法是最常用的两种选择方法，本文将两种选择方法结合起来使用。

2．4 禁忌遗传算子

为了克服遗传算法爬山能力弱的缺点，将禁忌搜索算法（TS）特有的记忆功能引入到普通的遗传算法（GA）算子中，由此重新定义了禁忌交叉算子（TSCO）、禁忌变异算子（TSMO），使得T HGA拥有更强的爬山能力。禁忌交叉算子根据交叉概率Pc随机地交换种群中两个个体的部分基因，禁忌变异算子根据变异概率Pm随机地改变父代染色体的某些基因位的值。显性操作模拟自然界的二倍体现象，它能够解决动态环境下复杂系统的优化问题，易于跟踪环境的动态变化过程，它能保护所记忆的基因免受有害选择运算的破坏［7］。禁忌遗传算子中描述基因的字符集为｛0，1，10｝，其中1表示显性的1，10表示隐性的1。具体映射关系如下所示：（0，0）→0；（10，0）→0；（1，0）→1；（0，10）→0；（10，10）→1；（1，10）→1；（0，1）→1；（10，1）→0；（1，1）→0。

3 应用举例

为了验证本模型及算法的实用性，本文分别选取了某汽车制造企业淡季、正常季、旺季三个时期的典型订单来进行说明，如表1所示，所有订单的交货期为7天，如超期则每台车罚金为3000元／天。企业信息如表2和表3所示。目前企业的订单分配原则是：M1车分配给1、2号生产线生产，M2车分配给3号生产线生产，M3车分配给4号生产线生产。

表1 某批订单信息表

表2 某汽车制造企业4条生产线生产能力信息表

表3 某汽车制造企业4条生产线生产成本信息表

设初始序列为123412341，表示1～9号订单分别分配给1、2、3、4、1、2、3、4、1号生产线，用序列编码123412341表示。同时设计了两级控制基因，第一级控制基因有9位，全部为1，处于激活状态，第二级控制基因均为4位，可以取0或1，分别控制参数基因是否激活。仿真模型中算法的参数设置如下：初始种群20，交叉概率Pc＝0．8，变异概率Pm＝0．1，运行8代，获得20组Pareto解，如表4、图2～图4所示。

表4 淡季、正常季、旺季的20组Pareto解

图2 淡季的20组Pareto解

图3 正常的20组Pareto解

图4 旺季的20组Pareto解

分析图2～图4可以明显看到，最优解即是离坐标轴原点最近的那个点，即表4中序号为1的一组解。最优解的详细数据如表5所示，各条生产线负荷情况如图5所示。从图5中可以看出，在生产淡季时各条生产线负荷差距大一些，这是因为为了节约成本而将订单集中为某一条或几条生产线的结果，当订单变多，到了生产的正常季节和旺季时，各条生产线的生产负荷率就变得趋于平均了。同时，从表5可以看出，经过优化的订单分配原则与现有的订单分配原则相比，在生产成本的控制和生产线负荷均衡度上均有了明显的改观，从而进一步验证了算法的有效性。

表5 淡季、正常季、旺季最优解

4 结语

针对某汽车企业的实际情况提出了以制造总成本最小和生产线负荷均衡为目标的数学模型，同时将禁忌—递阶遗传算法应用到该模型，并且选取了3组较具代表性的分别反映销售淡季、正常季和旺季的订单，得出了比较满意的结果。本文提出的模型和方法可以合理地优化配置处于不同地域不同生产线的生产任务，降低企业生产成本。该方法也可供其他整车制造型企业借鉴。

图5 各条生产线负荷图

［1］ 赵伟，韩文秀，罗永泰．准时生产方式下混流装配线的调度问题［J］．管理科学学报，2000，3（4）：23－28．

［2］ Zhao Xiaobo，Zhou Zhaoying，Asres A．A Note on Toyota’s Goal of Sequencing Mixed Models on an Assembly Line［J］．Co mputers ＆ Industrial Engineering，1999，36：57－65．

［3］ 黄刚．混流装配生产的计划排序及其执行过程管理［D］．武汉：华中科技大学，2007．

［4］ 孙新宇，万筱宁，孙林岩．蚁群算法在混流装配线调度问题中的应用［J］．信息与控制，2002，32（6）：486－490．

［5］ 郑丕谔，马艳华．RBF神经网络的递阶遗传训练新方法［J］．控制与决策，2000，15（2）：165－168．

［6］ 柯珂，张世英．禁忌－递阶遗传算法研究［J］．控制与决策，2001，16（4）：480－483．

［7］ 汪定伟，王俊伟，王洪峰，等．智能优化方法［M］．北京：高等教育出版社，2007．