In this thesis, we consider optimization problems arising in the PCB manufacturing industry using component placement machines.
First, given a component placement machine having single head, a PCB and components to assemble the PCB, we consider the problem of determining the allocation of component feeders and the mounting sequence of components while minimizing the PCB assembly time. We present a quadratic mixed integer programming model for the problem. And, we decompose the original problem into an assignment problem and an asymmetric traveling salesman problem, based on the analysis of the pick-and-mount operation in the machine. Furthermore, we propose a solution procedure to the overall problem using heuristics to solve the subproblems.
Second, given a component placement machine having multiple heads, a PCB and components to assemble the PCB, we consider the same problem as the case of the single-head machine. In the case of the machine with multiple heads, some different technological configurations of the machine make the problem more complicated, compared to the single-head machine. We decompose the problem into five subproblems; feeder grouping problem, head allocation problem, location clustering problem, feeder allocation problem and mounting sequence problem. For each subproblem, we develop a mathematical formulation and a solution approach based on the analysis of the problem. Moreover, we propose an overall solution approach to the original problem, incorporating the methods to solve the subproblems recursively.
Finally, given a component placement machine, several types of PCBs and a number of component feeders used to assemble the PCBs, we consider the problem of determining the PCB group with the objective of minimizing setup time of component feeders. We develop a column generation approach to find an optimal solution to the problem. In this approach, we decompose the original problem into master problem and column generation subproblem. Starting with a few columns in the master problem, we generate new columns successively by solving subproblem optimally. To solve the subproblem, we use a branch and cut approach.
Performances of all solution procedures are evaluated through series of computational tests on some real world problems and some randomly generated problems. The test results show that our solution approaches developed in this thesis give high quality solutions. Consequently, the solution approaches may be efficiently used for planning the PCB manufacturing process.
본 연구는 표면 실장기를 이용한 인쇄회로기판 생산 공정에서의 최적화 문제를 고려한다.
첫번째 문제는 하나의 헤드를 가진 표면 실장기를 이용하여 인쇄회로기판의 조립에 필요한 부품들이 주어진 경우에, 기판 조립 시간을 최소화 하기 위한 부품함의 배치와 부품 장착순서를 결정하는 것이다.
본 연구에서는 이 문제에 대한 2차 혼합 정수계획 모형을 제시한다. 제시된 모형은 비대칭 외판원 문제 (asymmetric traveling salesman problem)와 인접 제약식을 갖는 할당문제 (assignment problem with adjacency constraints)의 두 가지 하위 문제로 분해되며, 각 하위문제에 대한 발견적 (heuristic) 해법을 제시하였다. 하위문제에 대한 발견적 해법을 근간으로 전체 문제에 대한 해법 절차를 제시하였다.
두번째는 주어진 표면 실장기의 헤드 수가 여러 개인 경우에, 첫번째 문제에서와 같은 인쇄회로기판 조립시간을 최소화 하기위한 부품함의 배치와 부품 장착순서를 결정하는 문제이다. 여러 개의 헤드를 가진 표면 실장기는 하나의 헤드를 가진 실장기와 부품의 흡장착 방식에 있어서 차이가 있다. 이러한 차이로 인해, 본 연구에서는 전체 문제를 다섯 개의 하위문제로 분해하였는데, 각각은 부품함 그룹핑 문제 (feeder grouping problem), 헤드 할당 문제 (head allocation problem), 장착 위치 집단화 문제 (location clustering problem), 부품함 할당 문제 (feeder allocation problem), 장착순서결정문제 (mounting sequence problem) 이다. 각 하위문제에 대하여 수리 모형과 해법 절차를 제시하였으며, 각 하위 문제를 순환적으로 풀어 전체 문제에 대한 해를 구할 수 있는 해법 절차를 제시한다.
마지막으로, 본 연구에서는 한대의 표면 실장기와 여러 종류의 인쇄회로기판 및 각각의 기판 조립에 이용되는 부품이 주어졌을 때, 부품함의 초기 장착에 걸리는 시간을 최소화할 수 있는 기판 그룹을 결정하는 문제를 고려한다. 이 문제에 대한 최적화 해를 구하기 위한 방법으로 열 생성 기법 (column generation approach)을 제시하였다. 열 생성 기법은 주어진 문제를 주문제와 부문제로 나누고, 한정된 수의 열 (column)로 구성된 주문제에 대하여, 부문제의 최적 해를 구해 주문제의 열을 계속 더해나간다. 부문제를 풀기 위한 방법으로는 분기-절단 평면 기법 (branch and cut procedure)을 이용하였다.
본 연구에서 제시된 해법 절차의 성능평가를 위해 실제 산업현장에서의 문제 및 임의로 생성한 문제들에 대해 실험을 하였다. 실험 결과, 본 연구에서 제시된 해법 절차는 좋은 결과를 보여준다. 결론적으로, 본 연구의 결과물은 인쇄회로기판 조립공정에서 효율적으로 이용될 수 있을 것이다.
