Abstract In this paper a new heuristic for solving the assembly line re-balancing problem is presented. The method is based on the integration of a multi-attribute decision-making procedure, named “Technique for Order Preference by Similarity to Ideal Solution” (TOPSIS), and the well-known Kottas and Lau heuristic approach. The proposed methodology does not focus on the balancing of a new line, rather it takes into account the more interesting current industrial aspect of re-balancing an existing line, when some changes in the input parameters (i.e. product characteristics and cycle time) occur. Hence, the algorithm deals with the assembly line balancing problem by considering the minimization of two performance criteria: (i) the unit labour and expected unit incompletion costs, and (ii) tasks re-assignment. Particularly, the latter objective addresses the problem of keeping a high degree of similarity between previous and new balancing, in order to avoid costs related to tasks movements: operators training, product quality assurance, equipment installation and moving. To assess the performance of the presented approach a comparison with the original Kottas and Lau methodology is carried out. The results demonstrate the capability of the proposed algorithm of dealing with the multi-objective nature of the re-balancing problem. Solutions with advantages both in workload re-assignment, implying beneficial effects on the costs factors affected by tasks movements, and in completion costs are obtained in almost half of all problems solved. In the other cases, trade-off balancings with low increases in completion costs are presented.