Advanced algorithms and solution techniques for U-shaped assembly line balancing problems

Assembly line balancing problems entail allocation of work content to different work stations, optimizing certain criteria like minimizing the number of stations, fair allocation of work content and cycle time minimization etc. The U type layout is known for its exceptional efficiency and flexibility for line balancing problems. It also provides workers with opportunities to enhance their skills and work experience through cooperation and continuous learning. However, most of the models in literature ignore the full potential of U-lines and focus on a few narrow aspects for line balancing. In this dissertation, we address the issue of assigning tasks to workstations in ways that offer more choices to line managers and workers. In the first part of this dissertation, we develop effective logic cuts that exploit the logical structure of the problems, to improve the performance of integer programming model in terms of computational time. Proposed logic cuts enable the model to utilize bin-packing bounds at each station. Moreover, idle time information, and the knowledge about combinations of task assignments to stations, that produce solutions dominated by alternative assignments, are also exploited. Computational experiments demonstrate that our enhanced model outperforms the previously developed integer programming models in solving U-type assembly line balancing problems In the second part, we present novel ways of assigning fair workload to stations. Our model is able to fulfill different fairness criteria like minimization of mean absolute deviation and sum of squared differences. We also develop a method for distributing certain types of workloads regularly along the assembly line. This way, work sharing and benefits of communication between the workers can be enhanced. Our approach also enables the decision makers to allocate appropriate idle time to certain groups of tasks. This third part deals with uncertain task times. We develop a new variance bounds based approach to deal with the stochastic U-line balancing problem. The variance based approach is considerably simpler to implement and solves the problems efficiently, outperforming other chance constrained models used for U-lines in literature. Overall, we present methods that can be adapted easily to more complex assembly line balancing problems and provide additional choices to managers, researchers and decision makers.