文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 机械/仪表 > 求解装配线平衡问题的一种改进蚁群算法
侵权投诉

求解装配线平衡问题的一种改进蚁群算法

为求解给定节拍最小化工作站数的第Ⅰ类装配线平衡问题,提出了一种改进的蚁群算法。在该算法中,针对装配线平衡问题的具体特点,给出了蚂蚁分配方案的生成策略。通过在任务和任务分配序列的位置之间释放信息素,并采用信息素总合规则进行更有效的信息素累积。为提高搜索效率,以综合考虑装配任务作业时间和后续任务数的分级位置权重为蚁群算法的启发式信息。最后,通过对大量测试问题

维普资讯 doc.guandang.net

第8期

张则强等:解装配线平衡问题的一种改进蚁群算法求

(mme it Up aeF rtFtI F方法和分级指 I dae d t i - i,UF ) s

() 2给定装配线的工作站数,装配线节拍最使

派法等。基于简单启发式规则的传统算法仅按某种 规则求得一种可行方案,于 AL P的结构特征,由 B

小,以获得最大的生产率,被称为第Ⅱ类

AL P, B记 为 S B一。 AL P 2

如任务间优先顺序关系、业时间长短分布等的差作异,至今尚无某一优先规则确保对该类所有问题都能够求得最优解,而难以提供具有普适性的实用因

() 3给定工作站数的上下限,小化装配线总延最误时间,即最优化装配线效率,这类更具一般性的问 题,为 S B- 记 AL P E。

算法。随着智能优化算法的发展,传算法、遗禁忌搜 索和模拟退火法等亚启发式方法在 AL P中得以 B 应用【,表现出良好的性能。 4并]

对于 S B一, AL P 1数学模型表示为:

∑t ma 一;一甘 mi。 x ; n () 1

由模仿蚂蚁觅食行为发展起来的蚁群算法,在 旅行商问题 ( rv l gS l nP o lm, S )二 T a ei ae rbe T P、 n ma S tS n s ,i .. ,一≠,,一 1 2…,;( ) i ,, 2 k一 1

次分配问题、机调度问题、单车辆路径问题等研究中得到了广泛应用【 9引,在求解组合优化问题中也表现出卓越的性能,别适合大规模启发式搜索,特

US 一 E;

() 3

Vi∈ S, J∈ S,若 P 一 1则 z≤ Y ( ),; 4 t S )≤ C k一 1,2…,。 (,, () 5

AL P的结构适合采用蚁群算法求解。 B 当前已有蚁群算法用于 AL P的求解,献 B文[ 3研究了在给定节拍下最小化工作站数的 AL P 1] B的一种蚁群算法,其信息素累积方式过于简化,但以至对于许多测试问题不能找到最优解,有待进一还步改善。文献[ 4提出了一种基于蚂蚁技术的方 1]法,于求解具有并行工作站、用随机作业时间等复杂因素的混合装配线平衡问题,验表明算法具有良试好的性能,文中算法仅采用了信息素的累积,但没有

式中,为装配线上任务的集合,一{,2…, E E 1, n;为分配到第 k个工作站的任务集合, S }S即一 (f务i i任 被分配到第志个工作站}C;为装配线的节拍;( tS )为第 k个工作站的总作业时间,( zS )一

∑t P一( 为A B的优先矩阵,,; p)

LP任务i 是 J S∈ k

任务 j的直接前接元素时,一 1任务 i . P;不是任务 J 的直接前接元素时,一 0 P。

式 () 2为发生约束,确保任一任务只能分配到某 一

考虑问题内含的启发式信息,故求解效率不高。 针对现有研究的不足,文结合 AL P的特本 B 征,出了一种改进的蚁群算法,方法采用在任务提该和任务分配序列的位置之间释放信息素的方式, 以及信息素总合规则,以综合考虑任务作业时间和后续任务数的位置权重作为蚁群算法的启发值。试验结果表明,该算法能快速有效地求解 AL P,取得 B并 了令人满意的结果。

工作站中,同一任务不能重复分配至多个工作即

站; ()式 3确保所有任务都被分配; ( )式 4为优先关系约束,保任务分配满足装配顺序关系,确没有任务分配至一个比其先前任务所分配的工作站更早的工作站中,即对于任一任务 J分配至工作站 Y中,任务若 i是任务J的先前任务,则任务 i只能分配到编号为 1 ~ Y中的某一工作站上,不能分配到序号大于 Y而 的工作站; ( )为节拍约束,式 5表示分配到任一工作站的所有任务的作业时间之和必须不大于节拍 C。 简单 A B L P的一个实例 (ak o J c s n问题 )图 1如

1装配线平衡问题描述 装配线平衡是指在工艺条件等约束下,有限将 的任务集合分配到一定数量的工作站中,以使每个工作站的作业时间满足一定的节拍要求,少工作减 站的闲置和过载时间,小化平滑指标。最 单一型装配线平衡问题 ( i l Ase l Smpe smby L n aa c gP o l ieB ln i rbe n m,S B,只考虑工序 AL P)是

所示。作业优先顺序图是个有向无环图,每个节点表示一项任务,每项任务有唯一的任务序号 (圈内数字表示)和作业时间 (上方数字表示 )圈。作业顺序图中的箭头线表示任务问的优先顺序关系,头线箭的头节点表示任务完成后,能开始实施箭头线的才尾节点表示的任务。

间的优先关系约束的单一产品的直线型装配线,可 分为如下三类:

2算法介绍 蚁群觅食等行为中

蕴含着自组织、正反馈、随机性、布式等重要机制,蚁能够自适应地找到从巢分蚂

() 1给定装配线节拍,最小工作站数,求被称为第 1类 AL P,为 S B -。 B记 AL P 1

求解装配线平衡问题的一种改进蚁群算法

上一页第2页

你可能喜欢

  • 工时管理
  • 汽车生产线
  • 生产线平衡分析
  • 流水线平衡
  • 汽车总装工艺
  • 工艺流程
  • 生产流水线设计

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email