A Petri net approach for simple assembly line balancing problems

A simple assembly line balancing problem of type-1 (SALBP-1) aims to minimize the number of workstations for a given cycle time. In the relevant literature, several heuristics based on a branch-and-bound procedure, tabu search, and genetic algorithms (GAs) were proposed to solve SALBP-1. In this paper, an algorithm based on the reachability analysis of Petri nets is developed for SALBP-1. The proposed algorithm searches enabled transitions (or assignable tasks) in the Petri net model of precedence relations between tasks, and then the task minimizing the idle time is assigned to the station under consideration. 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 optimal solutions of traditional heuristics and a GA.     

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.     

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 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.     

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.     

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

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

A novel feasible task sequence-oriented discrete particle swarm algorithm for simple assembly line balancing problem of type 1

To solve the simple assembly line balancing problems of type 1 (SALBP-1), almost all of particle swarm algorithms (PSAs) for SALBP-1 adopt task sequence-oriented solution representation and are limited to the priority-based indirect encoding of feasible task sequence (FTS) so far. In this paper, firstly a novel FTS-oriented particle swarm algorithm (FTSOPSA) that directly records a FTS by a particle, named direct discrete PSA (DDPSA), is proposed to solve SALBP-1. In the DDPSA, a new multi-fragment crossover-based updating mechanism is developed, and the fragment mutation is incorporated into the DDPSA to improve exploration ability. Secondly, a systematic comparison of DDPSA and two existing FTSOPSAs as well as two existing genetic algorithms (GAs) has been presented against a set of instances selected from the literature and 15 randomly generated instances of SALBP-1. Comparisons between the FTSOPSAs and existing GAs show promising higher performance of the proposed DDPSA for SALBP-1, and also show that the direct encoding of FTS seems superior to the priority-based indirect encoding of FTS for solving SALBP-1.     

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.     

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

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

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.

     

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

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

发动机装配生产线平衡问题研究

装配线平衡问题是装配线规划中的重要组成部分,在工作站数量确定的前提下采用人工平衡法进行装配线的规划,得到多个方案,从中选择接近最佳的方案.以某发动机装配线为案例进行了分析,并使用eM-Plant软件对规划的装配线进行了仿真.     

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.     

采用遗传算法的混流装配线平衡多目标优化

针对混流装配线操作人数已知、生产节拍待定情况下的平衡问题,研究了混流装配线第二类平衡问题的优化方法,以均衡各工作站的加权平均负荷、最小化生产节拍为优化目标,建立了求解加权平均负荷与生产节拍加权和的数学模型,并运用遗传算法对其进行求解.各优化目标数量级的统一,简化了算法求解过程,在保证解的有效性的同时提高了算法求解效率.算例分析验证了算法的有效性.     

A branch-and-bound algorithm for two-sided assembly line balancing

Two-sided (left- and right-side) assembly lines are often used in assembly of large-sized products, such as buses and trucks. A large number of exact algorithms and heuristics have been proposed to balance the well-known classical one-sided assembly lines. However, little attention has been paid to balancing the two-sided lines. Moreover, according to our best knowledge, there is no published work in balancing the two-sided assembly line exactly. In this study, a branch-and-bound algorithm is proposed to solve the balancing problem optimally. Experiments are carried out to demonstrate the performance of the proposed method and the results are promising.     

A Web-based interactive advisor for assembly line balancing

Assembly line balancing (ALB) aims at distributing those work required to assemble a product in mass or series production among a set of workstations in an assembly line. Heuristics approaches, in corporation with computer simulation, have demonstrated a number of advantages in practice. Recognizing the importance of interactions between production planners and the scheduling system, this paper discusses the design and implementation of a Web-based ALB advisor for scheduling hard disk drive assembly involving multiple criteria. With the assistance of such an ALB advisor, production engineers, who may have difficulties in understanding those sophisticated ALB heuristics, can remotely present and specify their particular ALB problems. Based on the user input, the advisor will compose a schedule based on various heuristic algorithms embedded in its library. The schedule can be manipulated directly via a graphical user interface. The advisor also generates simulation models for the user-specified ALB problems and presents the user with performance evaluation of the suggested ALB solutions.     

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...     

基于装配关系复杂性的装配线动态平衡问题

在制造系统复杂性分类研究的基础上,将装配系统的结构复杂性区分为装配关系复杂性、装配工艺复杂性和系统配置复杂性,并基于信息熵给出了装配关系复杂性的度量方法.通过分析各类结构复杂性与影响系统的动态性因素之间的关系,将装配关系复杂性应用于装配线动态平衡问题的研究中,给出了最小装配关系复杂性差异度这一动态优化目标,并结合静态目标装配线平衡损失进行求解.优化结果表明,该指标能降低动态性因素对装配线平衡的影响,为系统所必须具备的柔性程度提供具体的量化指标.同时,通过对装配错误发生率的仿真验证研究表明,该方法能有效降低各工位的错误发生率和总完工时间,实现装配线的动态平衡.     

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

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

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

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