基于Memetic算法的混流装配线排序问题研究

本资料包含pdf文件1个，下载需要1积分

M emetic Algorithm for Sequencing Problems in M ixed M odel Assembly LinesLI Honghua，LAN Xiuju，CHEN Chengpin(College of Mechanical Engineering，Zhejiang University of Technology，Hangzhou 310014，China)Abstract：Mixed assembly production is one of the effective strategies to achieve multi-species，smal-batch and JITproduction.To realize efective operation of mixed assembly line，according to the actual needs of enterprises，forsequencing problems in mixed-model assembly lines，two objectives were considered simultaneously to keep averageconsumption rate of all pans in the assembly line and to minimize the makespan. The mathematical models werepresented.Memetic algorithm was proposed to solve the mode1. In this algorithm，the genetic algorithm as a globalsearch strategy expanded the search space of solution. Introducing tabu search strategy enhanced the neighborhoodexploring ability of the algorithm.Through a mixed sequencing instance，comparison results show that memetic algorithmproposed in this chapter is an eficient method for sequencing problems in mixed-model assembly lines。

Key words：mixed assembly sequencing problem；memetic algorithm；genetic algorithm；tabu search随着市撤境的变化，消费者对产品的个性化、多样性以及交货期要求越来越严格，传统的小品种、大规模生产方式已很难适应市场的需求，因此，基于订单生产的多品种，小批量生产方式已逐渐成为装配型企业的首眩多品种混流装配生产作为 JIT生产方式的具体应用之-，是-种柔性很强的生产系统，可以按照客户个性化需求在最短时间内最大限度地生产出其所需产品，以提高企业对市场需求变化的快速反应能力。目前，混流装配生产方式已在汽车、家电等行业得到广泛应用。

混流装配线(Mixed-Model Asembly Line)是指在- 段时间内，有多种结构相近、工艺类似的产品同时在装配线上进行装配加工 J。由于工艺与结构的差异造成的单元作业和作业时间差别，因此，混流装配生产必须合理地组织产品投产顺序以及数量，消除装配线上工作站的物流瓶颈”，实现总装配线以及分装线上的均衡生产、物流速率平稳。针对混流装配线排序问题，学者们研究了多种不同的目标函数 3 J，如零部件消耗速率均匀化、最携工作站超载与闲置时间、最小化总切换时间、最小生产循环周期最短等。但 目前针对混流装配线排序优化问题的研究很少涉及到加工周期问题，然而在市澈争环境越来越激烈的今天，更短的交货期对提高企业竞争力非常重要。因此，通过合理安排投产顺序，缩短加工周期也是-个重要的优化收稿 日期 ：2012-09-10；修回日期：2012-09-28基金项目：浙江省 自然科学基金资助项 目(Y1111118)作者简介：李洪华(1987)，男，广西桂林人，硕士研究生 ，主要研究方向为生产调度 、制造业信息化。E-mail：lhh168.hi###t63.com[经营·警理] 李洪华，等：基于Memetic算法的混流装配线排序问题研究 ·97·目标 。

混流装配线排序问题属于-类 NP难组合优化问题。目前，针对排序问题的优化求解方法主要有：目标追踪法(Goal Chasing，GC)，智能算法(如遗传算法、PSO算法等)。文化基因算法 (Memetic Algorithm，MA)是 1989年由Pablo Moscato在模拟文化进化基础上建立起来的-种新型优化算法，其基于种群的全局搜索和基于个体的局部启发式搜索的结合机制使其搜索效率在某些问题领域比传统智能优化算法(如 GA，PSO等)快几个数量级。R.Tavakkoli-Moghaddam1 ，刘文平 针对混流装配线多目标排序优化问题，设计了Memetic算法进行求解，对比验证了 Memetic算法在求解 性能上 的优越性。魏臻 等 提 出了-种Memetic框架下的混合粒子群优化算法(HM.PSO)，实验结果表 明该算法具有 良好 的寻优性 能∩见，Memetic算法作为-种新兴的优化算法，在求解组合优化问题上具有良好的性能，但目前在混流装配线排序问题上的研究较少，具有很大的研究空间。

文章针对混流装配线排序问题，建立了以装配线上各零部件消耗速率均匀化与最大加工周期最短为目标的多目标优化模型，并设计了 Memetic算法进行求解。该算法将遗传算法(GA)与禁忌搜索算法(TS)结合起来，保持了 GA的智能性与并行性，扩大了解的搜索空间，具有优秀的全局搜索性能；引入禁忌搜索算法，提高了算法的邻域探索能力，优化了种群分布，及早剔除不良个体，从而减少了迭代次数，提高了算法的优化性能；最后通过混流装配线排序案例，验证了多 目标模型及所设计 Memetic算法的有效性。

1 问题描述与数学模型1.1 问题描述混流装配线问题描述如下：装配线上有 种产品同时进行混流加工装配，在-个生产计划期内，第 种产品的需求量为 D (i1，2，3，， )，总需求量 D：盯D 。最小生产循环(Minimal Production Set，MPS)是指各种所需装配的产品按照-定的比例所形成的最小生产序列。令 r为各产品的需求量 D 的最大公约数，则在-个最小生产循环(MPS)内，每种产品的装配数M量d D /r，所含产品总的数量为d∑d ，只需对d 1单位的产品进行投产排序，重复 r遍即可完成产品的装配生产需求。因此，混流装配线排序优化问题可简化为对最小生产循环(MPS)序列的排序优化问题，其计算复杂度大为缩校混流装配线排序问题可以根据企业的需求采用不同的目标函数，在实际的应用中，往往同时考虑几个 目标函数。文中根据在某电机装配企业的调研情况，引入了两个优化目标：①零部件消耗速率均匀化；②最大加工周期最短。

1.2 各种零部件的消耗速率均匀化零部件消耗速率均匀化是指混流装配线上各零部件的实际消耗速率旧能与该零部件的理论消耗速率- 致，以使得上游零部件加工线能够平稳、均衡地进行生产，进而保证整个混流装配生产系统的稳定性，并减少在制品库存量。在-个最小生产循环内，零部件消耗速率均匀化的目标函数为d r Mmin∑∑(∑Yi ×b -k× /d) (1)约束条件i∈[1，M]，.j∈[1，d]， ∈[1，T] (2)M∑8 1 (3)0 ld. ∑6 d (4)k1d ∑8 (5) lM ∑d ×b (6)式中：k为投产排序序号； 为产品型号； 为零部件种类；6 为0～1变量，如果第k个位置上是型号为 的产品，则 8 1，否则为 0。目标函数 (1)中第 1项M∑Yi ×b 为-个最小生产循环序列中，装配前 个产品实际消耗零部件 的数量， 表示生产序列前k个产品中型号为i的产品数量～b为装配-件型号为 的产品所需零部件 的数量；目标函数(1)中第 2项 k X/d为理论消耗数量，其中 为装配完最小生产序列中的产品所需部件 的总数量。式(3)确保任-工位同- 时间只有-个产品在该工位装配。式(4)为-个最小生产循环内第 种产品的装配数量为 d 。

1.3 最大jD'r周期最短加工周期是指在最小循环序列(MPS)中，装配线上第 1个产品开始加工到最后-个产品加工完成所用的总时间。最大加工周期最短是生产负荷均衡类 目标的重要衡量指标之-，其目标函数为：min[max(E )] (7)约束条件 k∈[1，d]， ∈[1，N] (8)· 98· 轻工机械 Light Industry Machinery 2013年第2期Sl 0 (9)Sl S -I)P1 1] (1O)EhS Ph，k∈[2，d] (11)Sh E(- I]， max(E( -1) ，E ( -1))，k∈[2，d](12)式中： 为序列中第 k个产品在工作站 n上的开始装配时间；Ph为序列中第 k个产品在工作站 上的所需加工时间；Eh为序列中第 k个产品在工作站 n上的装配结束时间；E 为最后-个产品在最后-个工作站的完工时间。

如前所述，针对两个 目标函数进行了研究，属于多目标优化问题。常规多 目标求解方法有：多 目标加权法、 .约束法、Pareto解集等。加权法具有简单易行、求解速度快等优点，得到了广泛应用。为求解混流装配线多目标排序模型，采用多目标加权系数法。W 与 W 分别代表子目标 与 之间的相对权重，则两个 目标通过线性加权可表示为fWL厂 W (13)2 Memetic算法设计2.1 Memetic算法总体设计Memetic算法采用基于种群的全局搜索与基于个体的局部搜索策略组成。在宏观层面，采用遗传算法(GA)作为种群的全局搜索策略，GA并行搜索能力强，可以扩大解的搜索空间，具有优秀的全局搜索性能，但其局部搜索能力较差，容易导致早熟”现象。

因为 GA的变异概率-般较小，引入新染色体的机会少，但如果概率取得太大，变异算子将导致算法的随机性很大，搜索过于盲目 ；在微观层面，采用禁忌搜索(TS)作为局部搜索策略，把 Ts作为 GA的变异算子。

Ts通过引入-种灵活的存储结构与相应的禁忌准则来避免迂回搜索，可看作个体从邻域内学习的过程，这饮合文化基因发生变异时需要有大量专业知识支撑的特征，同时，引入藐视准则来赦免-些被禁忌的优良状态，并有-定的概率接受劣解 ，从而保证搜索过程的有效性与多样性。文中所设计的Memetic算法总体流程如图1所示。

2.2 Memetic算法求解步骤从图 1中可以看出，Memetic算法的主要求解步骤如下：Step 1 采用随机方法生成初始种群e(0)；Step 2 评价种群 P(/7，)中每个个体的适应度值；Step 3 判断终止条件是否满足，若满足则输出优化结果，算法终止；否则执行以下操作；图 1 Memetic算法总体流程Figure 1 Flow chart of Memetic algorithmStep 4 根据适应度值大小，采用轮盘赌方式对个体进行亲本选配，产生新-代种群；Step 5 依据交叉概率 P 执行交叉操作，采用改进的顺序交叉算子(order crossover) 14]对选择的两条父本个体进行交叉操作，生成新-代染色体；Step 6 依据概率 P 选择是否进行局部搜索；Step 7 tt1，返 回 Step 2。

2.3 局部搜索策略局部搜索策略是决定 Memetic算法搜索性能关键因素之-，禁忌搜索具有记忆功能与爬山能力强的特点，克服了遗传算法爬山能力弱的缺陷，故选塞忌搜索作为 Memetic算法的邻域搜索策略←忌搜索算法邻域探索关键步骤如下：1)邻域结构。文章将遗传算法进化得到的优化结果作为禁忌搜索的初始解，进而生成邻域解，并确定候砚。邻域解的产生方法是邻域搜索的核心部分，移位变异策略(shift)是目前效果较好的邻域生产方法之-。

2)禁忌表与长度←忌表是针对禁忌对象所设计的-种结构，对已经进行的优化过程进行记忆”，以指导下-步的搜索方向；禁忌长度是指每个禁忌对[经营.蕾理] 李洪华，等：基于Memetic算法的混流装配线排序问题研究 ·99·象在禁忌表中不能被选取的最大次数，其决定了算法的计算复杂度←忌长度-般取为 ，n为问题的维数。

3)藐视准则。采用基于适应度值的藐视准则，若某个禁忌候砚的适应度值优于当前最优解，则无视其禁忌属性，仍将此候砚作为新的当前解与当前最优解。

3 实例研究某电机装配企业总装线 采用混流方式进行生产，该装配线共 8个工作站，混合装配 4种产品，计划日产量分别是A为120台，B为80台，c为8O台，D为160台。最小生产循环为 3A，2B，2C，4D，共 11个产品。根据混流装配线排序问题的特点，采用基于加工序列的数字串编码方式。在-个最小生产循环内，代表 投 产 顺 序 DDAABCBCDAD 的 基 因 串 为(44112323414)，产品按编码依次装配。各产品对应工作站作业时间如表 1所示，其中 ～ 分别表示工作站 1～8。各产品装配所需零部件如表 2所示，其中l，。～I， 。分别表示零部件 1-10。

表 1 各工作站加工时间Table 1 Operation time of each workstation为验证所提出的 Memetic算法的有效性，对该案例分别采用Memetic算法与GA进行优化。两个目标函数的权重分别设为 。0.4与 加：0.6。Memetic算法参数：种群规模为 100，迭代次数为 100，交叉概率为0.8，个体参与禁忌搜索的概率为 0.2，禁忌搜索代数为30，候砚集 C30，禁忌表长度为 10；GA参数设置：种群规模为100，迭代次数为100，交叉概率为0.8，变异概率为0.1～两种算法分别对实例进行20次求解，优化结果如表3所示∩见，Memetic算法在收敛速率以及寻优性能方面均优于 GA，是求解混流装配线排序问题的有效方法。Memetic算法最优解的搜索过程如图2所示，最优解fmi 1 190(其中 73.86 1 934)，所对应的基因串为(14412432341)，解码得到产品的投产顺序为AD 肋 C ∞A，对序列重复40次投产即可完成装配任务。

表 3 案例优化对比Table 3 Case optimize contrast图2 Memetic算法最优解搜索过程Figure 2 Optimal solution searchprocess of Memetic algorithm4 结语混流装配线排序问题是混流装配生产系统能否有效运作的关键问题之-，为实现各种零部件的均衡生产以及缩短加工周期，文中从装配线上各零部件消耗速率均匀化以及最大加工周期最短两方面，对混流装配线排序问题进行了研究，并建立了数学模型，分别采用 Memetic算法、GA对多目标优化问题进行了求解，最后通过应用实例，验证了文章所设计算法在求解混流装配线多目标排序优化问题方面的有效性。该算法在参数设置方面仍有不足，今后将进-步研究算法参数的自适应调整方面，以实现参数的最优设置。