New solution approaches for assembly line balancing problems with parallel multi-manned workstations

Assembly lines of big-sized complex products; like buses, trucks, helicopters etc., 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. If they are produced in simple or two-sided assembly lines, then hundreds of stations are needed. This means that a long product flow time, a large area for establishment of the line, a high budget for the investment of equipments and tools in stations and several works in process are also required. In order to eliminate these disadvantages, assembly lines with parallel multi-manned workstations can be used to produce this type of products. In this study, these lines and one of their balancing problems are considered. After the problem definition and literature review, it is modeled as a mixed integer programming formulation. In the experimental study, it has been seen that only some of small-sized problems can be solved optimally by using this formulation. Therefore, after presenting a detailed study of heuristic methods, a new efficient constructive heuristic algorithm is proposed. The efficiency of the proposed heuristic method is verified in small-sized problems whose optimal solutions are found. For medium and big-sized problems, heuristic results and CPU times are presented. A branch and bound based enumeration algorithm is also proposed for solving considered problems optimally. This algorithm includes some efficient dominance and feasibility criteria which are developed based on problem-specific knowledge and the branching scheme used. A heuristic-based guidance for enumeration process is the one other efficient component of the algorithm. The branch and bound algorithm which was proposed for a special version of the studied problem in the literature has been modified to tackle the studied problem, and it is compared with the proposed algorithm. Through an analysis of the results, it has been seen that the proposed algorithm has better performance than the other one in terms of CPU times for the problems whose optimal solutions have been found by both algorithm, as well as the quality of feasible solutions of the problems whose optimal solutions could not be found by both algorithms for a given period of time.