Research Of Assembly Line Balancing Problem Based On Branch-and-Bound Algorithm

During those processes ahead of assembly, all components are standardized and produced by mass production mode in order to reduce production costs. But at the last stage, assembly, small batch production is required in response to customers’personalized demands, which leads to the high complexity of the production management with assembly lines. The imbalance of workload among different stations will have an impact on the efficiency of the production line, employees’enthusiasm, and product quality. And effectively and efficiently balancing workload along assembly lines has a significant impact to a company’s development. Thus the study of assembly line balancing problem, the design of an efficient algorithm to optimize assembly line, are quite significant to improve production performance and meet the needs of the manufacturing industry.In this thesis, according to the global economic situation, the significance of assembly line balancing problem research is analyzed. Research status of assembly line balancing problem is summarized. The characteristic, classification and terminology used in this thesis of assembly line and assembly balancing problem are illustrated. The evaluation measures of assembly line balancing problem are illustrated by a example. For three types one-sided assembly line balancing problem and two-sided assembly one balancing problem of type-I, mathematical models are established respectively.Based on traditional branch-and-bound algorithm used to solve linear programming problem, the branch-and-bound algorithm to solve mixed-model one-sided and two-sided assembly line balancing type-I problem is proposed by transferring the mixed-model problem to simple problem with combined relation diagram. Lower bounds, operation assignment priority rule are utilized to reduce the computational effort. Precedence relation constraint and precedence relation matrix transformation rule are proposed to guarantee the feasibility of the proposed algorithm.Experiment proved that the proposed branch-and-bound algorithm is effective to get the optimal solution of assembly line balancing problem, the algorithm rules are efficient, and the proposed precedence relation matrix transformation rule and station starting rule are useful to guarantee the procedure feasibility. Although the algorithm still is difficult to solve large-scale problem because of the algorithm characteristic, it is the theory base to solve the large-scale problems. Furthermore, it can supply some guidance for shop management.