基于Pareto蚁群算法的拆卸线平衡多目标优化

为提高产晶拆卸效率,针对拆卸线平衡问题建立了数学模型.该模型以最小拆卸线闲置率、负荷均衡和最小拆卸成本为优化目标.结合拆卸线平衡问题的具体特点,提出了一种改进的基于Pareto解集的多目标蚁群优化算法.算法采用小生境技术,引导蚂蚁搜索到分布良好的Pareto最优解集,并以被支配度和分散度为个体评价规则.实验测试结果表明了该算法的可行性.最后,结合企业生产实际,给出了所提模型与算法的具体应用.     

U型布局的拆卸线平衡问题及其求解算法研究

建立以精益生产为准则的多目标U型拆卸线平衡问题模型,并提出了一种改进的人工蜂群算法求解该问题。通过利用蜜蜂对蜜源进行标记完成自身学习过程,有效地改善了蜜蜂寻找蜜源的能力。为避免算法搜索过程中陷入局部最优,采取模仿其他蜜蜂的搜索行为打破僵局,并将改进人工蜂群算法应用于求解文献中的实例,通过对比表明改进人工蜂群算法可以寻找到更优的解,从而验证了算法的可行性。最后,将改进人工蜂群算法用于U型布局求解,将U型布局结果与直线型布局进行对比,体现了U型布局的优越性。     

A mathematical model and ant colony algorithm for multi-manned assembly line balancing problem

In real-world assembly lines, that the size of the product is large (e.g., automotive industry), usually there are multi-manned workstations where a group of workers simultaneously perform different operations on the same individual product. This paper presents a mixed integer programming model to solve the balancing problem of the multi-manned assembly lines optimally. This model minimizes the total number of workers on the line as the first objective and the number of opened multi-manned workstations as the second one. Since this problem is well known as NP (nondeterministic polynomial-time)-hard, a heuristic approach based on the ant colony optimization approach is developed to solve the medium- and large-size scales of this problem. In the proposed algorithm, each ant tries to allocate given tasks to multi-manned workstations in order to build a balancing solution for the assembly line balancing problems by considering the precedence relations, multi-manned assembly line configuration, task times, and cycle time constraints. Through computational experiments, the performance of the proposed ACO is compared with some existing heuristic on various problem instances. The experimental results validate the effectiveness and efficiency of the proposed algorithm.     

空间约束下多目标拆卸线平衡问题的改进狼群算法

考虑实际拆卸过程中的工作站空间面积约束,以最小化工作站数目、空闲时间均衡指标、拆卸成本及工作站实际使用面积极差值为优化目标,建立空间约束下的多目标优化数学模型,提出一种离散多目标改进狼群算法求解.通过对游走行为、召唤行为和围攻行为进行离散化,引入Pareto解集思想及NSGA-Ⅱ拥挤距离机制,获得多个高质量、多方面综合的较优解.通过对不同规模基准算例的求解,对比说明所提算法的有效性和优越性.最后,将该算法用于求解考虑空间约束的某打印机拆卸实例中,得到10组可行的任务分配方案,表明考虑空间约束的模型和所提算法的可行性.     

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

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

Station ant colony optimization for the type 2 assembly line balancing problem

An improved ant colony optimization (ACO), namely, station ant colony optimization (SACO), is proposed to solve the type 2 assembly line balancing problem (ALBP-2). In the algorithm, ACO is employed to search different better combinations of tasks (component solutions) for each station; an iteration compress mechanism is proposed to reduce the searching space of feasible solutions of ALBP-2. Three heuristic factors [i.e., (1) task time, (2) number of successors, and (3) number of releasable successors], two pheromones, and a task assignment mechanism are proposed to search better component solutions for every station. Finally, the effectiveness and stability of SACO are confirmed through comparison with literatures in 23 instances included in nine examples.     

A particle swarm optimization algorithm with neighborhood-based mutation for sequence-dependent disassembly line balancing problem

For environmentally conscious and sustainable manufacturing, manufacturers need to incorporate product recovery by designing manufacturing systems to include reverse manufacturing by considering both assembly and disassembly systems. Just as the assembly line is considered the most efficient way to assemble a product, the disassembly line is seen to be the most efficient way to disassemble a product. While having some similarities to assembly, disassembly is not the reverse of the assembly process. The challenge lies in the fact that it possesses unique characteristics. In this paper, we consider a sequence-dependent disassembly line balancing problem (SDDLBP) that is concerned with the assignment of disassembly tasks to a set of ordered disassembly workstations while satisfying the disassembly precedence constraints and optimizing the effectiveness of several measures considering sequence-dependent part removal time increments. SDDLBP is not a trivial problem since it is proven to be NP-complete. Further complications occur by considering multiple objectives including environmental and economic goals that are often contradictory. Therefore, it is essential that an efficient methodology be developed. A new approach based on the particle swarm optimization algorithm with a neighborhood-based mutation operator is proposed to solve the SDDLBP. Case scenarios are considered, and comparisons with ant colony optimization, river formation dynamics, and tabu search approaches are provided to demonstrate the superior functionality of the proposed algorithm.     

改进蚁群算法求解圆排列问题

圆排列问题是典型的NP完全问题,且蚁群算法已成功地解决了许多组合优化的难题.介绍了一种求解圆排列问题的蚁群算法,并通过改变概率、下一个元素的选择方式以及采用分段交换,对求解圆排列问题的蚁群算法进行了优化.提出了一种改进的蚁群算法,并将其应用于求解圆排列问题.仿真实验的结果表明,该方法有效地改善了蚁群算法的搜索时间较长,且易于过早地收敛于非最优解的缺陷.     

基于蚁群算法的产品拆卸序列规划研究

为了能以较高的效率求解出产品拆卸序列的方案,首先阐述了拆卸可行性信息图的概念,将产品的拆卸序列规划问题转述成对该加权有向图中具备最优值的路径搜索和寻优问题。提出了一种蚁群优化算法,并结合对产品元件的拆卸路径求解工具,以实现对产品拆卸可行性信息图的构建和对拆卸方案的搜索和寻优。蚂蚁的一条遍历路径代表了一个描述产品元件拆卸的方案;蚂蚁已经遍历过的路径上代表可行操作的节点数决定了其留下的信息素。启发式信息的求解分为两个部分,包括了确定启发式向量和求出启发式信息值,它们分别表征了方案的可行性及其优异程度。最后,通过一个实例,验证了这一方法的可行性及其计算效率。     

多目标混合流水车间作业调度的演化算法

针对多目标条件下混合流水车间作业调度的优化问题,提出了一种在优化进程中能够动态调整适应度分配的演化算法。该算法采用矩阵编码描述多阶段并行机调度方案,结合问题的优化模型,对每一代Pareto解在各目标方向上的改善程度进行度量,进而通过多目标的选择性权重系数计算种群个体的适应度,以获得在改善指示方向上的选择压力。通过BENCHMARK问题测试和实际算例分析,表明新算法的性能优于现有的求解算法,特别是对于高维多目标优化问题,能够获得较高的演化收敛速度。     

求解物流配送路径优化问题的一种改进蚁群算法

物流配送路径优化是现代物流配送服务的关键环节之一,由于需求的小批量和动态变化等特点,需要设计一个快速有效的求解算法。为此,构建了物流配送路径优化问题的数学模型,设计了一个改进的蚁群算法来求解该问题,引进了选择算子、插点操作和动态改变算法参数等改进措施,开发和实现了一个试验软件包。仿真试验结果表明,该算法具有较好的全局寻优能力,收敛速度快,是解决物流配送路径优化问题的有效算法。     

基于蚁群算法的单目标选择性拆卸序列规划研究

根据选择性拆卸的特点,介绍了基于混合图的选择性拆卸模型.该模型描述了零件间的接触连接关系和非接触优先关系.基于混合图模型,以单个零件为目标推理生成选择性拆卸序列解空间;然后结合蚁群算法,从所有可行序列中搜索最优或接近最优的单目标零件选择性拆卸序列.最后,通过实例说明该方法的可行性和有效性.     

A new multi-objective approach in order to balancing and sequencing U-shaped mixed model assembly line problem: a proposed heuristic algorithm

The International Journal of Advanced Manufacturing Technology - Mixed model production is the practice of assembling different and distinct models in a line without changeovers responding to...     

An improved artificial bee colony algorithm with MaxTF heuristic rule for two-sided assembly line balancing problem

Two-sided assembly line is usually used for the assembly of large products such as cars, buses, and trucks. With the development of technical progress, the assembly line needs to be reconfigured and the cycle time of the line should be optimized to satisfy the new assembly process. Two-sided assembly line balancing with the objective of minimizing the cycle time is called TALBP-2. This paper proposes an improved artificial bee colony (IABC) algorithm with the MaxTF heuristic rule. In the heuristic initialization process, the MaxTF rule defines a new task’s priority weight. On the basis of priority weight, the assignment of tasks is reasonable and the quality of an initial solution is high. In the IABC algorithm, two neighborhood strategies are embedded to balance the exploitation and exploration abilities of the algorithm. The employed bees and onlooker bees produce neighboring solutions in different promising regions to accelerate the convergence rate. Furthermore, a well-designed random strategy of scout bees is developed to escape local optima. The experimental results demonstrate that the proposed MaxTF rule performs better than other heuristic rules, as it can find the best solution for all the 10 test cases. A comparison of the IABC algorithm and other algorithms proves the effectiveness of the proposed IABC algorithm. The results also denote that the IABC algorithm is efficient and stable in minimizing the cycle time for the TALBP-2, and it can find 20 new best solutions among 25 large-sized problem cases.

     

基于蚁群算法的选择装配

选择装配是一种由低加工精度零件获得高精度装配件的方法,可归纳为一个组合优化问题,蚁群算法是解决这类问题的有效方法.综合考虑选择装配中的匹配率和匹配精度,提出以综合装配质量指标为选择装配的目标函数.为了求解选择装配的组合优化问题,在蚁群算法的框架内提出一个考虑信息素分布为节点模式的蚁群算法解构造图模型,并详细讨论蚁群算法的实现过程.通过对实例的仿真计算,考证该方法的实效性.     

A P-invariant-based algorithm for simple assembly line balancing problem of type-1

A simple assembly line balancing problem of type-1 (SALBP-1) concerns minimizing the number of workstations on an assembly line for a given cycle time. In this problem only a single product with deterministic task times is considered. Since the SALBP-1 is known as an NP-hard, considerable research effort has been spent to develop heuristic approaches. In this study we develop a different heuristic approach based on the P-invariants of Petri nets. The algorithm is coded in MATLAB, and its efficiency is tested on Talbot’s and Hoffmann’s benchmark datasets according to some performance measures and classifications. A computational study validates its effectiveness on Tonge’s 70-task problem by comparison with solutions of traditional heuristics and a genetic algorithm reported to perform well.     

求解带区域约束的双边装配线平衡问题的一种改进蚁群算法

双边装配线在汽车、工程机械等大中型装配作业中广为应用.实际装配线布局往往受复杂区域约束,针对带区域约束的双边装配线平衡第一类问题建立数学模型.进而提出求解该问题的一种改进蚁群算法,该算法针对双边装配线问题特点建立构造解方式,综合采用禁忌集合、优先集合与蚁群搜索规则相结合的方法构造出满足区域约束条件的可行解,并采用改进的蚁群综合搜索规则搜寻任务.最后,经大量算例测试对比,验证了所提算法的有效性.     

一种求解变速机调度问题的混合蚁群优化算法

针对一类变速机总加权拖期调度问题,提出一种混合蚁群优化算法.引人单机拖期调度问题中性能良好的修正预计完成时间的一种修改版本启发式规则,计算信息素初值,有利于算法跳出局部极值,并在局部搜索阶段,采用单亲遗传算法基因移位算子,有效优化当代最优解.通过均匀试验设计和统计分析,确定算法的关键参数组合,将算法应用于随机生成的不同规模的40个算例,并将其结果与同类文献中算法的优化结果进行对比分析.结果表明,在相同迭代次数下,混合算法优于对比算法.     

改进自适应蚁群算法求解集装箱装载瓦楞纸板问题

集装箱装载瓦楞纸板问题是一个复杂组合优化问题,针对该问题,在满足基本的装载要求和约束条件下,充分利用自适应蚁群算法的强搜索能力和启发式算法对具体问题的针对性,将自适应蚁群算法和启发式算法结合,提出一种改进的自适应蚁群算法,求解出了最优装载方案。对纸板装载问题建立模型,提出目标函数并给出约束条件;根据实际情况提出启发式规则,将其与自适应蚁群算法进行结合;使用实例进行仿真验证。将仿真结果与实际情况进行对比,装载体积率明显提高,证明了该算法能够提高瓦楞纸板装载空间利用率,节省了人力,大大提高了工作效率。     

Improved multi-objective ant colony optimization algorithm and its application in complex reasoning

The problem of fault reasoning has aroused great concern in scientific and engineering fields.However,fault investigation and reasoning of complex system is not a simple reasoning decision-making problem.It has become a typical multi-constraint and multi-objective reticulate optimization decision-making problem under many influencing factors and constraints.So far,little research has been carried out in this field.This paper transforms the fault reasoning problem of complex system into a paths-searching problem starting from known symptoms to fault causes.Three optimization objectives are considered simultaneously: maximum probability of average fault,maximum average importance,and minimum average complexity of test.Under the constraints of both known symptoms and the causal relationship among different components,a multi-objective optimization mathematical model is set up,taking minimizing cost of fault reasoning as the target function.Since the problem is non-deterministic polynomial-hard(NP-hard),a modified multi-objective ant colony algorithm is proposed,in which a reachability matrix is set up to constrain the feasible search nodes of the ants and a new pseudo-random-proportional rule and a pheromone adjustment mechinism are constructed to balance conflicts between the optimization objectives.At last,a Pareto optimal set is acquired.Evaluation functions based on validity and tendency of reasoning paths are defined to optimize noninferior set,through which the final fault causes can be identified according to decision-making demands,thus realize fault reasoning of the multi-constraint and multi-objective complex system.Reasoning results demonstrate that the improved multi-objective ant colony optimization(IMACO) can realize reasoning and locating fault positions precisely by solving the multi-objective fault diagnosis model,which provides a new method to solve the problem of multi-constraint and multi-objective fault diagnosis and reasoning of complex system.