The Research On The Multiple Rules Combination Algorithm For The Type-2Assembly Line Balancing Problem

Assembly line balancing problem (ALBP) is an important problem inmanufacturing area. Balancing assembly line can balance each station time and makesupplies maintain a state of continuous and stable, so it raises the production efficiency,improve the utilization rate of equipment, and guarantee the stability of product quality.ALBP is a NP-hard problem in combination optimization concerning the arithmetic, andits exact solution is not found in polynomial time, so the research of effective algorithmfor it has important theoretical significance. There are three innovative points in thepaper on the type-2ALBP as follows.An multiple rules combination algorithm based on the cellular automation (CA) isproposed to the type-2simple assembly line balancing problem (SALBP-2), whichminimizes the cycle time of the line. In the algorithm, two evolution rules, amelioraterule and recovery rule, are proposed based on the interaction among evolvable cell,replaceable neighbor, evolved cell and evolved neighbor in cellular space. Thecomputational results of comparative experiment show the effectiveness of CAalgorithm.Five simple rules are formed based on the the rules in CAalgorithm, which are taskselection rule, task assignment rule, task exchange rule, bound rule and search rule withvariable step. The functions of them are emphasizing the global optimization, payingattention to the local search, strengthen the local optimization, indicating the searchingdirection for algorithm, and speeding up the search speed, respectively.At the same time,the sufficient conditions of applying task exchange rule are also proposed and proved.The computational results of comparative experiment for the type-1simple assemblyline balancing problem (SALBP-1), SALBP-2and the type-2U assembly line balancingproblem (UALBP-2) show that the proposed algorithm has obvious advantage onlarge-scale multiple stations ALBP and its precision and computation speed are superiorto the existing algorithms. In the algorithm, the fast search speed and the good solutionquality are created on heuristic factors and rules, and the optimization mechanismformed by combining multiple rules, respectively.Some corresponding active control strategies of four constraints, mutual exclusion,stiffened edge, necessary assignment and imperfect assignment in assembly line, are proposed and systematically melted to task selection rule and task assignment rule,respectively, which strengthen the practical of the proposed algorithm. Moreover, thenecessary conditions of existing feasible solutions in multiple constraints assembly linebalancing problem (MCALBP) are also proposed and proved. The conclusions that theproposed algorithm can effectively solve the feasible solutions of MCALBP-2wheneach constraint of it are independence, and it is superior to the penalty function methodand the dependent response method in the matter of obtaining the feasible solutions, canbe drawn according to the search mechanism.