基于蚁群算法的装配线平衡问题研究

发布时间：2018-03-18 16:51

本文选题：蚁群算法　切入点：模拟退火　出处：《华中科技大学》2011年硕士论文　论文类型：学位论文

【摘要】：装配线是装配制造系统中广泛采取的一种生产模式。装配线平衡就是实现劳动生产率、设备利用率和满足市场需求三者之间的平衡的过程,它是装配线的设计与管理中需要关注的一个重要问题,其直接影响到制造系统的生产效率和产品的质量。装配线平衡问题(Assembly Line Balancing Problem, ALBP)是一种典型的NP-hard问题,其包含的子问题极其丰富,按装配线的平面布局分为直线型、U型,按作业时间分为确定型、随机型,按平衡目标分为最小化节拍、最小化工作站和最小化平衡指标等装配线平衡问题。由于该问题的复杂性,采用传统最优化方法寻求最优解的效果并不理想。近年来,通过模拟自然界中蚂蚁觅食行为过程中所表现出的某些群体智能特点而发展的蚁群算法(Ant Colony Optimization , ACO),为装配线平衡问题的求解提供了新的思路。本文首先在分析蚁群算法优化机理的基础上,提出了一种自适应蚁群算法求解单一确定型装配线平衡问题。在该算法中,针对装配线平衡问题的具体特点,设计了一种蚂蚁分配方案可行解的构造策略,提出了一种区分度更好的评价解质量的目标函数,同时自适应地调整信息素的挥发度等系数,在保证收敛速度的条件下提高算法的全局搜索能力,通过求解标准测试问题集验证了算法的有效性。随后,研究了另一类更为复杂的装配线平衡问题——随机U型装配线平衡问题。在实际生产中,特别是在人工装配线中,装配任务的作业时间是随机的。通过建立该问题的数学模型,针对该问题的特点,提出了一种混合蚁群算法求解随机U型装配线平衡问题,该算法利用SA的局部搜索能力来克服ACO易陷入局部最优的缺点。应用提出混合蚁群算法求解标准测试问题集,验证了该混合算法的可行性和有效性。最后,开发了基于蚁群算法的ACO-ALBP原型系统,并通过对确定型和随机型装配线平衡问题实例的测试验证了系统的有效性。对全文进行了总结,并对ACO算法和装配线平衡问题未来的研究方向进行了展望。
[Abstract]:Assembly line is a widely adopted production mode in assembly manufacturing system. The balance of assembly line is the process of achieving the balance among labor productivity, equipment utilization ratio and meeting market demand. It is an important problem in the design and management of assembly line, which directly affects the production efficiency of manufacturing system and the quality of products. The assembly line balance problem Line Balancing problem (ALBPs) is a typical NP-hard problem, which contains a lot of sub-problems. According to the layout of the assembly line, it can be divided into linear type U type, definite type and random type according to the working time. The problem of assembly line balance is divided into three parts: minimum beat, minimized workstation and minimum balance index according to the objective of equilibrium. Due to the complexity of the problem, the traditional optimization method is not effective in finding the optimal solution. Ant Colony Optimization (ACOG), developed by simulating some swarm intelligence characteristics of ants in the process of foraging behavior in nature, provides a new idea for solving the assembly line balance problem. In this paper, based on the analysis of the optimization mechanism of ant colony algorithm, an adaptive ant colony algorithm is proposed to solve the single deterministic assembly line balance problem. In this paper, a construction strategy of feasible solution for ant allocation scheme is designed, and an objective function for evaluating the quality of solution with better discrimination is proposed. Meanwhile, the coefficients of volatilization of pheromone are adjusted adaptively. The global search ability of the algorithm is improved under the condition that the convergence rate is guaranteed. The validity of the algorithm is verified by solving the standard test problem set. Then, another more complex problem of assembly line equilibrium, random U-type assembly line equilibrium, is studied. In practical production, especially in manual assembly line, The job time of assembly task is random. According to the characteristics of the problem, a hybrid ant colony algorithm is proposed to solve the random U-type assembly line balance problem. The local search ability of SA is used to overcome the disadvantage that ACO is prone to fall into local optimum. A hybrid ant colony algorithm is proposed to solve the standard test problem set, which verifies the feasibility and effectiveness of the hybrid algorithm. Finally, the ACO-ALBP prototype system based on ant colony algorithm is developed, and the validity of the system is verified by the test of deterministic and stochastic assembly line balancing problems. This paper summarizes the whole paper, and looks forward to the future research direction of ACO algorithm and assembly line balance problem.
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TH186

【相似文献】