基于分枝定界法的装配线第一类平衡问题研究基于分枝定界法的装配线第一类平衡问题研究.pdf

《基于分枝定界法的装配线第一类平衡问题研究基于分枝定界法的装配线第一类平衡问题研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、机械设计与制造第2期2O4MachineryDesign&Manufacture2012年2月文章编号：1001—3997(2012)02—0204—03基于分枝定界法的装配线第一类平衡问题研究米徐发平唐秋华刘海(武汉科技大学机械自动化学院，武汉430081)Branch—and-boundalgorithmforassemblylinebalancingtypeIproblemXUFa-ping，TANGQiu—hua，LIUHai(CollegeofMechanic-Automation，WuhanUniversityofScienceandTechnology，Wuha

2、n430081，China)【摘要】在生产节拍给定的条件下，针对装配线平衡的数学模型，提出一种求解装配线第一类平衡问题的改进分枝定界法，该方法将较好的解存储起来，最后归纳可得到最优解的装配序列，避免了传统方法只能输出一个最优解的缺点。同时运用3种分枝规则加速寻找最优解；使用了两种定界方法的最大下界规则，节点控制规则和最大闲置时间规则被用来剪掉不能获得最优解的分枝，减小搜索空间。并且将影响算法性能的要素作了简要的分析，实验结果表明该算法具有良好的性能。关键词：装配线平衡；分枝定界；最优解【Abstract】Abranch-and-boundalgorithmarepropose

3、dtosolvetheassemblylinetype—Ibalancingproblem,inwhichthecycletimeisgiven．Thebettersolutionsaresaved,andthenconcludetheassemblysequenceswhichCanobtaintheoptimalsolutionsinthemethod．Theshortcomingofformermethodinwhichonlyoneoptimalsolutioncanbeobtainedisavoided．Meanwhile，threebranchingrulesar

4、eusedtospeedupfindingtheoptimalsolution．Themaximallowerboundruleinwhichtwoboundingmethodsareused,nodecontrollingrulesandmaximalidletimeruleareappliedtocutthebranchwhicheann’tobationtheoptimalsolutionstodiminishthesearchingspace．Andfactorswhichinfluencedthealgorithmpetformo~eale帆edbriefly．Th

5、eexperimentalresultstestifythatthealgorithmiseffwient．}Keywords：Assemblyline；Branch-粕d—bOnl：Optimalsolution’；+，、1hhr_，r_，_，l_，

6、hh·二N_1hH—N，

7、1nht__nht、，th。：『，-rt。．．1N，-，--1-+1h-．1-．1h1-_1--1h-1h-1，中图分类号：TH16文献标识码：A1引言用已分配工位的闲置时间与理论最小闲置时间的比较进行剪枝，即每完成一个工位的分配，就计算一次闲置时间，如果其闲置时装配线平衡就是将具有装配优先关系约束的

8、装配工作分配到间大于理论最小闲置时间，则剪枝。虽然该方法避免了FABLE中相应的工位上完成，并达到设定的优化目标。装配线平衡问题是著大量不必要分枝的出现，但存在以下不足之处：名的组合优化问题，同时也是NP难问题。目前，启发式方法为求解(1)如果全局下界值增加，一些分枝有可能会重复搜索；(2)装配线平衡问题的主流算法，文献m。虽然这一方法能较得到解，没有加入任何分枝规则，不能保证搜索向较优的方向靠近；(3)只但一般只能找到较优解或次优解，无法保证找到的解为最优解。能输一个最优解。1997年，一些国外科研人员提出双向分枝定界分枝定界法是一些科研人员于6O年代提出的一种部分枚法，S

9、ALOMEt4~。SALOME在利用文献[21和文献pL些优点的同时也举方法。其将所有可行解都枚举出，故能找到最优解；但与此同克服了其中的一些缺点。该方法主要运用局部下界方法和动态双时，用此方法求解大规模问题所需的时间与硬件需求难以接受。向分枝规则，与此同时对前人提出的一些定界规则也做了相应加入一定的剪枝方法，减小枚举树规模可有效的解决这一矛盾。的扩展。1999年，一些国外科研人员在[51中对FABLE，OptPackI~，1988年，国外科研人员提出快速求解装配线平衡第一类问题的Eureka和SALO