随机型混流装配线动态排序问题研究

第ｌｌ期　２０１３年ｌ１月　组合机床与自动化加工技术　

Ｍｏｄｕｌａｒ　Ｍａｃｈｉｎｅ　Ｔｏｏｌ＆Ａｕｔｏｍａｔｉｃ　Ｍａｎｕｆａｃｔｕｒｉｎｇ　Ｔｅｃｈｎｉｑｕｅ　Ｎ０．１１　ＮＯＶ．２０１３　

文章编号：１００１—２２６５（２０１３）ｌ１—０１ｌ４一Ｏ５　随机型混流装配线动态排序问题研究　

朱华炳　，王　龙　，涂学明　，余　锋　（１．合肥工业大学机械与汽车工程学院，合肥２３０００９；２．江铃汽车股份有限公司，南昌　３３００００）　

摘要：通过对传统的装配线产品排序方法进行研究，提出了一种基于粒子群算法与仿真分析相整合　的方法。以装配线上各种零部件消耗速率均衡化和最小生产循环周期最短为优化目标，建立随机型　装配线产品动态排序问题的仿真模型。最后以某车桥企业装配线产品排序问题为例进行了验证，证　明了该方法同时具备智能群算法高效搜索能力与便于建立动态仿真模型的优点。该方法可以快速　获得排序问题最优解，大大减少设计者的工作量，具有很强的实用性，为解决多目标优化的产品排序　问题提供了一种新途径。　关键词：随机型装配线；产品排序；粒子群算法　中图分类号：ＴＨ１６；ＴＧ６５　文献标识码：Ａ　

Ｒｅｓｅａｒｃｈ　ｏｎ　Ｄｙｎａｍｉｃ　Ｓｅｑｕｅｎｃｉｎｇ　Ｐｒｏｂｌｅｍ　ｏｆ　Ｓｔｏｃｈａｓｔｉｃ　Ｍｉｘｅｄ－ｍｏｄｅｌ　Ａｓｓｅｍｂｌｙ　Ｌｉｎｅ　ＺＨＵ　Ｈｕａ—ｂｉｎｇ　，ＷＡＮＧ　Ｌｏｎｇ　，ＴＵ　Ｘｕｅ－ｍｉｎｇ　，Ｙｕ　Ｆｅｎｇ　（１．Ｓｃｈｏｏｌ　ｏｆ　Ｍｅｃｈａｎｉｃａｌ　ａｎｄ　Ａｕｔｏｍｏｔｉｖｅ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｈｅｆｅｉ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈｅｆｅｉ　２３０００９，　Ｃｈｉｎａ；２．Ｊｉａｎｇｌｉｎｇ　Ｍｏｔｏｒｓ　Ｃｏｒｐｏｒａｔｉｏｎ，Ｎａｎｃｈａｎｇ　３３００００，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｂｙ　ｓｔｕｄｙｉｎｇ　ｐｒｏｄｕｃｔ　ｓｅｑｕｅｎｃｉｎｇ　ｍｅｔｈｏｄｓ　ｏｆ　ｔｒａｄｉｔｉｏｎａｌ　ａｓｓｅｍｂｌｙ　ｌｉｎｅ，ａ　ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　ｐａｒｔｉ—　ｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｃｏｍｂｉｎｅｄ　ｗｉｔｈ　ｓｉｍｕｌａｔｉｏｎ　ａｎａｌｙｓｉｓ　ｈａｓ　ｂｅｅｎ　ｐｕｔ　ｆｏｒｗａｒｄ，ａｎｄ　ａ　ｓｔｏｃｈａｓ—　ｔｉｃ　ａｓｓｅｍｂｌｙ　ｌｉｎｅ　ｓｉｍｕｌａｔｉｏｎ　ｍｏｄｅｌ　ｗａｓ　ｅｓｔａｂｌｉｓｈｅｄ，ｏｐｔｉｍｉｚａｔｉｏｎ　ｇｏａｌｓ　ａｎｄ　ａｌｇｏｒｉｔｈｍｓ　ｗａｓ　ｇｉｖｅｎ，Ｆｉｎａｌｌｙ　ｔｈｅ　ｒｅａｒ　ａｘｌｅ　ａｓｓｅｍｂｌｙ　ｌｉｎｅ　ｓｅｑｕｅｎｃｉｎｇ　ｐｒｏｂｌｅｍｓ　ｏｆ　ａ　ｅｎｔｅｒｐｒｉｓｅ　ｗａｓ　ｔａｋｅｎ　ｆｏｒ　ｅｘａｍｐｌｅ　ｔｏ　ｖａｌｉｄａｔｅ　ｔｈｅ　ｍｅｔｈｏｄ　ｗｈｉｃｈ　ｈａｖｅ　ａｄｖａｎｔａｇｅｓ　ｏｆ　ｅｆｆｉｃｉｅｎｔ　ｓｅａｒｃｈ　ｃａｐａｂｉｌｉｔｉｅｓ　ｏｆ　ｉｎｔｅｌｌｉｇｅｎｔ　ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　ｂｕｉｌｄｉｎｇ　ａ　ｄｙ—　ｎａｍｉｃ　ｓｉｍｕｌａｔｉｏｎ　ｍｏｄｅｌ　ｅａｓｉｌｙ，ＳＯ　ｔｈａｔ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ　ｏｆ　ｓｅｑｕｅｎｃｉｎｇ　ｃａｎ　ｂｅ　ｇａｉｎｅｄ　ｑｕｉｃｋｌｙ，ａｎｄ　ｒｅｄｕｃ—　ｉｎｇ　ｔｈｅ　ｗｏｒｋ　ｏｆ　ｄｅｓｉｇｎｅｒｓ，Ｔｈｅ　ｍｅｔｈｏｄ　ｈａｓ　ａ　ｓｔｒｏｎｇ　ｐｒａｃｔｉｃａｌ　ａｐｐｌｉｃａｔｉｏｎ，ａｎｄ　ｐｒｏｖｉｄｅ　ａ　ｎｅｗ　ａｐｐｒｏａｃｈ　ｔｏ　ｒｅｓｏｌｖｅ　ｐｒｏｄｕｃｔ　ｓｅｑｕｅｎｃｉｎｇ　ｗｉｔｈ　ｍｕｌｔｉｐｌｅ　ｏｂｊｅｃｔｉｖｅｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｓｔｏｃｈａｓｔｉｃ　ａｓｓｅｍｂｌｙ　ｌｉｎｅ；ｐｒｏｄｕｃｔ　ｓｅｑｕｅｎｃｉｎｇ；ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　

Ｏ　引言　随机型混流装配线是一种柔性装配线，在同一　条装配线可混合连续装配几种结构相似且工艺接近　的不同品种的产品，特点是装配线上的各道工序的　作业时间为随机变量。混流装配线的引人可大大减　少装配线上生产能力的浪费和在制品的占用量…，　是实现“一个流”生产模式的有效手段。　目前，混流装配线排序问题的研究主要集中于　确定型装配线，即各道工序的作业时间为一个确定　的数值，国内外许多学者对该类型排序问题进行了　大量的研究　，并取得了不少理论成果。然而在实　际生产系统中，许多装配线仍然以人工为主，甚至完　全依靠人工完成，因此，装配线上的作业时间必然会　受到工人的疲劳程度、技术熟练度和环境的照明度　等因素的影响，在这种情况下，各作业元素的加工时　间往往是波动的，即为随机变量，因此只能用一个随　

机分布的函数来描述。因此，对随机型混流装配线　排序问题的研究更具现实意义。　苏平，于兆勤等以各种零部件消耗速率均匀和　最小生产循环周期最短为优化目标，并采用混合遗　传算法进行求解　；刘文平建立了零部件消耗速度　最小化模型、生产准备总调整时间最小化模型和因　超载所需要线外加工任务总数最小化的模型，采用　归一权重系数的方法将３个模型进行整合，最后采　用Ｍｅｍｅｔｉｃ启发式算法进行了求解　。方波采用改　进的差分进化算法对混合装配线排序问题进行研　究　；王进建立了一个汽车企业产品投放顺序的数　学模型，并采用目标追踪法和Ｌｉｎｇｏ软件数学规划方　法进行了研究，最终得到满意的排序方案　。显然，　文献［７—９］都是针对确定型装配线排序问题进行研　究的，所提出的方法都具有一定的缺陷，难以将装配　线上各工序作业时间的随机特点表达出来，而且不　

收稿日期：２０１３—０３—２２；修回日期：２０１３—０４一ｌ４　作者简介：朱华炳（１９６３一），男，安徽怀宁人，合肥丁业大学机械与汽车Ｔ程学院教授，博士，主要研究方向为机电一体化装备设计与制造　制造系统工程理论及应用技术等，（Ｅ—ｍａｉｌ）２８９４７８７２７＠ｑｑ．ｃｏｒｎ。　２０１３年１１月　朱华炳，等：随机型混流装配线动态排序问题研究　・１　１５・　易构建其数学模型。　针对随机型混流装配线的特点，王哲建立了通　过Ｆｌｅｘｉｍ仿真软件建立了装配线的动态模型进行求　解　。该方法的缺点是：在排序问题求解过程中，需　要将各种排序备选方案手动输入Ｅｘｃｅｌ表格中，然后　将其导人仿真软件中，选出最佳方案，整个求解过程　比较繁琐，而且随着ＭＰＳ中产品数量的增加，产品的　排序方案数将成指数倍增长，这会给Ｅｘｃｅｌ输入带来　极大工作量，因此该方法不适用于大规模的装配线　产品排序问题的求解。　针对以往随机型混流装配线排序问题研究方法　的缺陷，本文提出基于粒子群算法和仿真分析的混　合方法。　１　随机型混流装配线排序问题　１．１问题描述　随机型混流装配线排序问题描述如下：在计划　期内，装配线上可同时生产　种结构相似的不同系　列产品，产品总需求量为Ｄ，每种系列产品的需求量　分别Ｄ　（ｍ＝１，２，３，…，　），　，Ｄ　，・・・　之间关系　如公式（１）所示。　Ｄ＝∑Ｄ　（１）　混流装配线产品排序问题一般采用最小生产循　环排序方法。设＾为市场需求量Ｄ　的公约数，那么ｄ，　ｄ　和Ｄ　关系如公式（２）和公式（３）所示。　Ｄ　ｄｍ＝　ｈ　（２）　Ｍ　ｄ＝∑ｄ　（３）　ｍ　１　一般把｛ｄ　，ｄ：，ｄ，…ｄ　｝称为一个最小生产循　环。理论上，只需要对最小生产循环中的ｄ个产品进　行排序，然后重复排序循环ｈ次即可。　１．２　多目标优化评价指标的选择　实际的工程优化问题绝大多数都需要考虑多个　不同的优化目标。多品种随机型装配线可以根据企　业的实际要求而采用不同的目标函数作为评价指　标。本文通过分析调研，确定了问题的优化目标即：　产品总完工时问最短和零部件消耗速率均衡化，以　实现物流合理化、生产均衡化的目标。　（１）零部件消耗速率　零部件消耗速率进行均衡优化，是在生产的各　个阶段，各种零部件的实际消耗与理论消耗尽可能　一致，保证各零部件的子装配线能够均衡，从而使生　产过程中在制品的库存量达到最小。为了便于描述　零部件消耗速率目标，定义以下符号：　①　：产品种类数；　②ｄ：一个ＭＰＳ内的产品需求量；　③ｄ　：一个ＭＰＳ内的第ｍ种产品的需求量（ｍ＝　１，２，３，…，Ｍ）；　④ｃ：第Ｃ生产阶段，即完成一个ＭＰＳ生产循环中　前ｃ个产品的时刻（Ｃ＝１，２，３，…，ｄ）；　⑤ｒｍ：第ｍ种产品的理想产量比率（ｍ＝１，２，３，　

…，　

）；计算方法如公式４所示。　

ｒ　：　：＃　（ｒ　了　■广　４）　ｙ　ｄ　』＿…　…　

￣ｘｃ，ｍ：判断第个位置是否为产品ｍ，如果是则　

ｃ，ｍ＝１，否则ＮＣ，ｍ＝０　ｏ　⑦ｇｍ，ｃ：截止到第ｃ个生产阶段时第ｍ种产品的　实际产量。　零部件消耗速率表达式如公式５所示。　

＝∑∑Ｉ　ｇ　，　一ｃ×ｒ　Ｉ　（５）　（２）产品总完工时间　产品的总完工时间最短，有利于缩短生产循环　周期，提高企业的生产效率，一个ＭＰＳ内，产品的总　完工时间计算方法如公式（６）所示。　Ｍ　Ｎ　＝∑∑（ｕ　＋“　）　（６）　

ｍ＝ｌ　１　其中：Ｕｍｎ一产品ｍ的第ｎ个作业元素的作业时间；　

ｕ　一产品ｍ的第ｎ个作业元素的等待时间。　２　粒子群算法和计算机仿真　

２．１　改进粒子群算法　２．１．１　算法流程设计　基本粒子群算法主要针对函数优化问题进行求　解，而对于组合优化问题的应用还是比较少…　。为　了解决装配线平衡这类典型的离散组合优化问题，　需要对粒子群算法进行改进。本文借鉴遗传算法中　染色体交叉和变异等思想¨　，对基本粒子群算法进　行了改进设计。改进后粒子群优化算法的具体执行　步骤如下：　Ｓｔｅｐｌ：种群初始化：设定种群规模ｐｏｐ—ｓｉｚｅ，迭代　次数ＮＣ，变异概率Ｐ　，随机产生ｐｏｐ—ｓｉｚｅ个初始解　；　Ｓｔｅｐ２：计算各个个体当前位置的适应度ｆｉｔｎｅｓｓ，　设定当前适应度为个体极值，当前位置为各个个体的　个体极值位置，然后确定全局极值和全局极值位置；　Ｓｔｅｐ３：从三种交叉和变异算子中随机选择一种　交叉和变异操作；　Ｓｔｅｐ４：将每个个体与其个体极值位置ｐｘｂｅｓｔ进　行交叉，得到　．；　Ｓｔｅｐ５：将　，与当前种群全局极值位置ｇｘｂｅｓｔ进　行交叉，得到　，；　Ｓｔｅｐ６：计算各个个体的适应度，如果存在当前位　置优于个体极值位置的个体，则用当前个体位置替　换个体极值位置，反之，个体极值位置保持不变；　Ｓｔｅｐ７：从个体极值位置中选出全局极值位置　ｇｘｂｅｓｔ；　Ｓｔｅｐ８：按照概率Ｐ　对各粒子的个体极值位置　ｐｘｂｅｓｔ进行变异得到　，如果　优于当前个体极值位　置，则接受变异操作，反之则拒绝；　Ｓｔｅｐ９：判断是否达到终止条件，如果达到了，则