We investigate the problem of mixed model assembly line balancing with sequence dependent setup times. The problem requires that a set of operations be executed at workstations, in a cyclic fashion, and operations may have precedences between them. The aim is to minimise the maximum cycle time incurred across all workstations. The simple assembly line balancing problem (with precedence constraints) is proven to be NP-hard and is consequently computationally challenging. In addition, we consider setup times and mixed model product types, thereby further complicating the problem. In this study, we propose a novel ant colony optimisation (ACO) based heuristic, which unlike previous approaches for the problem, focuses on learning permutations of operations. These permutations are then mapped to workstations using an efficient assignment heuristic, thereby creating feasible allocations. Moreover, we develop a mixed integer programming formulation, which provides a basis for comparing the quality of solutions found by ACO. Our numerical results demonstrate the efficacy of ACO across a number of problems. We find that ACO often finds optimal solutions for small problems, and high quality solutions for medium-large problem instances where mixed integer programming is unable to find any solutions.
History
Volume
12576
Pagination
125-137
Location
Online from Canberra, A.C.T.
Start date
2020-11-29
End date
2020-11-30
ISBN-13
9783030649845
Language
eng
Publication classification
E1 Full written paper - refereed
Editor/Contributor(s)
Gallagher M, Moustafa N, Lakshika E
Title of proceedings
AI 2020 : Proceeding of the 33rd Australasian Joint Conference on Artificial Intelligence and Advances in Artificial Intelligence 2020
Event
Joint artificial intelligence and advances in artificial intelligence. Conference (33rd : 2020 : Online from Canberra, A.C.T.)