Research On Optimization Model And Algorithm Of U-shaped Line Balancing In Lean Production

The U-shaped line is an important element of lean production and has many advantages compared to traditional straight line. The entrance and exit of the U-shaped line are at the same position and make it easy to implement pull production. In a U-shaped line, workstations are close, the walking distances of operators are short, material handlings are simplified and make it easy for one operator to operate multiple machines. The space at the centre of the‘U'is a shared area where operators can communicate, help each other and learn from others. The U-shaped line configuration allows for more possibilities with respect to the assignement of tasks to workstations, therefore the workstations needed by U-shaped line less than or equal to those needed by straight line at the same cycletime. More and more manufacturers are switching to U-shaped lines.U-shaped line balancing problem (ULBP) is a new branch of line balancing problem's research. ULBP focus on how to realize optimum allocation of production resource and is essential to design and organize U-shaped line. However, there are restrictive assumptions in current reseach, including assume no other assignement restrictions except cycletime and precedence restriction, assume operators'walking time are negligible, assume all equipments can be moved freely and so on. The optimation goals don't completely meet the requirement of lean production. On the other hand, another research point of ULBP, as a NP-hard problem, is to design good algorithm to find satisfactory solution within acceptable time. Ant colony algorithm ( ACO ) is one of swarm intelligence optimization algorithm based on constructive solution generation. Because ACO can generate feasible solution directly, is easy to handle complex constraints and integrate with priority rules, it has potential to sovle ULBP. However, ACO has some drawbacks, such as long searching time, premature convergence and so on. At present using ACO to solve ULBP is not effective.Therefore, according to the requirement of lean production and manufacturing practice, the paper establishes several optimization models of U-shaped line balancing, and then developes effective algorithm based on ACO from the characteristics of optimization models. The research aims to provide theory and method guidance for manufacturers to develop optimation tools of U-shaped lines. The main content of the dissertation is as follows:(1) The paper analyzes three operation mode of U-shaped line, elaborates five features of lean production, discusses the advantage of U-shaped line relative to traditional straight line and summarizes the optimal design rule of U-shaped line in lean production.(2) The bidirectional petri net model of precedence graph is set up. And then the process of task assignment can be described by the movement of token. The candidate task can be identified by reachability analysis of Petri net.(3) A hybrid algorithm of filtered beam search and ant colony algorithm (FBS-ACO) is proposed. FBS-ACO utilizes the positive and negative feedback mechanisms of ant colony algorithm and integrates the filtered beam search in the solution generation process. The ant will exploit several nodes in one step and accept one beam node by global evaluation and probability local evaluation to enhance the ant's ability to find the optimum solution. The paper proposes a new pheromone updating rule to preserve the best information and avoid premature convergence. An extensive experimental study on 269 testing problem indicates that FBS-ACO display very competitive performance.(4) Seven assignment restrictions in manufacturing pratice, incluing continuous link, non-continuous link, strong imcompatible, weak imcompatible, setup time, workstation total attribute and unilateral attribute are consided. The paper set up integer programming model and reduces the model size by computing the upper and lower bounds of workstations. And then, improves FBS-ACO to handle the complex restriction using ant's candidate list to filter the feasible elements.(5) Based on operator's walking shape, walking distance and time are calculated and considered in U-shaped line balancing problem. A new lower bound of workstation is put forward as the global evaluation in FBS-ACO. And then in order to meet the requirement of just-in-time and flexible operators, U-shaped line rebalancing problem is solved according to whether the device on the line can be moved.(6) Combined U-shaped lines balancing prolems in lean production are analyzed systematically. With regard to serial combined U-shaped lines balancing, a goal programming model which considered the minimization of workstations and the first/last workstation's operation time. Two hybrid algorithms of FBS-ACO, local search and branch and bound are developed to solve serial combined U-shaped lines balancing problems. With regard to parallel combined U-shaped lines balancing, a non-linear integer programming model which considered the minimization of equipment and operator's cost is set up and is sloved by a two-stage method.(7) In order to meet the requirement of just-in-time, flexible operators, level production and flow manaufacutring, a cooperation optimization model of balancing and sequencing of mixed-model U-shaped line is set up. The objects of the model are minimizing the workstation at the given cycletime, balancing workload, minimizing the setup cost and time and leveling the material flow. An improved multi-objective co-evolution ant colony algorithm is developed. The results of experimentation indicate the proposed algorithm's effectiveness.