A design method for minimum cost path of flying probe in-circuit testers
作者： Katsumi Konishi , Seiichi Shin , Yuki Hiratsuka , Fumihiko Katoh
DOI:
关键词: Flying probe 、 Minimum cost path 、 Type (model theory) 、 Travelling salesman problem 、 Mathematical optimization 、 Integer programming 、 Mathematics 、 Algorithm
摘要: This paper focuses on X-Y type in-circuit testers, which has two flying probes. The problem of finding the ordering inspection points that minimizes total time is an expansion travelling salesman (TSP). We formulate minimum traveling cost probes as 0–1 integer programming, and algorithm to solve this proposed. Experimental results show effectiveness method.
参考文章(6)
Lyle A. McGeoch, David S. Johnson, The Traveling Salesman Problem: A Case Study in Local Optimization ,(2008)
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Gábor Pataki, Teaching Integer Programming Formulations Using the Traveling Salesman Problem SIAM Review. ,vol. 45, pp. 116- 123 ,(2003) , 10.1137/S00361445023685
Vašek Chvátal, William Cook, George B. Dantzig, Delbert R. Fulkerson, Selmer M. Johnson, Solution of a Large-Scale Traveling-Salesman Problem Operations Research. ,vol. 2, pp. 7- 28 ,(1954) , 10.1007/978-3-540-68279-0_1
Jon Louis Bentley, Experiments on traveling salesman heuristics symposium on discrete algorithms. pp. 91- 99 ,(1990) , 10.5555/320176.320186
D.B. Shmoys, E.L. Lawler, Jan Karel Lenstra, A.H.G. Rinnooy Kan, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization ,(1985)