In this thesis, we consider operational optimization problems of gantry-type surface mounting machines with multi-heads. We decompose the problems into hierarchical related problems, component allocation, feeder arrangement, work cycle formation, pickup sequencing, and mounting sequencing problems. Since all problems in the hierarchy are combinatorial problems and computationally intractable, we developed effective algorithms based on genetic algorithm, column generation algorithm, and branch-and-price algorithm.
First, we address the component allocation and feeder arrangement problems arising in a dual-gantry multi-head surface mounting machine. The component allocation decision is to determine which components are mounted by each gantry and the feeder arrangement decision is to determine how the feeders are arranged on the feeder slots of a feeder rack. Since multi-head gantry-type machines have distinct features of simultaneous pickup, feeder interference, we need to develop unique solution approaches for the problems. We propose a genetic algorithm of optimizing the two decisions simultaneously. The two decisions are optimized by maximizing the number of simultaneously picked up components for each access of a multi-head module, or equivalently minimizing the number of pickups, and balancing the workload between the two gantries. We propose a gene encoding method that incorporates interference between the feeders of different widths. In order to evaluate the two decisions using a fitness function based on the gantry workload, we propose a greedy heuristic for the work cycle formation and pickup sequencing decisions.
Second, we consider the work cycle formation problem in multi-head gantry-type machines. The work cycle formation decision is to determine which components are picked up for each pick-and-mount work cycle. A multi-head surface mounting machine fills up multiple heads with components through one or multiple pick-up operations before starting mounting operations at each work cycle. The number of pickups to fill up the heads depends on which components are picked up at the work cycle. Since each pickup operation requires moving to the pickup position at the feeder slots and access to the feeders, it is essential to minimize the total number of pickup in order to reduce the machine cycle time. We formulate the work cycle formation problem as a set covering problem that has decision variables as many as the number of feasible pickup patterns of a cycle. We solve the integer programming formulation of the problem by a column generation method of which subproblem for column selection is efficiently solvable in a polynomial time graph algorithm.
Third, we consider pickup sequencing problem in multi-head gantry-type ma-chines. The pickup sequencing decision is to allocate the single pickup groups which are picked up simultaneously to heads and determine the sequences in which the components of each work cycle are picked up. The pickup sequencing decision should minimize the the total gantry moving distance in the feeder rack for all work cycles to pick up the components without change in the total number of pickups by work cycle formation. We formulate the problem as a set partitioning problems. Although the formulations have exponentially many variables, we solve the linear programing relaxation of them by using the column generation technique. For solving the pricing problem, we exploit the subproblem structure and present a practical optimal algorithm.
Finally, we consider mounting sequencing problem in multi-head gantry-type machines. The mounting sequencing decision is to determine which mounting lo-cations the gantry visits for component mounting. Though the problem is similar to the vehicle routing problem (VRP), the mounting sequencing problem has many distinct features different from the traditional VRP. Therefore, it requires unique model and algorithm to solve the problem. We first formulate this problem as an integer program, and reformulate this integer problem as a set partitioning problem using Dantzig-Wolfe decomposition. Although the formulations have exponentially many variables, we solve the linear programming relaxation of them by using the column generation technique. For solving the pricing problem, we exploit the sub-problem structure and present special optimal algorithm techniques based on dynamic programming. After solving the linear programming relaxation, we apply the branch-and-price procedure to get an optimal solution. We develop branching rules that exclude the current fractional solution and partition the solution space validly.
본 논문은 복수의 헤드를 갖는 갠트리형 표면실장장비의 효율적 운영에 대해 다룬다. 복수의 헤드를 갖는 갠트리형 표면실장 장비의 최적화 문제들은 매우 복잡하며 상호 강한 상관관계를 가지고 있다. 따라서 각 문제들을 잘 정의하고 적절한 접근방법의 개발이 필요하다. 본 연구에서는 갠트리형 표면실장 장비의 여러가지 의사 결정 문제들을 하위 문제들로 분할하고 각각의 문제에 대해서 개별적으로 모델링하고 각각의 문제에 대한 해법을 제시하였다.
첫번째로, 부품할당과 피더배치 문제를 동시에 고려한 유전자 알고리즘을 제안하였다. 부품할당문제는 PCB 조립을 위해 부품을 어느 장비에 의해 실장될 것인가를 결정하는 문제이고, 피더배치문제는 각 부품의 피더를 피더랙의 슬롯에 어떻게 배치할 것인가를 결정하는 문제이다. 본 연구에서는 이중겐트리 방식의 표면실장장비를 대상으로 부품할당과 피더 배치 문제를 효율적으로 해결하기 위해 적합한 유전개체와 평가함수를 정의하였다. 또한 장비의 사이클 타임을 계산에 필요한 워크사이클 형성과 픽업 시퀀싱을 위하여 그리디 알고리즘을 제안하였다.
두번째로, 워크사이클 형성문제를 위하여 열생성 기법을 이용한 분해모형을 제안하였다. 워크사이클 형성문제는 각 픽업-장착 사이클에 흡착할 부품을 할당하는 것이다. 복수의 헤드를 가지는 표면실장장비에서는 동시픽업이 매우 중요한 요소이므로 전체 픽업수를 최소화 함으로서 장비의 성능을 높일수 있다. 본 연구에서는 분해모형의 부 문제인 열 생성 문제를 해결하기 위해 패턴 생성 그래프를 정의하고 이를 이용하여 Polynomial-Time내에 열 생성 문제의 최적해를 구하는 방법을 제안하였다. 분해모형의 최적해 탐색을 위해 열생성기법과 분지한계법을 결합한 알고리즘을 제안하였다.
세번째로, 픽업시퀀싱 문제를 위하여 정수계획모형을 제시하고 열생성기법과 분지한계법을 이용한 해법을 제시하였다. 픽업시퀀싱 문제는 워크 사이클에 할당된 부품을 픽업하기 위해 한번이상의 픽업수가 필요로 할 때 픽업 순서를 결정하고 각 사이클에 할당된
동시픽업 그룹을 재할당을 통해 사이클 내에서 픽업수를 최소화하고 피더랙에서의 겐트리 이동시간을 최소화하는 것이다. 본 연구에서는 부문제인 열생성 문제를 해결하기 위해 깊이 우선 탐색 알고리즘을 제안하였고 정수해를 얻기 위해 생성된 열에 대해서 분지한계법을 적용하였다.
마지막으로, 장착시퀀싱 문제를 위하여 정수계획모형을 제시하고 열생성 기법과 분지-평가법을 이용한 해법을 제시하였다. 장착시퀀싱 문제는 각 사이클에서 헤드에 장착되어 있는 부품들을 장착 이동 거리를 최소화 하도록 PCB 위의 어느 장착점에 실장할 것인가를 결정하는 것이다. 본 연구에서는 장착시퀀싱 문제를 주문제와 부문제로 나누어 모형화하였고 분문제인 열생성문제를 풀기 위하여 동적계획법을 이용하였다. 또한 적절한한 분지룰의 개발을 통해 분지 평가법을 적용함으로서 최적해를 도출할 수 있었다.
제안된 모든 알고리즘은 실제 현장에서 얻은 데이타에 적용 검증하였다. 실험결과, 빠른 시간내에 최적해 또는 근사 최적해를 구할 수 있었다. 따라서 본 연구에서 제안된 알고리즘을 통해 복수의 헤드를 가지는 갠트리형 표면실장장비의 생산성 향상을 기대할 수 있다.
