Study For Two-sided Assembly Line Balancing Problem With Multiple Constraints Based On Hybrid Bat Algorithm

Two-sided assembly lines were evolved from single assembly lines,which were mainly used for the assembly of large products such as automobiles and loaders.Compared with single assembly line,it had the advantages of shortening the assembly line length,improving the utilization of auxiliary machinery,and reducing the logistics cost.However,compared to the single assembly line balancing problem,the two-sided assembly line balancing problem was more complicated.Because stations of both sides can assign tasks and tasks have their preferred sides,tasks between stations on either side may have contextual relationship,which may result in latency due to sequence depended.In addition,there were some additional constraints such as positional constraints,zonging constraints and synchronous constraints in practical production.These constraints may exist coupling relationship among them.Aiming at the two-sided assembly line balancing problem with multiple constraints of type I,including positional constraints,zoning constraints and synchronous constraints,its mathematical model was constructed.After analyzing discrepancy and conjunction of the problem,the optimization algorithm was proposed against its complex property of NP-hard.The main achievements of this paper are as follows:1)After comparing and analyzing the advantages and disadvantages of other decoding methods,merged with the strategy of selecting a station before selecting tasks,a new decoding method oriented to positional constraints was proposed.A task selection decision tree of the current mated-station was established around the positional constraint tasks,and appropriate tasks were selected according to the leaf nodes.The proposed decoding method solves the problem of high proportion of unfeasible solutions due to the neglect of positional constraints in the past and improves the quality of decoding method.2)Aiming at the two-sided assembly line balancing problem with multiple constraints of type I,based on the proposed decoding method,a hybrid bat algorithm was proposed,by combing the global optimizing ability of bat algorithm and the local optimizing ability of variable neighborhood search algorithm.For two-sided assembly line balancing problem,the coding method based on task topology sorting matrix and the dual coding mapping mechanism was designed,which mapped the continuous physical space of flight to the discrete space of solutions.In order to filter out better solutions under the same total number of workstations,a new heuristic objective was added to guide the population to search in a better direction.To improve the local searching ability of bat algorithm,the bat algorithm was combined with the variable neighborhood search algorithm to avoid premature.Experiments based on benchmark problems were carried out to validate the superiority and effectiveness of the proposed algorithm.3)two-sided assembly line balancing software system with good Interactivity and expansibility was developed by object-oriented programming.Unified modeling language was adopted to design and model the the balancing system.C++,with high running efficiency,was used as the development language.The basic functions required by the software was realized based on Qt development platform and SQLite database.