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

.82oO 7年8月ComputerIntegrated M删facturi“gSystemsAug.2o07 文章编号:l006—5911(2007)08—1632—07 求解装配线平衡问题的一种改进蚁群算法张则强,程文明,...
求解带区域约束的双边装配线平衡问题的一种改进蚁群算法_教育学/心理学_人文社科...运用改进蚁群算法求解直... 暂无评价 6页 2.00 多目标装配线平衡的优化....
宋莉波 (华南理工大学 工商管理学院, 广东 广州 510640) 摘要: 针对直线型 和 U 型装配线第一类平衡问题, 提出一种基于最优成分 信息素更新规则的改进蚁群算法...
一种基于混合品种装配线均匀零部件消耗速 率的方差算法,对目标追踪法进行了改进...当前已有蚁群算法用于混合品种装配线平衡 问题的求解,文献[17]提出了一种基于...
计算机系统应用 201 0年第1 9卷第1期 蚁群算法求解装配线平衡第一类问题毛凌...王金诺 求解装配线平衡问题的一种改进蚁群算法[期刊论文]-计算机集成制造系统 ...
基于一种新蚁群算法的装配线平衡研究 2 2 城, 张超勇 ( 1. 湖北汽车工业...陈志楚 ,田 摘要: 采用改进蚁群优化算法来 解决装配 线平 衡的第 一类 问题...
基于一种新蚁群算法的装配线平衡研究 2 2 城, 张超勇 ( 1. 湖北汽车工业...2 2. 1 基于改进的蚁群算法的装配线平 衡问题研究可行解的构造 考虑到 2. ...
ALBP)是制造领域里的一个重要问题,其 微小的改进都可以导致经济上显著的收益,...当前已有蚁群算法用于混合品种装配线平衡 问题的求解,文献〔17】提出了一种基于...
求解装配线平衡问题的一种... 9页 5财富值 运用改进蚁群算法求解直线... 暂无...在已有装配线平衡设计迭代算法的基础上,提出了一种改进的迭代算法,该方法采用...
运用改进蚁群算法求解直线型和U型装配线平衡问题 针对直线型和U型装配线第一类平衡问题,提出一种基于最优成分信息素更新规则的改进蚁群算法。算法在任务和工作站之间释...
针对混合型双边装配线平衡问题 的具体特点,本文运用一种改进的智能蚁群优化算法来平衡装配线。首先,建 立数学模型,描述这个问题。然后,利用智能蚁群优化算法来解决...
热门文档