Mathematical Modelling and Methods for Load Balancing and Coordination of Multi-Robot Stations

Sammanfattning: The automotive industry is moving from mass production towards an individualized production, individualizing parts aims to improve product quality and to reduce costs and material waste. This thesis concerns aspects of load balancing and coordination of multi-robot stations in the automotive manufacturing industry, considering efficient algorithms required by an individualized production. The goal of the load balancing problem is to improve the equipment utilization. Several approaches for solving the load balancing problem are suggested along with details on mathematical tools and subroutines employed. Our contributions to the solution of the load balancing problem are fourfold. First, to circumvent robot coordination we construct disjoint robot programs, which require no coordination schemes, are flexible, admit competitive cycle times for several industrial instances, and may be preferred in an individualized production. Second, since solving the task assignment problem for generating the disjoint robot programs was found to be unreasonably time-consuming, we model it as a generalized unrelated parallel machine problem with set packing constraints and suggest a tailored Lagrangian-based branch-and-bound algorithm. Third, a continuous collision detection method needs to determine whether the sweeps of multiple moving robots are disjoint. We suggest using the maximum velocity of each robot along with distance computations at certain robot configurations to derive a function that provides lower bounds on the minimum distance between the sweeps. The lower bounding function is iteratively minimized and updated with new distance information; our method is substantially faster than previously developed methods. Fourth, to allow for load balancing of complex multi-robot stations we generalize the disjoint robot programs into sequences of such; for some instances this procedure provides a significant equipment utilization improvement in comparison with previous automated methods.