New MILP model and station-oriented ant colony optimization algorithm for balancing U-type assembly lines

Abstract

U-type assembly lines are extensively applied in modern manufacturing systems for higher flexibility and productivity. This research presents a new mixed-integer linear programming model to minimize the number of stations, where one expression is used to represent the precedence relationship constraint rather than two expressions as in published researches. The proposed model is compared to three other models and the correctness or the incorrectness of these models are analyzed by enumerating all possible allocations between the two tasks. The comparison makes it clear that the proposed model iterates fast and achieves competing results. Additionally, a modified ant colony optimization approach, referred to as station-oriented ant colony optimization algorithm, is proposed to tackle large-size problems. This method generates a set of task assignments and selects the best one for the current station, rather than obtaining only one task assignment at a time. A set of benchmark problems is solved using the proposed method and the results are compared to those obtained by the state-of-the-art methods (including ULINO) and the variants of ant colony optimization approach. The computational study demonstrates the superiority of the proposed method over the compared ones as it achieves optimal solutions for 255 cases (out of 269) and outperforms the current best method, ULINO, for 21 cases. It is also worthy to mention that the station-oriented procedure improves the performance of original ant colony optimization by a significant margin.