An Ant Colony Optimisation Based Heuristic for Mixed-model Assembly Line Balancing with Setups

Balancing and sequencing of assembly lines is the process of partitioning the assembly work in terms of operations, and to assign and schedule them to workstations in an optimal way. In particular, in response to highly competitive market conditions, manufacturers face the problem of producing several models of a base product on the same assembly line, which leads to a mixed-model assembly line balancing problem. This problem is proven to be NP-hard and is computationally challenging. In addition to the usual problem constraints (e.g. precedences between operations and satisfying cycle times), we consider setup times between operations, which further complicates the problem. In this work, we present a novel ant colony optimisation approach, which is based on learning permutations of the operations. The permutations are then mapped to an assignment of operations to workstations in a greedy fashion. The numerical experiments demonstrate improvements both in the quality of solutions and significant improvements in computational time in comparison to the exact state of the art solution methods currently available in the literature.