Precedence constrained TSP arising in printed circuit board assembly

Abstract

Component placement sequencing is a challenging problem that arises in automated assembly of printed circuit boards. While for some placement machines all placement sequences are acceptable, in other cases some sequences are not allowed because of the shape of the placement head. In such cases, while the head moves down to perform a placement, it might damage a previously placed component, and the problem of determining a minimum cost and at the same time acceptable sequence leads to a Precedence Constrained Travelling Salesman Problem formulation. In this study, a solution procedure to such a formulation is developed and its implementation in a real PCB assembly environment is discussed.