Characterization and solution of traveling salesman problem with backend information processing

Abstract

This research focuses on the path planning problem that emerges during the inspection of a Printed Circuit Board (PCB) at semiconductor fabs. The inspection process consists of two elements: camera and backend information processor (BIP). The camera visits and captures the predetermined locations on a PCB. This image will be sent to BIP to be processed and obtain an inspection information. The objective of the research is to minimize the makespan of PCB inspection and characterizing the problem. The extension problem also provided by applying priority group. Meanwhile, characterizing problem are studying the effect of number of nodes, effect of variance in inspection time, effect of travel inspection ratio, effect of identical mBIP, and effect of non-identical mBIP. MILP and 2-Opt are the main solutions proposed to solve these problems. In addition of that, hybrid methods formed by exact solution (MILP), 2-Opt heuristic, branching approach, swapping history, and one step ahead allocation heuristic are also performed to solve several cases.