Multi-manned assembly line balancing with time and space constraints: A MILP model and memetic ant colony system

In the automotive and electronics industries, more than one operator work in the same workstation to assemble a high volume of products. When assigning the tasks of these products to workstations, we should fulfill the cycle time and precedence relationships. Limited research has investigated space restrictions to store tools or components (i.e., time and space assembly line balancing problem) but without multi-manned workstations. Therefore, this paper addresses the time and space assembly line balancing problem with multi-manned workstations. Our model includes five kinds of constraints by considering task assignment, precedence, cycle time, sequencing and space constraints. Our aim is to minimize the total number of workstations and operators via a new MILP model and memetic ant colony system. The memetic ant algorithm uses a new solution generation method which integrates 16 heuristic rules to help each ant of the algorithm to effectively build a feasible solution. New pheromone release strategies, including deposition and evaporation, are employed to update the global pheromone quantity. Additionally, a new best solution update method does not retain the solution with minimum objective function but balances the workload of each operator. Our experiments show the effectiveness of solving the MILP model by exact methods in small-scaled instances and the superiority of the memetic ant colony optimization algorithm in all the instances.