基于遗传算法和仿真分析的混合装配线平衡问题研究

为兼顾混合装配线平均负荷平衡和瞬时负荷平衡,提出了一种综合运用遗传算法和仿真分析的混合装配线平衡问题的求解方法.首先,基于综合作业顺序图和多品种产品在每个作业任务上的平均作业时间,采用遗传算法求解混合装配线平衡问题,其优化目标是均衡各工作站平均作业时间;然后,对遗传算法求解的一组较优解,从瞬时负荷平衡方面进行仿真分析,其优化目标是最大化各工作站利用率;最后,综合两个优化目标确定混合装配线平衡问题的最优解.通过算例分析,验证了求解方法的有效性.     

基于改进遗传算法的双边装配线平衡

针对目前研究较少的双边装配线平衡问题,研究了双边装配线的特点及其对平衡的特殊要求,建立了双边装配线平衡问题的数学模型.根据双边装配中任务具有操作方位约束,以及工位上分配任务的操作顺序与平衡结果直接相关等特点,提出了相应的符合问题特性的遗传算法.该算法采用基于序列、任务及其分配方位组合的编码方法,运用可行的交叉与变异算子,使搜索过程仅在可行解空间内进行,提高了效率.算例结果验证了算法的有效性.     

基于遗传算法的直线型和U型混流装配线平衡问题研究

针对混流装配线上不同产品作业时间差异导致的工作站瞬时负荷不均衡问题,提出了一种改进的直线型和U型混流装配线多目标平衡方法,并以装配线平衡率、平滑指数作为平衡效果的评价指标.综合考虑工序分配约束、工作站约束、优先关系约束和节拍约束等约束条件,同时兼顾工作站数最小和各工作站内不同品种产品负荷均衡2个目标函数,分别建立直线型...     

基于混合优化算法的装配线平衡问题

为求解给定装配线生产节拍、最大化装配效率的装配线平衡问题,根据装配线的特点和平衡优化需求,分析了装配作业顺序、站位数量等因素对装配线站位内作业分配的影响,综合考虑装配线平衡率和平滑系数,建立了装配线平衡问题数学模型,并设计了 一种结合遗传算法(Genetic Algorithm,GA)、蚁群算法(Ant Colony ...     

第2类装配线平衡问题的改进规则组合算法

针对大规模第2类单边装配线平衡问题,提出一种改进的规则组合算法。算法利用操作选择规则选择操作,根据操作分配规则择优分配操作,通过操作交换规则,将当前工位中的操作和未分配操作进行互换,使得当前工位的工位时间满足定界条件。对操作交换规则,提出其能够实施的充分条件。对两个大规模算例Arcus-111和Scholl-297进行求解,将求解结果与已有规则组合算法进行比较,验证了算法的有效性和高效性。     

基于约束矩阵和遗传算法的装配线平衡优化方法

针对装配线平衡问题(ALB),归纳装配作业的三种基本约束关系,并通过约束矩阵描述装配作业的约束与优先权关系.利用遗传算法对装配线平衡问题(ALB)进行分析和求解.算法中,提出基于约束矩阵的作业序列编码策略,设计遗传操作(选择、交叉、变异),并通过基于模拟退火机制的精英策略加速了算法收敛.最后,用实例证明此算法的有效性.     

Optimization of workcell layouts in a mixed-model assembly line environment

Mixed-model assembly lines enable automotive manufacturers to build different vehicles using the same equipment and facility. They allow a more rapid response to changes in customer demand. However, the increased production flexibility creates new challenges regarding assembly line planning and balancing. Part of this problem is how to allocate stock within the workcells so that non-value added operations, such as walking and waiting, are minimized. This paper addresses the issue of workstation layout optimization. Different formulations can be used to minimize non-value added time depending on the level of sophistication desired. We present three different optimization formulations and give an example of an optimized workstation layout.     

基于多目标模糊决策的混流装配线排序算法

在订单生产环境下的多品种混合装配线排序问题的基础上,建立了三种目标函数:最小化生产周期时间、最小化工作站闲置与超载时间以及最大化平均负荷率.引入了一种基于模糊决策模型的改进后的混合遗传禁忌搜索算法.在求解过程中,计算出所有个体的各个目标特征值的影响度、影响度因子以及相对隶属度,将目标特征值矩阵转化为相对隶属度矩阵,应用模糊层次分析法,计算多目标排序问题中各指标的权重值,用综合评判线性加权平均模型进行评价,构造出相对适应度函数.     

Two-sided assembly line balancing using an ant-colony-based heuristic

Two-sided assembly line balancing (ALB) problems usually occur in plants which are producing large-sized high-volume products, such as buses, trucks, and domestic products. Many algorithms and heuristics have been proposed to balance the well known classical one-sided assembly lines. However, little attention has been paid to solve two-sided ALB problems. Moreover, according to our best knowledge, there is no published work in the literature on two-sided ALB problems with zoning constraints (2sALBz). In this study, an ant-colony-based heuristic algorithm is proposed for solving 2sALBz problems. This paper also makes one of the first attempts to show how an ant colony heuristic (ACH) can be applied to solve 2sALBz problems. In the paper, example applications are presented and computational experiments are performed to present the suitability of the ACH to solve 2sALBz problems. Promising results are obtained from the solution of several test problems.     

双边装配线第二类平衡问题研究

与传统的单边装配线平衡问题不同,双边装配线平衡不仅要考虑任务优先顺序关系,而且要考虑任务操作方位以及双边并行作业的要求.为有效地解决双边装配线第二类平衡问题,建立了数学模型,并提出一种基于归组策略的启发式平衡算法.该算法利用图深度优先搜索方法,将任务进行归组,然后运用一系列启发式规则对组进行选择分配.最后,通过在某装载机总装生产线上的应用,验证了算法的有效性.     

Branch-and-bound algorithms for simple assembly line balancing problem

In this paper, exact algorithms for solving the simple assembly line balancing type I problem are presented. The proposed algorithms consist of a constructive and two destructive algorithms. Several well-known lower-bound computational methods are also applied in these algorithms. Computational experiments were carried out to test the performance of the proposed algorithms based on a set of benchmark problem instances. The computational results show that the algorithms proposed in this paper are efficient in solving the simple assembly line balancing benchmark problem instances. Moreover, a problem instance whose optimal solution had previously been unknown is solved by one of the proposed algorithms.     

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

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

A comparative evaluation of assembly line balancing Heuristics

A comparative evaluation is presented of six popular assembly line balancing heuristics, namely, ranked positional weight, Kilbridge and Wester, Moodie and Young, Hoffman precedence matrix, immediate update first fit, and rank and assign heuristic. The evaluation criteria used are the number of excess stations given, line efficiency, smoothness index and CPU time. The trade and transfer phase of the Moodie and Young method is applied to all heuristics, then the results are compared based on the evaluation criteria. Twenty problems each with 5 different cycle times are used for the comparative evaluation of heuristics. All six heuristics are coded in C++ language. Among the six considered heuristics the Hoffmann enumeration procedure performs best; but, the execution time for the Hoffmann procedure is longer because this procedure enumerates all the feasible alternative sets of tasks for the stations. An erratum to this article is available at .     

小生境遗传算法在混流装配线排序中的应用

在总结混流装配线排序问题的基础上,根据汽车制造业的实际情况建立一种新的汽车装配线排序模型.根据装配车型的关键件不同,引入车型相似度的概念,并将小生境遗传算法用于以最大化相似度总和为目标的混流装配线优化排序问题,同时将简单遗传算法和小生境遗传算法性能进行比较.最后通过在某汽车制造厂中的应用,验证小生境遗传算法在解决混流装配线生产排序问题中的有效性.     

Scheduling of an assembly line with a multi-objective genetic algorithm

Scheduling problems are difficult combinatorial problems because of the extremely large search space of possible solutions and the large number of local optima that arise. A multi-objective genetic algorithm is presented as an intelligent algorithm for scheduling of the mixed-model assembly line in this paper. The Pareto ranking method and distance-dispersed approach are employed to evaluate the fitness of the individuals. The computational results show that the proposed multi-objective genetic algorithm is quite effective.     

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.     

基于改进遗传算法的混装线多目标优化

在考虑产品需求速率的前提下,提出了调整加工成本的新方法,建立了混流装配线平衡问题的多目标优化模型。设计了基于自然数序列和拓扑排序的改进遗传算法对模型进行求解,改进交叉、变异操作来保护优秀基因,提出了种群扩张机制。对经典问题的计算试验结果表明,改进遗传算法在降低生产节拍的同时能优化产品加工成本,在求解效率和求解质量方面有显著的成效。     

混流装配线平衡分析与算法设计

为了设计合理可靠的混流装配线并有效地提高装配线的平衡率,分析了混流装配线的特点并设计了一种以工序对调为核心思想的新算法,该算法的逻辑结构较为简易且兼容性高,能够与现有的大部分投产排序方法相结合,对装配线做进一步平衡优化处理.具体地描述了新算法的原理和执行过程,最后将该算法应用到某厂的汽车车灯线束装配线上,结果验证了该方法的有效性和可行性.     

A bidirectional heuristic for stochastic assembly line balancing Type II problem

In this paper, a heuristic algorithm is proposed to solve the single-model stochastic assembly line balancing Type II problem. For a given number of workstations and a pre-specified assembly line reliability, which is the probability of the workload not exceeding the cycle time for the whole assembly line, the proposed algorithm tries to obtain a solution with the smallest cycle time. In the first stage, the tasks are assigned to workstations from the forward and backward directions alternatively. In the second stage, the workload is smoothed by swapping tasks among workstations. At last, the upper bound of the cycle time obtained in the second stage is reduced step by step until the smallest cycle time satisfies the pre-specified assembly line reliability. The performance of the proposed algorithm is compared with a modified version of Moodie and Youngs algorithm by applying them to some literature problems. The computational results show that the proposed algorithm is efficient in minimizing the cycle time for the single-model stochastic assembly line balancing problem.     

基于改进遗传算法的某发动机厂装配线平衡研究

以一条发动机装配线为研究对象,对工序作业元素进行重新划分,建立作业元素优先关系。以装配线的生产均衡指数为目标函数,通过改进遗传算法实现对研究对象的优化方案设计。运用Matlab实现算法获得了最优装配顺序及各工位作业分配结果,使生产线获得更好的平衡状态,从而提高生产效率。