多品种变批量拉链生产计划优化方法研究

关键词：生产计划； 多品种变批量； 遗传算法

中图分类号：TP39 文献标识码：A文章编号：2095-2163（2013）05-0081-04

0引言

随着时代的发展，变批量多品种生产模式应运而生，因其有着灵活应对市场变化、满足客户多样需求，提高企业市场竞争力等诸多优点[1]。已有众多学者对多品种变批量进行了深入的研究并提出各种生产优化模型[2]。凭此契机，本文也研究了一种多品种变批量情况下的生产计划优化方法。

多品种变批量生产是一种根据待制造产品的品种和批量变化，而快速调整生产计划的生产模式。该模式面向生产任务和生产资源，以快速重排、重复利用的方式快速调整生产计划，使得生产功能、生产能力和生产过程得到快速改变，以实现产品多品种、变批量的柔性生产[3]。变批量生产强调生产过程中的产品的不确定性，包括产品品种的不确定性，产品数量的不确定性。变批量多品种生产中的生产资源还应该具备柔性。由于拉链生产的多品种变批量特性，在实际生产中都是将变批量的产品整合为多个子批的产品而统一安排生产，在满足每个子批的交货量和交货期的情况下，采用生产计划优化方法，实现最短生产周期[4]。

由于生产计划问题通常存在着很多约束，使其成为非常难解的NP完全性复杂的优化问题，如果采用常规的精确算法，将难以在较短时间内找到问题的最优解，于是引入遗传算法。目前，遗传算法已成为生产计划优化等NP难问题的研究实现热点和实用解决方法。本文提出了一种新的生产计划问题的多种群遗传算法，该算法通过随机产生两个初始种群，各自进化，并彼此迁移，每个种群都产生局部最优解，相互比较获得全局最优解。

1问题描述

多品种变批量的拉链制造企业在计划期收到一批订单，由于品种与批量的不确定性，整理后分为N子批产品，通过生产资源设备、模架、模具的相应组合以实现产品的生产。由于设备出模次数，模具的出模个数和模架上安放模具个数等约束，设备生产每种产品的生产能力可能各不相同。由于设备和产品等约束，产品在各个设备的生产计划会导致完成所有批次产品的生产周期不一样。

2模型建立

2.1确定多品种产品分成子批的生产序列

首先根据接收到的订单计划将其按产品类型、批量大小和交货期分为子批，具体步骤如下：

（1）按产品类型分成不同种类产品批次。

（2）再按每种产品的交货期进行分批。每个满足相近交货期生产的产品将合成为同一批次。

（3）若某种批量的交货量并未超过最大批量限制，则将其分为一批。否则将最大批量分为一批，超出部分按照（3）再重新分批。

这样共分成了N个子批的产品，再对这N个子批生成生产次序：

（1）确定每个子批包含的所有产品的交货期，并以其中的最小交货期作为整个子批的交货期。

（2）将所有子批按照交货期从小到大进行依序生产。

（3）交货期相同的子批，交货量小的和不可延迟的则要优先生产。

（4）产生最终生产序列。

2.2确定子批序列的生产计划模型

本模型的主要任务是在综合各种生产资源生产能力的情况下，进行生产计划优化。在完成这些子批产品生产的基础上，生成各个设备完成这批订单的生产计划。第5期陶小晶：多品种变批量拉链生产计划优化方法研究智能计算机与应用第3卷

在拉片压铸车间，有设备、模架和模具。每台设备安放一台模架，由于模架与模具的组合，每台模架上安装的模具数量不定，设备上安放的模架通常为限定。在某段时间内，接到一批订单，每个订单需要的产品多种多样，需要的产品批量也有大有小，产品的交货期也有分段。假设将该批订单整合，然后分成N个子批进行生产，该模型要在满足全部订单的各种产品交货量和交货期的前提下，根据生产资源的生产能力，生成将所有设备分配给各种产品以完成这批订单的生产计划。该计划将使得完成该批订单的生产周期最小。

此处，假设每台设备每天工作8小时；这N个子批产品在每台设备上按各子批优先顺序生产；模架上更换模具时间忽略；拉片生产设备有限，模架和模具数量足够；模架安放不同的模具时个数不定；每台设备在同一时刻只能生产一种拉片产品；每种产品在模具上生产之前的准备工作都不考虑；过程不考虑突发事件，所有资源正常工作；每种产品的交货量与交货期已知；按照整理过后的批次顺序进行排产。

综合上述各假设条件，可得子批序列的生产计划模型如下：

模型中，MSmin为最小生产周期；MSj为设备j的生产时间；DNi为第i批产品的交货量；DTi为第i批产品的交货期；Ej为安放在设备j上的模架的出模次数；bij为子批i的产品在设备j的模架上可安放的模具数量；ci为出模子批i的产品的模具每次出模个数；aij为标志是否将设备j分配给子批i进行生产；tij为将设备j分配给子批i的生产时间。

3优化算法

由于拉片压铸为生产计划问题，，需要进行生产方案的全局寻优。本文采用多种群遗传算法进行生产计划优化。

3.1问题的编码

本文采用自然数编码的方式，以各子批要生产的产品为对象进行编码，并使用一个n*m矩阵来表示该问题的可行解。现在给出n个子批产品在m台设备上的加工序列矩阵如下：

其中，aij表示将设备j分配给子批i的生产时间。矩阵的第i行向量[ai1，ai2，…，aim]依次表示子批i的产品在各个设备上的生产时间。矩阵的第j列向量表示将设备j分配给各个子批的产品次序和生产时间。在初始化产生的染色体中，将子批i在设备j上的生产时间代入染色体的基因aij中，这样依次代入，则初始化的染色体为[a11，a12，…，a1m，a21，…，aij，…，anm]。通过自左向右遍历染色体所产生的生产结果都是可行的，用这类方法产生的初始解也都为可行解。

3.2适应度函数

通常，取目标函数直接作为适应度函数，在这里取生产完成一批订单的生产周期MSmax=max{MSj|j=1，…，m}的倒数作为适应度函数，由此来计算每个染色体的适应度值。

令MSkmax表示第k个染色体的生产周期，则该染色体的适应度函数即表示为：

3.3遗传操作

针对前述的编码方式，采用如下遗传操作[5]。

3.3.1选择

本文采用精英保留策略和期望值策略结合使用的选择方法。精英保留策略指的是将当前种群中适应度值最高的个体不进行交叉变异而直接复制到下一代种群中。采用精英保留策略能够使进化过程的每一代种群内的最优解不致为交换和变异操作所破坏，从而增加获得局部最优解的概率。

采用精英保留策略和期望值策略结合使用的选择方法是：在种群开始进化时，将种群内的最优解直接复制到下一代种群中，再考虑剩余染色体个体的期望值，通过期望值操作将其他染色体遗传到下一代种群中。期望值操作的步骤是：

（1）按照适应度的值计算期望值fi，计算公式为：

fi=1n∑ni=1fi（3）

（2）计算种群中的每一个体在下一代生存的期望值Ei，计算公式为：

Ei=fifi（4）

（3）将Ei四舍五入取整得Ei，Ei即为选中个体i的个数。

如果Ei=0，则个体i被淘汰。

3.3.2交叉

本文采用的交叉法是在染色体上依据问题性质定位多个分割点，再随机选取两个相邻分割点，定义这两点之间的区域为一匹配区域，并使用位置交换操作交换两个父串的匹配区域 。具体的交叉操作如下：

（1）任意选择两个父代染色体P1和P2。

（2）根据这两个染色体的构成n*m，将这两个染色体按m分割成n+1个分割点。随机选择一个a（a

（3）将L1中的基因依次插入到P2染色体的空位中，将L2中的基因依次插入到P1染色体的空位中，分别生成子代染色体S1和S2，未被选中的基因在子代染色体中的相对位置是保持不变的。

对于4*4（4批次产品，4台设备）的生产计划问题，有p1和p2两个生产计划方案：

上面染色体每一个“.”处为一个分割点，随机选择a=1，则第2个分割点（第4*1+1=5个基因）为起始，第3个分割点（第4*2=8个基因）为结束的基因串就分别是L1=[0 3 2 2]，L2=[5 0 2 2]。将L1放入染色体P2中原来L2在的空位处，将L2放入染色体P1中原来L1在的空位处实现交叉操作，保持其余各基因串顺序不变。得到子代染色体：

3.3.3变异

本文采用的变异操作的具体步骤是：

（1）染色体长度n*m，随机选择一个a（a

（2）以变异概率p使g1的基因值加1，g2的基因值减2。

（3）将g1和g2插回Q中两个基因的原来位置，成为新的染色体R。

（4）先检验第a+1批次产品的生产可行性，即新染色体R的可行性。若可行，再比较新个体与父代个体的适配值。如果新个体适配值较小，则用其取代父代个体；否则，保持父代个体不变。

选择a=1，范围第4*1+1个基因开始，4*2个基因结束，基因串是[0 3 2 2]，随机选择p1的第6个基因和第8个基因为变异基因g2，g1。g1的基本值加1变为3，g2的基因值减2变为1，将g1和g2插回原来的染色体，构成新染色体R为：

3.4利用多种群遗传算法优化生产计划问题

多种群遗传算法的设计思想是存在不同初始值的几个种群，每个种群都有着对应的进化参数，采用不同的选择策略和交叉变异算子使种群发生进化，产生每个种群的局部最优个体，进而得出全局的最优个体[6]。

采用多种群遗传算法求解生产计划模型的具体步骤如下：

（1）初始化种群。使用自然数编码方法，随机产生染色体组成两个种群。

（2）初始化种群进化参数。为每个种群选择交叉概率、变异概率和种群间精英迁移的概率。

（3）为每个种群确定选择操作。对种群1选用的选择操作为精英保留策略和期望值策略结合方法，对种群2选用的选择操作为轮盘赌法。

（4）各个种群按照各自设定的交叉概率和变异概率进行交叉和变异操作。

（5）对产生的新一代种群，各个种群按照设定的迁移概率交换种群间的个体。交换后更新种群，形成下一代种群。

（6）检验是否满足终止条件，如果满足则产生各个种群的局部最优个体，如果不满足则返回（4）继续进化。

（7）对两个种群产生的局部最优个体进行比较，得出全局最优个体，输出全局最优个体。

4仿真实验与分析

例1：在一段时间内，有4个订单计划生产。这4个订单需要的拉片产品及其交货量交货期如表1；生产设备M={1，2，3}，设备的出模次数分别是{80，70，60}，各个设备每天生产8小时。产品i（i=1，2，3，4）的模具安放在设备j（j=1，2，3）上的个数如表2所示，所有产品分批后结果则表3所示。

种群1初始个体数量30，交叉概率0.9；变异概率0.1，迁移概率0.05，最优个体保留个数2；最大遗传代数50；种群2初始个体数量30，交叉概率0.85，变异概率0.15，迁移概率0.05，最优个体保留个数2，最大遗传代数50。

仿真结果分析：算法收敛曲线如图1所示，最优生产计划如表4所示，甘特图如图2所示。比较局部染色体后，得到全局最优染色体[6 0 6 0 16 10 0 14 16 27 4 2 ]。 最小生产周期为34小时。

Tab.4 Production planing子批号设备1（小时）设备2（小时）设备3（小时）子批1606子批201610子批301416子批42742由以上仿真结果可以看出：种群1和种群2都能够保持种群多样性，且都逐步达到最优解，该算法具有良好的收敛性和有效性。文献[7]对模型的优化结果为35小时，而根据本文的优化方法，优化结果为34小时，且有多个排产结果。

5结束语

本文应用多种群遗传算法对拉链生产中的拉片压铸的生产计划优化问题进行了研究。采用表示生产时间的自然数编码，选用适合本问题的选择、交叉和变异操作，以完成生产的最小生产周期为评价指标，并建立完整的生产计划模型的优化算法。仿真结果表明该算法实现了生产计划方案的全局优化。

参考文献：

[1]任瑞荣. 多品种变批量生产质量控制关键技术的研究与应用[D]. 上海：东华大学， 2010.

[2]李宏霞，彭威，史海波.装配车间的多品种变批量的生产调度优化模型[J]. 机械设计与制造， 2006（6）：94-96.

[3]安进. 车间生产批量优化调度研究[D]. 南京：南京航空航天大学，2005.

[4]CAVALICRI S ， GAIARDCLLI P. Hybrid genetic algorithms for a multiple-objective scheduling problem [J] . Journal of Intelligent Manufacturing ，1998 （9） ：361 - 367.

[5]任庆生，叶中，曾进，等. 对常用选择算子的分析[J] . 上海交通大学学报，2000 ，34 （4） ：564 - 566.

[6]蔡良伟，张基宏，李霞. 作业车间调度问题的多种群遗传算法[J]. 电子学报， 2005， 33（ 6） ： 991- 994.

[7]张毕西，谢祥添.非流水型生产调度问题的研究[J].机械制造，2007，45（4）：60-62.

（上接80页）

（2）对硬件配置要求较低，服务器采用的配置相当自由；

（3）系统平滑切换，不会造成使用不便；

（4）系统效率较高。因为数据管理和服务器故障纠错由相对独立的两个子系统联合完成，而双机心跳线使用的又是冗余网络，所以不需消耗CPU和宽带资源。

同时，双机与磁盘互联的缺点为：

（1）单点错。即使系统中某一个节点出错，也会导致系统全部宕机；

（2）当磁盘阵列出现逻辑故障或物理故障时，还会导致储存数据全部丢失。

5结束语

在全球信息高速路建设渐趋完成的今天，大到高新科技前沿技术，小到平民百姓日常生活，信息服务无处不在，而保护这些信息甚至已成为维护社会稳定的必要手段。双机热备份技术的出现解决了这一问题，在保护重要数据的同时，又不致影响到用户正常使用。在网络技术的激烈竞争中，人力组配是很宝贵的重要资源，双机热备份即节省了人力资源，因而具有重要的实用推广价值。

参考文献：

[1]施维力.浅谈服务器的双机热备份技术[J].广播电视信息，2009（12）： 60-61.

[2]王崇霞.数据库双机热备份系统解决方案[J]. 微机发展，2003（S2）：79-80，85.

[3]史文路.双机热备份系统的研究与设计[D].南京：南京工业大学，2006.

[4] ALLCOCK B，FOREST I， NEFEDOVA V. High-Performance remote access to climate simulation data：A challenge Problem for data grid technologies[A].The conf of High-Performance Networking and Computing，Denver SC2001[C].USA：[s.n.]，2001：283-297.

[5]李利军.星载双机热备份计算机系统设计[D]. 西安：西安电子科技大学，2010.

[6]曹阳.RAID技术实现及发展[J].电脑学习，2006（4）：43-44，60.

[7]徐敏，陆达，赵洪志，等.廉价冗余盘阵列（RAID）发展综述[J]. 计算机工程与应用，1999（6）：27-29.