热门关键词:

基于禁忌粒子群算法的混流装配线排序研究

  • 该文件为pdf格式
  • 文件大小:379.43KB
  • 浏览次数
  • 发布时间:2014-11-10
文件介绍:

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

混流装配线可以在基本不改变生产组织方式的前提下,同时生产出多种不同型号、不同数量的产品,它是应对大规模定制生产的-种有效组织方式n 。目前 ,我国家电、汽车生产行业大量采用了混流装配方式 ,装配线上合理的投产顺序能有效提高装配线的生产效率、降低生产周期和充分利用生产资源,因此解决混流装配线的排序问题是混流装配线能否高效运作的关键。

在求解混流装配线的排序问题上,通过智能算法求解是 目前的研究重点。目前,常用的智能算法有遗传算法、粒子群算法(PSO)、蚁群算法等。郑永前、王永生等 通过免疫粒子群算法求解最携超载时间与空闲时间的费用的混流装配线排序模型,但算法结果- 般,且没有考虑其他影响装配线效率的因素;刘炜收稿 日期:2012-127基金项目:国家 自然科学基金资助项目(70971118);浙江省自然科学基金资助项 目(LY12E05021);浙江侍育厅科研资助项目(Y201121984)作者简介:翁耀炜(1988-),男,浙江温州人,主要从事精益生产、生产调度方面的研究.E-mail:wengyaowei###126.com通信联系人:鲁建厦,男,教授,硕士生导师.E-mail:ljs###zjut.edu.cn第4期 翁耀炜,等 :基于禁忌粒子群算法的混流装配线排序研究 ·431 ·琪、刘琼等b 通过混合粒子群算法求解以最携超载时间、最携调整时间、最携产品变化率为优化目标的混流装配线排序模型,取得-定的效果,但忽略了所优化的多目标间的冲突和竞争;王炳刚、饶运清等 和苏平、于兆勤b 通过混合遗传算法对零部件消耗均匀和最短生产循环周期对混流装配线排序问题进行优化;董巧英、阚树林等 通过改进离散微粒群算法对最小超载、空闲和调整时间的费用最低的混流装配线排序问题进行优化;薛琴微、兰秀菊等 通过小生境蚁群算法求解以传送带中断时间最短为目标的混流装配线优化模型。

与其他算法相比,粒子群算法在求解过程中,微粒只需要在解空间内追随最优的微柳行搜索,并用公式来更新 自己的速度及位置,不需要进行交叉和变异等操作,具有原理简单、计算方便、全局搜索能力强等优点。在连续空间的实值型处理上已经表现出优良的性能,但其不能直接进行离散空间问题的求解,且 容易陷入局部最优点 ,禁 忌搜索算法 (TS,TabuSearch或Taboo Search) 具有很强的局部搜索能力 ,可以有效避免陷人局部最优。

因此,本研究通过建立基于PSO算法和禁忌搜索算法的模型求解混流装配线排序问题。

1 混流装配线排序数学模型建立1.1 混流装配线排序问题描述由于混流装配线的类型各不相同,目前学术界主要研究的是由传送带(链 )连接的封闭作业域混流装配线。在这类装配线中,当某工作站未能完成产品的加工时,往往假设 由线外的员工及时完成 ,但在实际生产中往往不能达到这个要求,而且-般家电、汽车的总装配线通常采用开放式的作业域。因此 ,为更加贴近实际生产要求,本研究对开发式作业域的混流装配线排序问题进行了研究。

开放式作业域的混流装配线排序模型可以描述为:混流装配线由传送带(链)连接Ⅳ个工位,传送带(链)以恒定速率 移动,每个装配工位长度为 ,工位是开放的,装配线上的工人在装配时需要随着装配输送链的移动而移动,当工人不能在自身的工位内完成加工时,可以在不影响其他工位加工的情况下进入下游加工,同时也可以进入上游工位进行加工。假设:①工件的投产间隔时间固定,以间隔时间A进行投产;②忽略工人的行走时间;③两个工位之间没有缓冲区。

有M种产品需要在装配线上装配,每个品种的需求量为D ,D ,D -, ,则总需求量为D D 。排序采用最小生产循环(MPS,Minimum Part Set)模式,即整个生产顺序由若干个MPS构成,MPS由各产品需求量比例形成最小生产序列,如每种产品的需求量为d (m1,2,3,, ),h为d 的最大公约数,则每种产品在最小生产循环中的数量为 d /h,那么这个MPS可以表示为 d /h,d:/h,d Ih。因此,只要对这个MPS进行排序,将最后排序的结果循环进行h次,就可以得到整个装配产品的投产顺序。

1.2 混流装配线优化目标描述针对排序问题采用不同的优化 目标,排序结果会有很大差异。为提高装配线上工人和设备的利用率并缩短总装配时间,本研究选择以最携超载时间和平顺化零部件消耗为优化目标。

1.2.1 最携超载时间在混流装配过程中,当工人在规定工位区域内没能完成装配任务,则剩余装配任务的标准工时为超载时间。Sarker等 考虑了不完全开放式作业域的混流装配线模型,在此基础上扩展了其模型,建立了开放式作业域的混流装配线 ,该 目标模型表示为: Min∑Y (1)s.t. ∑ 1(v力 (2)∑X阿d (V (3)M ,∑M 槭- )(4)U1JMax(O,∑ t。, - -z )/ ) (5)Z Max l/c∑Xm川 -A , ∑ -。

i≠ 1(6)zu ·nax(O,Zx -。t -A(z。√-。-zl。)/ )(7)zo0,L ≥0,Z ≥0,d ≥0, ∈(0,1) (8)式中:.,--个MPS的投产序列 , -序列中的某-顺序的产品, -投产序列中第 个产品在工位 i上的超载时间,z -投产序列中第 个产品在工位i上的起始装配位置, -工位 i的起始装配位置, -工位的长度, -传送带(链)的传送速度,A-装配线上产品的投产间隔时间,∑X t i-序列中第J个产品在第i个工位上的加工时间,∑ -序列中第机 电 工 程 第30卷个产品所属的产品类型。

由于第-个工位属于封闭式的作业域,研究者需要另外计算,计算公式为式(5,7)。

1.2.2 平顺化零部件消耗混流装配线上不同的产品需要的零部件不尽相同,因此平顺化零部件消耗是指将装配线上的不同产品所需零部件的消耗处于-个平稳的状态。

i K M ∑∑2x .- )J1 1a m1s.t. 2x 1(V (9),∑X d (V m)1式中: ~平顺化零部件消耗; :-在-个MPS中,装配前 个产品消耗第 k种零部件数量的期望值,; XR /.,;R -在-个MPS中装配所有产品消耗的第 k种零部件的数量; -在-个MPS中,装配前个产品实际消耗 的第 k种零部件数量 ,戈 ∑ F ;Fm,k-实际装配第m种产品时所消耗的第m 1k种零部件的数量。

优化模型中采用了最携超载时间与平顺化零部件消耗两个 目标,是多目标优化问题。为求解多目标优化问题,本研究采用加权系数法。尽管该方法有其固有缺点,但考虑到它具有简单易行和求解速度快等特点,并且生产中需要的是可以接受的近优解 ,仍在实际运用中得到了大量的应用。因此,优化目标表示为:F 。 2A (10)式中: , :-超载时间 和平顺化零部件消耗在多 目标优化问题中的重要程度的权重系数。

2 模型求解算法设计2.1 标准PSO模型粒子群优化算法是-种进化计算技术算法 ,由Eberhart和Kennedy提出。在该算法中,种群中的每-个体被称为微粒,微粒在搜索空间中以-定的速度飞行,并根据它本身的飞行经历以及同伴的飞行经历进行动态调整。在每-次的迭代中,微粒通过跟踪两个最优解来更新 自己,第-个是 自身所找到的最优解,即个体极值 P ,记为 P (pu P:O), P ),式中:i-粒子数,d-问题维数;另-个是整个种群所找到的最优解 g ,记为P ,微粒的更新速度和位置为:vij(t1)Wld ( c JrJD - (明c2r2 - 。( (11)2;ij(t1) )vid(t1) (12)式中:c ,c -学习因子;r。,r -(O,1)之间的随机数;i-粒子数;J-问题某-维数;W-喷性权因子。

图 1 标准粒子群算 法流程在算法的初期 ,由于个体最优值 P 和全局最优值 g 在不断变化 ,算法全局搜索能力强。但是在算法的中后期,由于 P 和 g 变化不大,同时由于微粒具有趋同性”,微粒速度将越来越小,最终使得大部分微粒速度接近或等于0,微粒位置得不到更新,有可能使算法陷入局部最优←忌搜索算法是-种全局性的邻域搜索算法。Ts在进行搜索时,它模拟人类大脑具有记忆功能的特点 ,对某些状态进行记忆,同时采用相对应的禁忌规则,使算法能够有效地避免循环搜索,提高算法的效率,并且算法采用藐视准则”来特赦某些具有优 良状态的解,避免丢弃导致由于禁忌规则的约束使-些状态良好的解被遗留,进而既提高了有效性又保证了算法执行中种群的多样化,最终实现了全局优化。

2.2 禁忌粒子群算法设计由于PSO算法的缺陷,本研究在标准PSO中引入两种策略进行改进:引入禁忌搜索算法,通过Ts算法搜索每次迭代群体中的最优解,由于Ts算法的特点,使劣解也可以更新p ,有利于改善算法的全局搜索第4期 翁耀炜,等:基于禁忌粒子群算法的混流装配线排序研究性能;随机权重法,将权重 W设置为随机时,有可能加速算法的收敛速度,当算法初期找不到最好点时,由于 的线性递减可能导致算法最终不能收敛到全局最优点,而随机权重可以克服这种局限。算法的关键及细节设计如下:2.2.1 编码与解码方式由于传统的基于产品表示的编码方式并不适用于PSO算法的微柳化方式,本研究需要新的解码和编码方式。假设-个MPS中有 1个 A产品,2个B产品,3个C产品,则用数字 1代表A产品,2和3代表B产品,4、5和6代表C产品,然后引人Bean 提出的随机数表示法进行编码,解码则采用映射规则依次升序解码。

2.2.2 惯性权重更新方式将标准PSO算法中设定 W为服从某种分布的随机数,可以从两方面克服由于 W的线性递减的不足。

首先,在算法初期,随机 可以产品相对较小的W值,加快算法的收敛速度;其次,如果算法初期找不到最优解 ,随着 'tO的递减可能使算法最终收敛到局部最优点,随机 W可以克服这种局限性。

W的随机更新计算公式为:W/xor·N(0,1) (13)/.t/z - )rand(O,1) (14)式中:Ⅳ(0,1)-标准正态分布;rartd(O,1)-0~1之间的随机数; - , -随机权重平均值的最大值和最小值; -随机权重的方差,由算法给定。

2.2-3 最优微粒的更新方式在算法的每次迭代过程中都会得到-个g 值,若经过g次迭代后,g 的值保持不变,则使用禁忌搜索算法进行邻域解的搜索,由于禁忌搜索可以接受劣解 ,提高了跳出局部最优解的能力。由于禁忌搜索采用邻域搜索方式,需要重新解码、编码。在禁忌搜索算法中候砚、禁忌表长度、禁忌对象、藐视准则是影响算法性能的主要因素。根据优化模型的优化问题和编码方式,禁忌表长度则根据经验设置为0.6 Z(Z为候砚个数),候砚从邻域中选择若干目标值最佳的粒子人选,禁忌对象采用 目标值的变化,藐视准则设置为根据适应度值的大校最优微粒的Ts算法更新方式如图2所示。

基于上述思想,禁忌粒子群算法的算法流程如下 :(1)随机初始化种群中各微粒的位置和速度;(2)评价每个微粒的适应度 ,将当前各微粒的位置和适应度存储在各微粒的 P 中;将所有 P 中最优个体的位置和适应度值存储在 g 中;图2 微粒的TS算法更新方式(3)通过公式(11,12)更新微粒的速度和位移;(4)对每个微粒 ,将其适应度值与其经历的最好位置作比较,如果较好 ,则将其作为当前的最好位置 ,并同时更新 g 。;(5)解码并重新编码对群体中的最佳微粒执行禁忌搜索,并更新其Pk 及群体的g ;(6)通过公式(13,14)更新权重值;(7)若满足迭代次数,停止搜索,输出结果,否则返回步骤(2)。

3 实例研究 ·某冰箱装配企业某条总装线采用混流方式进行生产,该装配线共6个工作站,混合装配4种产品,计划 日产量分别为120台A产品、40台B产品、60台C产品和 40台 D产品。那么 日产的 MPS为 6A,2B,3C,2D,共 l3个产品。

各产品在各工作站上的装配时间以及工位长度如表1所示;各个不同产品装配所需零部件如表2所示。

GA是 目前求解混流装配线排序问题的常见方表1 工位装配产品时间及工位长度· 434 · 机 电 工 程 第30卷表2 各种产品所需零部件数量产品类型产品数量623213零部件消耗数量/件P3 P4 - - 033l17 - - 0l3215ABCD总数2 11 02 31 222 19O l3 03 21 2l7 16法n ]。因此,为了验证算法的优越性,本研究通过禁忌粒子群算法和GA算法对案例进行优化。GA算法参数 :编码方式采用基于产品的编码方式,染色体选择策略为轮盘赌,迭代次数为100,种群数量20,交叉算子为单点交叉再进行编码修正,交叉概率为0.9,变异概率为0.09←忌粒子群算法参数 :学习因子 c。C 2,:0.8, 0.8, 0.2,初始粒子种群数量为50个 ,迭代次数为500。装配线的运行参数为: 取 1Omm/s,A取 50 S,两个 目标函数的权重 W。,W:分别取0.5和0.5。各个算法都运行1O次,取最优值。

两种算法的优化结果如表3所示←忌粒子群算法的收敛图如图3所示。

表3 案例优化结果及对比迭代次数图3 禁忌粒子群算法收敛图由表 3和图3可知,禁忌粒子群算法在计算结果上优于GA算法,同时拥有很好的收敛速度。这是因为禁忌粒子群算法结合了粒子群算法全局搜索的能力以及和Ts算法在邻域搜索能力较强的特点以及随机权重更新方式,加强了算法的全局和邻域搜索的平衡能力,并且粒子群的快速收敛能力为禁忌搜索算法对提供了较好的初始解。

4 结束语为了更好地解决开放式作业域的混流装配线排序问题,本研究探索了-种新的粒子群算法。针对开放式混流装配线,笔者建立了以最携超载时间与平顺化零部件为优化目标的混流装配线排序数学模型;为求解该排序模型,给出了提高邻域搜索能力和跳出局部最优的解决方法,给出了平衡全局搜索和局部搜索的平衡方法,给出了禁忌粒子群算法流程;通过比较算例结果,本研究设计的禁忌粒子群算法在求解混流装配线排序问题优于遗传算法,验证了该算法的有效性。但由于禁忌粒子群算法还是对单 目标优化问题的求解,且没有对算法中的相关参数的设定进行灵敏度的分析,还存在禁忌粒子群算法在多目标优化问题上的适用性问题和对算法参数研究不足的问题 ,有待于进-步研究。

正在加载...请等待或刷新页面...
发表评论
验证码 验证码加载失败