Stochastic two-sided U-type assembly line balancing: a genetic algorithm approach

In this paper, a novel stochastic two-sided U-type assembly line balancing (STUALB) procedure, an algorithm based on the genetic algorithm and a heuristic priority rule-based procedure to solve STUALB problem are proposed. With this new proposed assembly line design, all advantages of both two-sided assembly lines and U-type assembly lines are combined. Due to the variability of the real-life conditions, stochastic task times are also considered in the study. The proposed approach aims to minimise the number of positions (i.e. the U-type assembly line length) as the primary objective and to minimise the number of stations (i.e. the number of operators) as a secondary objective for a given cycle time. An example problem is solved to illustrate the proposed approach. In order to evaluate the efficiency of the proposed algorithm, test problems taken from the literature are used. The experimental results show that the proposed approach performs well.     

Two-sided U-type assembly line balancing problem

U-type and two-sided assembly lines are two types of design having advantages over traditional straight assembly lines. In this paper, a new line design hybrid of U-type and two-sided lines is presented. A bi-objective 0-1 integer programming model is developed to solve the line balancing problem of the proposed design. Zoning constraints are also considered for the proposed design. A number of test problems from the literature with up to 65 tasks are solved. Benefits of two-sided U-type lines are discussed.     

Stochastic assembly line balancing using beam search

This paper presents a beam search-based method for the stochastic assembly line balancing problem in U-lines. The proposed method minimizes total expected cost comprised of total labour cost and total expected incompletion cost. A beam search is an approximate branch and bound method that operates on a search tree. Even though beam search has been used in various problem domains, this is the first application to the assembly line balancing problem. The performance of the proposed method is measured on various test problems. The results of the computational experiments indicate that the average performance of the proposed method is better than the best-known heuristic in the literature for the traditional straight-line problem. Since the proposed method is the first heuristic for the stochastic U-type problem with the total expected cost criterion, we only report its results on the benchmark problems. Future research directions and the related bibliography are also provided in the paper.     

Optimization of the assignment of circuit cards to assembly lines in electronics assembly

Process planning is an important and integral function for ensuring efficient operations in printed circuit card assembly systems. This paper presents a new approach for solving the circuit card to assembly line assignment problem to minimize assembly time. This problem occurs frequently in process planning for electronic assembly systems and involves considering other interelated process planning problems. The line assignment problem is formulated as a large-scale mixed-integer programming problem and then solved using problem decomposition along with the branch-and-bound algorithm. Techniques for improving the solution time are discussed, and the solution approach is demonstrated using industry representative data sets from Lucent Technologies. For the data sets considered, the solution approach provides solutions within 3% of optimal in approximately 6 min of computation time on a Sun UltraSparc 2 Workstation. The solution approach developed for addressing the line assignment problem can serve as a useful decision-support tool by offering significant opportunities to improve the productivity and throughput of the assembly lines with improved process plans. The approach also allows planning engineers to respond faster to changes in production requirements. This research will be of interest to researchers in printed circuit card assembly systems and to practitioners in both original equipment manufacturing and contract assembly firms.     

Balancing Multi-Manned Assembly Lines With Walking Workers: Problem Definition,Mathematical Formulation,and an Electromagnetic Field Optimisation Algorithm

Assembly lines are widely used in industrial environments that produce standardised products in high volumes. Multi-manned assembly line is a special version of them that allows simultaneous operation of more than one worker at the same workstation. These lines are widely used in large-sized product manufacturing since they have many advantages over the simple one. This article has dealt with multi-manned assembly line balancing problem with walking workers for minimising the number of workers and workstations as the first and second objectives, respectively. A linear mixed-integer programming formulation of the problem has been firstly addressed after the problem definition is given. Besides that, a metaheuristic based on electromagnetic field optimisation algorithm has been improved. In addition to the classical electromagnetic field optimisation algorithm, a regeneration strategy has been applied to enhance diversification. A particle swarm optimisation algorithm from assembly line balancing literature has been modified to compare with the proposed algorithm. A group of test instances from many precedence diagrams were generated for evaluating the performances of all solution methods. Deviations from lower bound values of the number of workers/workstations and the number of optimal solutions obtained by these methods are concerned as performance criteria. The results obtained by the proposed programming formulations have been also compared with the solutions obtained by the traditional mathematical model of the multi-manned assembly line. Through the experimental results, the performance of the metaheuristic has been found very satisfactory according to the number of obtained optimal solutions and deviations from lower bound values.     

A priority rule-based constructive heuristic and an improvement method for balancing assembly lines with parallel multi-manned workstations

Assembly lines of big-size products such as buses, trucks and helicopters are very different from the lines studied in the literature. These products’ manufacturing processes have a lot of tasks most of which have long task times. Since traditional assembly line models including only one worker in each station (i.e. simple assembly lines) or at most two workers (two-sided assembly lines) may not be suitable for manufacturing these type of products, they need much larger shop floor for a number of stations and long product flow times. In this study, an assembly line balancing problem (ALBP) with parallel multi-manned stations is considered. Following the problem definition, a mixed integer programming formulation is developed. A detailed study of priority rules for simple ALBPs is also presented, and a new efficient constructive heuristic algorithm based on priority rules is proposed. In order to improve solutions found by the constructive heuristic, a genetic algorithm-based solution procedure is also presented. Benchmark instances in the literature are solved by using the proposed mathematical programming formulation. It has been seen that only some of the small-size instances can be solved optimally by this way. So the efficiency of the proposed heuristic method is verified in small-size instances whose optimal solutions are found. For medium- and big-size instances, heuristics’ results and CPU times are demonstrated. A comparative evaluation with a branch and bound algorithm that can be found in the literature is also carried out, and results are presented.     

Balancing manual mixed-model assembly lines using overtime work in a demand variation environment

This study deals with the balancing problem of a manual mixed-model assembly line, where the production volume or the product mix changes from shift to shift during the planning horizon. The unstable demand can be characterised by several representative scenarios, and the line uses overtime work to meet the demand variation. The balancing problem concerns how to assign assembly tasks to stations and determine the amount of overtime in each possible demand scenario. The objective is to satisfy the demand in each possible scenario with the minimum labour costs paid for both normal shifts and overtime work. A lower bound on the labour costs is proposed, and a heuristic algorithm is developed to quickly find a feasible solution. A branch, bound and remember (BB&;R) algorithm is then proposed to find better solutions. These solution methods are tested on 765 instances. The BB&;R algorithm obtains optimal solutions for 510 instances and gives high-quality solutions for the remaining 255 instances within 60?s. The experimental results show that the use of overtime work and adjustable cycle times significantly reduces the labour costs, especially when the demand or task processing time variations are large.     

U-shaped assembly line balancing problem with genetic algorithm

This paper presents a multi-objective genetic algorithm (moGA) to solve the U-shaped assembly line balancing problem (UALBP). As a consequence of introducing the just-in-time (JIT) production principle, it has been recognized that U-shaped assembly line systems offer several benefits over the traditional straight line systems. We consider both the traditional straight line system and the U-shaped assembly line system, thus as an unbiased examination of line efficiency. The performance criteria considered are the number of workstations (the line efficiency) and the variation of workload. The results of experiments show that the proposed model produced as good or even better line efficiency of workstation integration and improved the variation of workload.     

新型窄间隙MAG旋转电弧传感焊缝偏差提取算法

针对旋转电弧窄间隙MAG焊多层单道焊时坡口变化平缓,传统电弧传感方法灵敏度下降的缺点,提出了1种新的电弧传感偏差提取算法.对通过实验获取的U形底对接坡口不同焊缝偏差下的电弧信号进行分析,得出偏差的大小和方向与1个旋转周期内电流极值的数目和分布有很好的对应性,并通过Matlab仿真进一步验证上述关系的合理性和可靠性.由此...     

A Petri net-based heuristic for mixed-model assembly line balancing problem of Type-E

To effectively respond to the changing market demands, a manufacturer should produce variety of products with small lots. Thus, multiple products (models) are assembled simultaneously on a same line. However, it is very challenging to balance such an assembly line. This paper conducts a study on balancing a mixed-model assembly line of Type E. To solve this problem, a coloured-timed Petri net model is developed to describe the task precedence relationship. Also, the optimisation problem is formulated as a mathematical programming model. Then, with the models, a two-stage heuristic algorithm is proposed to solve the problem. At the first stage, based on the Petri net model, a P-invariant algorithm (PA) is presented to minimise the number of workstations. At the second stage, a heuristic is proposed to further minimise the cycle time by combining the PA with a binary search algorithm (BSA). Performance of the proposed method is evaluated by an illustrative example and numerical experiments. It is shown that it works well in terms of both solution accuracy and computational efficiency for large size problems.     

Simultaneous balancing and sequencing of mixed-model parallel two-sided assembly lines

Growing interests from customers in customised products and increasing competitions among peers necessitate companies to configure their manufacturing systems more effectively than ever before. We propose a new assembly line system configuration for companies that need intelligent solutions to satisfy customised demands on time with existing resources. A mixed-model parallel two-sided assembly line system is introduced based on the parallel two-sided assembly line system previously proposed in the literature. The mixed-model parallel two-sided assembly line balancing problem is illustrated with examples from the perspective of simultaneous balancing and sequencing. An agent-based ant colony optimisation algorithm is proposed to solve the problem. This algorithm is the first attempt in the literature to solve an assembly line balancing problem with an agent-based ant colony optimisation approach. The algorithm is illustrated with an example and its operational procedures and principles are explained and discussed.     

考虑人员能力差异的装配生产线优化

针对具有人员能力差异的装配生产线节拍优化问题,建立数学模型,提出一种先分配工序、后分配工人的分步求解启发式方法,并分别利用双种群遗传算法和分枝定界法对其进行求解;提出构建原优化问题的上下界,并以某企业的装配生产线为实例,验证了本方法的有效性与实用性。     

The type-II assembly line rebalancing problem considering stochastic task learning

Assembly lines with non-constant task time attribute are widely studied in the literature. For the SALBP-II assembly line balancing problem, we take account of stochastic task time changes, which is more practical than the deterministic times often assumed in industrial application. An algorithm – ENCORE, which leverages the traditional algorithm SALOME2, is proposed to address the assembly line balancing problem with stochastic task time attribute. Computational and statistical experiments are conducted to show the efficiency of proposed algorithms over traditional methods with regards to the improvement of total production times.     

A complete immunoglobulin-based artificial immune system algorithm for two-stage assembly flowshop scheduling problem with part splitting and distinct due windows

This paper considers a two-stage assembly flowshop scheduling problem with distinct due windows to minimise the sum of weighted earliness and tardiness. There are several identical parallel machines which produce parts in the first stage. When the required parts are available, a single assembly machine can group these parts into products in the second stage. It is assumed that a part can be split into sub-parts which can be processed independently on the parallel machines in the first stage. Setup is also considered. A mathematical model is established to describe and define the proposed problem. A new decoding method is developed by extending an existing decoding method. Two novel operators, named part splitting (PS) and optimal idle time insertion (ITI), are incorporated into the decoding procedure for improving the quality of the solution. A rule named Priority of Earliness and Tardiness (PET) and a Complete Immunoglobulin-based Artificial Immune System (C-IAIS) algorithm are proposed for solving the problem. To evaluate PET and C-IAIS algorithm, several existing algorithms are used in the experiments. Computational results show that C-IAIS algorithm performs better than other algorithms for solving the proposed problem.     

基于时间有限元的弹簧摆动力学新解法EI北大核心CSCD

弹簧摆问题是一种刚柔耦合的非线性动力学问题,随着电力技术的发展,弹簧摆在高压电塔减震方面获得了大规模的应用,但其动力学仿真还存在很多不完善之处。对此该文提出了一种利用时间有限元与保辛递推算法求解弹簧摆问题的新方法。该方法通过对弹簧摆的非线性摆动问题进行了近似积分处理,并对作用量采用矩形和梯形积分的方法获得保辛递推的形式。在提高求解速度的同时,提高了长时间求解的数值稳定性。为了体现了该文方法在求解内共振系统上的速度和稳定性优势,同已有结果进行两次对比,显示本算法较传统算法的计算速度、时间稳定性与精度上均存在一定优势。最后初步讨论了采用该方法求解大摆角混沌问题的途径。     

Order-oriented cooperative sequencing optimisation in multi-mix-model assembly lines

Order-oriented products assembly sequence among different assembly lines becomes a critical problem for mass customisation manufacturing systems. It significantly affects system productivity, delivery time, and manufacturing cost. In this paper, we propose a new approach to extend the traditional products sequencing from mixed model assembly line (MMAL) to multi-mixed model assembly lines (MMMALs) to obtain the optimal assembly sequence with the objectives of minimising consumption waviness of each material in the lines, assembly line setup cost, and lead-time. A multi-objective optimisation algorithm based on variable neighbourhood search methods (VNS) is developed. We perform an industrial case study in order to demonstrate the practicality and effectiveness of the proposed approach.     

Two-stage assembly flow-shop scheduling problem with non-identical assembly machines considering setup times

In this paper, we address the two stage assembly flow-shop problem with multiple non-identical assembly machines in stage two to minimise weighted sum of makespan and mean completion time. Also, sequence dependent setup times are considered for the first stage. This problem is a generalisation of previously proposed two stage assembly flow-shop problems (TSAFSP). In many real world industrial and production systems, there is more than one assembly machine to assemble job components. After extending a mathematical mixed-integer linear programming model to solve the problem, we use GAMS software. The TSAFSP has been known as NP-hard. Therefore, our more general problem is NP-hard too and so for large sized problems the right way to proceed is with the use of heuristic algorithms. So in this paper a hybrid VNS heuristic, which is a combination of the variable neighbourhood search (VNS) algorithm and a novel heuristic is developed and its solutions compared with solutions obtained by GAMS. Computational experiments reveal that the hybrid VNS heuristic performs much better than GAMS with respect to the percentage errors and run times.     

带时间窗的汽车总装线物料配送路径规划

分析了现阶段汽车总装线物料配送中存在的问题,建立了适用于汽车总装线物料配送路径规划的混合时间窗模型,提出了解决带时间窗的汽车总装线物料配送路径优化问题的改进遗传算法,使用了一种新的染色体编码方式和与之对应的交叉算子。针对传统轮盘赌随机操作选择误差比较大的弊端,提出改进的轮盘赌选择算子,加大随机数的产生次数并加入排序选择的思想,融合了最佳个体保存选择策略,提高算子的选优性能。实验表明该算法用于求解带时间窗的汽车总装线物料配送路径问题的有效性。     

An ant colony optimisation algorithm for scheduling in agile manufacturing

Producing customised products in a short time at low cost is one of the goals of agile manufacturing. To achieve this goal an assembly-driven differentiation strategy has been proposed in the agile manufacturing literature. In this paper, we address a manufacturing system that applies the assembly-driven differentiation strategy. The system consists of machining and assembly stages, where there is a single machine at the machining stage and multiple identical assembly stations at the assembly stage. An ant colony optimisation (ACO) algorithm is developed for solving the scheduling problem of determining the sequence of parts to be produced in the system so as to minimise the maximum completion time (or makespan). The ACO algorithm uses a new dispatching rule as the heuristic desirability and variable neighbourhood search as the local search to make it more efficient and effective. To evaluate the performance of heuristic algorithms, a branch-and-bound procedure is proposed for deriving the optimal solution to the problem. Computational results show that the proposed ACO algorithm is superior to the existing algorithm, not only improving the performance but also decreasing the computation time.     

SHAPE OPTIMIZATION OF A 2D BODY SUBJECTED TO SEVERAL LOADING CONDITIONS

An algorithm for shape optimization based on simultaneous solution of the equations and inequalities arising from Kuhn-Tucker necessary conditions is presented. Regular triangular FE assembly is proposed. Element vertices are associated with design variables directly or through spline parameters defining the boundary of the optimized body. This way, during the iteration procedure, FE assembly is automatically remeshed together with the motion of the optimized boundary. Multiple loading conditions are represented in the problem as equality conditions in the form of a set of equilibrium equations for each loading condition separately. From the necessary condition equations an additional, important relation between cost function, Lagrange multipliers associated with inequality constraints and their limit values is derived. The algorithm combines standard professional FEM programs with an optimizer proposed in the paper which is illustrated with shape optimization of several 2D bodies. The proposed approach is theoretically rigorous and relatively simple for practical applications, and allows considerations sensitivities, adjoint systems and constraints linearization to be avoided.