1. 서 론

표면실장기술(Surface Mount Technology; SMT)은 납 인쇄 (Solder Paste), 전자부품장착(Electronic Component Placement), 납땜(Solder Reflow) 과정을 통해 인쇄회로기판 (Printed Circuit Board; PCB)을 생산하는 기술이다[19]. 최 근 급증하는 PCB 생산 수요에 대응하기 위해 SMT 제조 라인의 전 과정은 고도로 자동화된 설비들에 의해 진행된 다[22]. SMT 제조 라인의 주된 병목은 전자부품장착 과정 에서 발생하기에 많은 이전 연구들[6, 20]은 이 과정을 처 리하는 표면실장기(Surface Mount Device; SMD)의 생산성 향상 문제에 집중하였다.

기계 구조와 활용 목적에 따라 SMD를 분류하는 기준 은 여러 연구자들[3, 7, 14, 15, 16]에 의해 제안되었다. Wilhelm et al.[21]은 SMD가 장착하는 부품의 특성에 따라 일반형 SMD와 이형 SMD로 분류하는 기준을 제안하였다. 이 기준법에 따르면 모양이 단순하고 무게가 가볍고 크기 가 작은 일반적인 형태의 전자부품들의 장착에 전문화된 SMD를 일반형 SMD라 하며 모양이 복잡하고 무게가 무 겁고 크기가 큰 일반적인 형태의 부품과는 다른 특이 형태 의 부품들의 장착에 전문화된 SMD를 이형 SMD라 한다.

일반형 SMD는 상대적으로 많은 수(150개 이상)의 일반 형 전자 부품들을 빠르게 장착하는 목적으로 사용되기에 2개 혹은 4개의 겐트리를 갖고 있으며 각 겐트리는 16개 이상의 다수의 헤드를 보유하고 있다. 이형 SMD는 모양이 복잡하고 무게가 무겁고 크기가 큰 일반적인 형태의 부품 과는 다른 특이 형태의 부품들의 장착에 전문화된 SMD로 상대적으로 적은 수(100개 이하)의 이형 전자 부품들을 정 확하게 장착하는 목적으로 사용된다. 이형 부품들은 크기 가 커서 헤드 간 간격이 넓어야 하기에 겐트리가 보유할 수 있는 헤드의 수가 제한되며 이형 SMD는 1개 혹은 2개 의 겐트리를 갖고 있으며 각 겐트리는 6개 이하의 헤드를 보유하고 있다. 본 논문은 4개의 헤드를 가진 1개의 겐트리 를 보유한 이형 SMD을 타겟으로 한다.

본 논문은 하나의 겐트리(Gantry)와 다수의 헤드(Head) 를 갖는 SMD의 최적화 문제에 집중한다. PCB 위에는 전자 부품들이 장착될 빈 공간들이 존재하고 해당 공간 에는 미리 정의된 유형의 전자 부품이 장착되어야 한다. 이러한 빈 공간을 장착점(placement)이라 부르고 장착되 어야 할 전자 부품들을 컴포넌트(component)라 부른다. SMD의 전체적인 구조는 <Figure 1>에 설명되어 있다.

피더(Feeder)는 SMD에 컴포넌트를 공급하는 장비이다. 하나의 피더는 하나의 컴포넌트를 공급하며 모든 피더는 각자 다른 종류의 컴포넌트를 공급한다. 카메라는 겐트리 에 흡착된 컴포넌트를 검사하는 용도로 사용된다. 겐트리 (Gantry)는 x, y, z축으로 움직이며 겐트리에는 컴포넌트 를 흡착 할 수 있는 헤드(Head)가 있다. 헤드가 어떤 컴포 넌트를 흡착하기 위해서는 노즐(Nozzle)을 장착해야 한다. 헤드는 노즐을 통해 공기를 흡입하는 방식으로 컴포넌트 를 흡착하기에 컴포넌트의 모양과 크기에 따라 적합한 노 즐을 장착 할 시 속도상의 장점이 있다. 이것을 노즐과 컴포 넌트 각각의 조합에 따른 적합도, 효율도를 나타내는 지 표인 Handling Class(HC) 라고 정의한다. 만약 헤드가 장착 중인 노즐이 흡착하려는 컴포넌트와 적합하지 않을 경우 겐트리는ANC(Auto Nozzle Changer)로이동하여 헤드의 노즐 을 새로운 적합한 노즐로 교환(Nozzle Change)을 할 수 있 다. ANC는 여러 가지 노즐 종류가 있는 컨테이너로써 겐 트리의 헤드에 끼우는 노즐을 교환할 수 있는 장소이다.

SMD에서 겐트리의 구동 방식은 다음과 같다. 겐트리 의 헤드에 컴포넌트를 흡착하기 위한 노즐이 끼워져 있지 않거나 노즐이 컴포넌트를 흡착하기 어려운 경우에 ANC 에서 노즐을 교환하게 된다. 단 노즐 교환의 경우 많은 시 간이 소요된다. 헤드에 노즐을 끼운 후 피더로 이동하여 컴포넌트를 흡착하게 되며 흡착이 끝나게 되면 카메라로 이동하여 흡착된 컴포넌트 검사를 한다. 그 이후 PCB로 이동하여 지정된 장소에 컴포넌트를 장착한다. 피더에서 컴포넌트를 흡착하는 것에서부터 이를 장착점에 장착하 는 것까지 겐트리의 순차 작동을 사이클(Cycle)이라고 한 다. 겐트리는 사이클을 달성함으로써 방문한 지점 수가 겐트리의 헤드 수보다 작거나 같은 일부 장착점을 방문할 수 있다. 일련의 사이클을 달성함으로써 겐트리는 PCB의 모든 장착점을 방문할 수 있다. 이 일련의 사이클을 계획 이라고 하며 PCB의 경우, 수많은 다양한 계획이 존재한 다. 각 계획은 자체적인 완료 시간을 갖게 되고 하나의 사 이클을 최소 시간으로 완료할 수 있는 계획을 찾는 데 중 점을 둔다. 노즐 교환과 HC, 사이클 수, PCB 장착 순서에 의해 사이클 시간은 최소화 된다.

SMD 문제는 피더 배치, 피더에서 컴포넌트를 픽업하는 순서, 노즐과 컴포넌트 할당, 컴포넌트 장착 순서, 경로 순 서 등등 여러 가지 문제가 결합된 복잡한 문제이다[12]. 최근 SMD 연구는 전체 문제를 분할하여 근사적으로 해결 하는 기법들이 사용되고 있다.

Ayob and Kendall[2]은 SMD 최적화에 관한 연구들을 전반적으로 정리, 비교, 분석하였다. 이 논문은 SMD를 5가 지 유형으로 분류하여 각 유형에 대한 설명과 각 유형에서 생기는 최적화 이슈를 정리하였고 각 유형에서 SMD 최적 화 문제를 해결했었던 논문들을 정리, 요약했다. Chen et al. [4]은 피더 배치와 피더에서 컴포넌트를 픽업하는 순서를 연구했으며 shuffled frog-leaping 알고리즘과 타부 서치를 통해 장착 순서에 대한 최적해를 얻었다. Sun et al.[18]은 유전 알고리즘과 그리디 알고리즘을 사용하여 컴포넌트에 대한 픽업 순서를 최적화 했으며 총 조립 시간 관점에서 각 컴포넌트 배치 순서 솔루션의 성능을 평가 하였다. Du and Li[5]은 SMD의 효율성을 최적화하기 위해 유전 알고리즘 과 휴리스틱 알고리즘을 결합한 새로운 알고리즘을 제시 하였으며 장착시의 총 이동거리를 평가하였다. Wilhelm et al. [21]은 2개 헤드에 대한 컴포넌트 픽업 순서문제를 흡착 시간만을 고려하여 주 문제와 부문제로 나눠 사이클 생성 최적해를 구하였다. Jiang et al.[8]은 컴포넌트 할당과 장착 순서 문제에 집중하였으며 전체 컴포넌트 장착 속도를 높 이기 위해서 TSP와 구성 요소 배치 순서 문제를 해결하기 위한 MAX-MIN Ant System을 제안하였다. Loh et al.[13] 은 유전 알고리즘에 의한 컴포넌트 할당 및 장착 순서를 해결하는 방법을 제안하였다. Tirpak[19]은 SMT line의 프 로세스 흐름을 크게 Front End와 Back End 두 부분으로 나누어 각각의 세부과정을 정리하여 제시하였다. 이 논문 에서 SMT line의 병목 현상(Bottle neck)이 기계수가 제한 되어 있는 Front End(SMD가 PCB에 부품을 조립하는 과 정)에서 일어난다고 밝혔다. Lee et al.[10]은 멀티 헤드 SMD에서 피더 배열을 동적 프로그래밍을 통해 해결한 모 델을 제시하고 시간을 단축하는 방법에 대해서 정리했다. Li et al.[11]은 Generic Algorithm을 통해 터렛형 SMD의 피더 배열을 연구하고 제시했다. Ashayeri et al.[1]은 계층 적 방법을 통해 헤드에 노즐 및 컴포넌트 할당과 PCB 장 착 순서를 해결하였고 그 방법을 제시하고 있다. 노즐 및 컴포넌트 할당에 정수혼합법을 사용하고 경로 순서, PCB 장착 순서에 대해서 휴리스틱 알고리즘을 사용하였다.

본 논문에서는 컴포넌트와 노즐 할당 및 경로 순서, PCB 장착 순서를 개선하여 멀티 헤드 SMD의 PCB 조립 시간 을 줄이는 것을 목적으로 하며 총 4가지의 의사결정 요소 를 다룬다. 본 연구에서는 이를 2단계 모형으로 분할하여 구현 하였으며 컴포넌트 배치를 위한 정수혼합법과 컴포 넌트 배치를 통한 B&P 배치 알고리즘을 제안한다. 정수 혼합법을 통해 할당 및 경로 순서를 정하고 Branch-andprice( B&P) 배치 알고리즘을 통해 장착점 방문 순서를 정 한다. 이 두 단계의 문제 해결방법은 빠른 시간 내에 해결 되는 솔루션을 보장한다.

논문은 다음과 같이 구성되어 있다. 제 2장은 SMD 문 제의 세부사항을 설명한다. 제 3장은 실험 결과에 대한 설명을 하고 제 5장에 논문에 대한 결론을 짓는다.

2. 문제 설명

이형 SMD에서 피더 배치, 피더에서 컴포넌트를 픽업 하는 순서, 노즐과 컴포넌트 할당, 컴포넌트 장착 순서, 경로 순서 등등 전체 과정을 수리적으로 풀기엔 불가능 하기 때문에 본 논문에서는 몇 가지 제한사항을 둔다.

노즐의 종류는 1개 이상이며 동일한 종류의 노즐은 4개 이상 있다. 하나의 노즐은 모든 종류의 컴포넌트를 흡착할 수 있다. 겐트리는 4개의 헤드를 가지고 있으며, 하나의 사이클로 최대 4개의 컴포넌트를 장착할 수 있다. 겐트리 가 SMD 구성 요소(PCB 테이블, ANC, 카메라, 피더)간 이 동 시 걸리는 시간과 피더에서 컴포넌트를 흡착하는 시간 및 카메라에서 검사를 위해 사용하는 시간은 없는 것으로 가정한다. HC는 컴포넌트와 노즐간 조합에 따른 이동속도 를 명시한다. 특정 컴포넌트는 특정 노즐과 조합이 좋거나 나쁠 수 있다. 이는 HC로 표현되는데 조합이 좋은 경우 HC는 낮은 값을 갖게 된다. HC가 낮을 경우 해당 컴포넌 트를 장착하기 위해 z축으로 이동할 때 속도가 빠르고, 반 대의 경우는 속도가 느리다. 겐트리의 각각의 헤드는 개별 HC를 갖게 되는데 이러한 경우 겐트리의 HC는 가장 높은 HC로 정의한다. 이러한 제약에서 기존 SMD의 구조를 간 략하게 도식화하면 <Figure 2>와 같으며 겐트리가 피더 (ANC, 카메라)를 거쳐 PCB위의 장착점에 컴포넌트를 장 착하는 것까지를 사이클로 본다.

이에 본 연구는 2단계 모형을 제시하여 사이클 완료 시 간 총합을 최소화 한다. 문제 각각은 노즐-컴포넌트 할당 문제, PCB 장착 순서 문제로 부르고, 의사결정은 다음과 같다. 첫째로 각 사이클에서 어떠한 노즐로 어떠한 컴포넌 트를 흡착하여 이동할지 결정하고 두 번째로 각 사이클에 서 PCB에 흡착한 컴포넌트를 장착할 때 어떠한 순서로 장 착할지 결정한다. 두 가지의 의사결정을 하는 목적은 1. 노즐 교환 횟수 최소화, 2. 사이클 수 최소화, 3. Z축 이동 (HC)속도 극대화, 4. 이동거리 최소화가 있다.

위의 4가지 목적을 달성하기 위해 우리는 계층적 절차 를 제안한다. 첫 번째 단계에서 1번 의사결정을 정수혼합 법으로 해결함으로써 1~3번의 주요 목표를 최적화 한다. 두 번째 단계에서 이동거리를 최소화하기 위해 첫 번째 단계에서 얻은 정수혼합법의 결과를 바탕으로 한 B&P 알고리즘을 구현한다.

본 연구에서 제시하는 알고리즘은 2단계로 분리되었 기 때문에 전역 최적성은 해치지만 계산시간의 이점이 존재한다. 반복되는 작업에서 노즐 교환 횟수와 z축 이 동 속도를 높임으로써 생산 처리 시간을 가장 크게 단축 할 수 있다. 첫 세 가지 목표는 서로 매우 밀접하게 연관 되어 있다. 노즐 선택은 HC와 노즐 교환 횟수를 결정한 다. 이동 거리를 최소화하는 것을 제외하면 컴포넌트 및 노즐 선택에 기초한 정수혼합법 조성이 가능해져 복잡성 이 감소한다. 정수혼합법을 통해 도출되는 정보에는 특 정 컴포넌트의 배치 순서는 정해지지 않는다. 즉 1~3번 목적을 위해 도출한 결과와 4번 목적을 위해 수행되는 B&P 알고리즘은 완전하지는 않지만 독립적이라고 볼 수 있다. 1~3번은 노즐과 컴포넌트 할당, Z축 속도 조절, 4 번은 (x, y)축 이동 거리기 때문이다. 그렇기 때문에 2단 계 알고리즘을 통해 문제 해결 시간을 유의미하게 줄일 수 있다.

2.1 노즐-컴포넌트 할당 문제

노즐-컴포넌트 할당 문제는 MIP모델을 만들어 CPLEX 를 활용하여 해결한다. 정수혼합법 모델은 Ashayeri et al. [1]의 논문의 것을 사용한다. 배치는 특정 헤드에 의해 PCB에 장착되어야 하는 동일한 컴포넌트의 집합으로 정 의되며 배치 레벨은 컴포넌트의 종류 수 +1보다 클 수 없다.

정수혼합법 모델의 입력 데이터 특정 컴포넌트의 총 개수 리스트, 노즐과 컴포넌트와의 조합에 따른 HC 테이블이 있다. 정수혼합법 모델은 입력된 데이터를 바탕으로 사이클 별 노즐과 컴포넌트와의 조합을 도 출한다.

다음은 모델에 사용되는 매개변수들이다.

아래는 모델에 사용되는 결정변수이다.

아래는 모델의 목적식과 제한조건이다.

목적식 (1)은 헤드간 작업 부하 균형, 노즐 교환 횟수, Z축 이동 시간 최소화를 목적으로 한다. 헤드간 작업 부하 균형이 일정하다면 만들어진 사이클 횟수는 최소값이라고 볼 수 있다. 제약조건 (2)는 PCB위 장착되는 모든 컴포넌 트의 합은 입력된 컴포넌트의 수와 같음을 보장한다. 제약 조건 (3)은 헤드의 가장 큰 작업이 무엇인지 계산한다. 제 약조건 (4)는 입력된 컴포넌트는 PCB위에 장착할 장소가 있음을 보장한다. 제약조건 (5)는 하나의 할당된 컴포넌트 는 PCB위의 한 점에만 장착됨을 의미한다. 제약조건 (6) 은 배치 할 컴포넌트가 없는 경우 PCB위의 장착점도 존재 하지 않음을 보장한다. 제약조건 (7)은 컴포넌트의 할당이 높은 배치 레벨에 할당되기 이전에 낮은 배치 레벨에 할당 됨을 보장한다. 제약조건 (8)은 PCB위의 장착점은 최대 하나의 컴포넌트만 장착 가능함을 의미한다. 제약조건 (9)는 노즐 교환이 있는 경우를 계산한다. 제약조건 (9)의 경우 는 절대값이 존재하여 아래와 같이 식을 바꾸어 계산한다.

제약조건 (10)은 제약조건 (9)에서 계산된 마지막 배치 레벨의 경우(0.5)를 제외한다. 제약조건 (11)은 배치 레벨 에서 가장 높은 HC를 계산한다.

2.2 PCB 장착 순서 문제

1단계에서 컴포넌트의 조합을 얻었다면 2단계에서는 PCB위 장착점들의 방문 순서를 정한다. SMD의 생산성 향상을 위한 방문 순서를 정하는 최적화 문제는 일종의 차량 경로 문제(Vehicle Routing Problem; VRP)로 매우 복잡한(NP-hardness) 문제이다[9, 17]. 그렇기 때문에 기 존 문헌에서는 휴리스틱 알고리즘을 사용하여 근사해를 찾는다. 하지만 본 연구에서는 근접해를 찾는 것이 아닌 최적해를 찾는다. 방문 순서를 정하기 위해서 여러가지 방법이 있지만 우리는 기존의 VRP 문제에서 많이 사용 되는 B&P 알고리즘을 사용한다. B&P는 선형 문제가 무 수히 많은 Column(열)을 갖기 때문에 제한된 열을 통해 서 선형 문제의 최적해를 구할 수 있다. B&P은 선형 문 제의 최적해를 Master problem(주 문제)와 Sub problem (부 문제)으로 나누어 해결한다. 주 문제는 현재 알고 있 는 제한된 수의 열을 통해 최적해와 dual reward(쌍대 비 용)을 구하고 부 문제는 주 문제가 개선될 여지가 있는 열을 찾아 추가한다.

2.2.1 주 문제

하나의 겐트리가 여러 번의 사이클을 통해 PCB위의 장착점을 방문하기 때문에 동일한 컴포넌트 조합의 사이 클은 같은 차량, 조합이 다른 경우는 다른 차량으로 가정 하여 문제를 해결한다.

아래는 주 문제에 사용되는 매개변수이다.

아래는 주 문제에 사용되는 결정변수이다.

아래는 주 문제의 목적식과 제약조건이다.

목적식 (15)는 차량에 의해 이동되는 모든 경로 비용의 최소값을 갖는 경로를 구한다. 제약조건 (16)은 모든 장착 점은 한번 방문해야 한다는 것을 의미한다. 제약조건 (17) 은 차량 타입 대수 제한 조건으로 차량 타입 m의 개수 이상의 차량이 사용되는 것을 방지한다.

2.2.2 부 문제(Pricing problem)

겐트리 경로 문제에서 부 문제는 주 문제를 푼 후에 해 결한다. π_i는 방문하는 노드의 쌍대 비용 값, f_m는 차량의 쌍대 비용값으로 정의한다. net reward(순수비용)는 c_m,r - π_n - f_m로 표현된다. 아래의 식은 차량 n으로 이동하는 경 로 r에 대한 모든 쌍대 비용을 더한 값으로 정의하며 최단 경로를 찾아내는 식으로 정의한다. r^*는 제한된 경로 R ˜ 에 추가하는 새로운 경로(column)이다. 부 문제를 해결하기 위해 아래 설명할 Labeling algorithm을 시용한다.

2.2.3 Labeling Algorithm

우리는 label(라벨) s를 (n, q, capa, E) 로 정의한다. n,q 는 각각 현재 위치하는 노드, 순수비용을 의미한다. capa 는 차량의 종류에 따라 차량이 이동 할 수 있는 장착점으 로 정의한다. 장착점 n에 장착되어야 할 컴포넌트를 type_n 이라 정의한다. c a p a = ( C a p a 1 , C a p a 2 ⋯ , C a p a | J | ) 는 정수 로 이루어진 벡터이며 방문할 수 있는 Capa_j는 노즐-컴포 넌트 할당 문제 해결 시에 인풋 데이터로 입력된다. E = ( E 1 , E 2 ⋯ , E | I | ) 는 이진 변수로 이루어진 벡터로써 방문한 장착점의 상태이다. 만약 해당 차량이 E_i 를 방문했으면 1 아니면 0이다. 장착점 n에서 장착점 n′으로 확장되기 위해 서 (s = (n, q, capa, E) 에서 s′ = (n′, q′, capa′, E′)로) 다음과 같은 제약이 존재한다.

제약조건 (20)은 방문하지 않은 장착점일 경우에만 확 장이 가능한 조건이고 제약조건 (21)은 겐트리가 방문할 수 있는 장착점일 경우에만 확장이 가능한 조건이다. 두 조건을 만족했을 때 확장은 다음과 같다.

식 (22)는 확장된 순수비용 q′는 기존의 순수비용 q와 확장하는 순수비용 q n ′ 의 합을 나타내며 식 (23)과 식 (24) 는 방문할 수 있는 장착점의 업데이트를 의미한다. 식(25) 는 방문한 장착점을 업데이트 해준다. 하나의 라벨보다 더 결과가 좋지 않은 라벨은 도태되어야 한다. 방문한 장착점 의 수가 더 많거나 같고, 방문할 수 있는 장착점의 종류와 수가 작거나 같을 때 순수비용이 작거나 같으면 라벨을 도태시킨다. s″ = (n″, q″, capa″, E ″ )수식은 다음과 같다.

2.2.4 Proposed B&P Procedure

Labeling algorithm을 통한 열 생성 기법은 겐트리 경로 문제에서 최적해를 찾을 수 있다. 음의 상대 비용 값을 가진 어떠한 열도 주 문제를 개선시킬 수 있다. 그렇기 때문에 주 문제를 풀고 개선할 열을 찾는 과정을 반복한다. 개선 할 수 있는 모든 열을 찾고 최적해를 구할 때 최적해가 정수가 아닐 경우에는 Branch and Bound(분기한정법)을 통하여 정수해를 구한다. 문제 해결 순서는 다음과 같다.

3. 실험 결과

제안한 방법론의 성능을 알아보기 위해 가상의 데이터 를 만들었다. 각각의 데이터는 랜덤 함수를 사용하여 구 성하였다. PCB의 크기는 가로 800mm, 세로 800mm이며 장착점의 개수는 (25, 50, 75, 100) 4가지 경우의 수를 가 정하였고, 컴포넌트의 종류는 장착점의 수 12%에서 25% 사이의 수, 노즐의 종류는 컴포넌트 종류의 50%의 수로 가정하였다. HC는 최소값 1, 최대값 4인 경우와 최소값 1, 최대값 8인 경우로 정의했다. 정수혼합법 문제와 B&P 알고리즘을 풀기 위해 IBM사의 소프트웨어 CPLEX를 활 용하였으며 데이터 생성 코드와 정수혼합법 문제를 해결 하는 코드는 Python으로 제작하였고, B&P 알고리즘 코드 는 Microsoft Visual C++로 제작되었다. 제작된 프로그램은 Intel Core i7-8700 CPU 3.20GHz, 메모리 8GB, Windows 10 환경에서 실행되었다. 장착점의 위치데이터와 컴포넌트 종류는 랜덤하게 뽑았기 때문에 5번의 실험을 하여 평균 을 냈다. B&P 알고리즘의 성능을 비교하기 위해서 같은 문제 상황의 Level Placing Algorithm을 사용한다[1]. Level Placing Algorithm은 Greedy 방법을 기반으로 한다. 기존 논문에서는 2단계 PCB 장착 순서 결정 문제를 해결할 때 점과 점사이의 거리를 Euclidian 방식이 아닌 Chebyshev 방식으로 계산했다. 본 논문의 점과 점 사이의 거리는 Euclidian 방식이기 때문에 기존의 코드를 Euclidian 방식 으로 변환하여 실험하였다. <Algorithm 1>에서 해당 알고 리즘을 확인할 수 있다. <Table 2>는 구성된 데이터의 장 착점의 수, 컴포넌트 종류의 수, 노즐 종류의 수, HC의 최 대값 및 최소값을 나타낸 표이다. <Table 3>은 <Table 2> 의 데이터를 사용한 결과 값이다. 각 데이터 셋에 대하여 정수혼합법을 통해 풀어진 시간과 B&P 알고리즘을 사용 하여 푼 시간 및 총 이동거리의 평균값과 최대값, 최소값 을 나타낸다. Case 13~Case 16에서 보는 바와 같이 장착 점 수가 큰 경우도 컴포넌트 종류 수에 따라 합리전인 시 간 내에 해결이 가능하다는 것을 보인다. Case 1~4, 5~8, 9~12, 13~16에서 장착점 수와 컴포넌트 종류가 증가함에 따라 정수혼합법에 걸리는 시간은 증가하지만 그에 따라 B&P 알고리즘의 계산시간은 적어지는 것을 확인할 수 있다. <Table 4>는 Level Placing Algorithm과 B&P 알고리즘과 의 차이를 나타낸 결과값이다. 1단계 실험결과는 같은 수리 모형을 사용했기에 제외하였다. 모든 실험 결과는 5번의 랜덤 데이터를 사용한 평균값이다. Level Placing Algorithm의 평균 총 이동거리를 α라고 하고 B&P의 평균 총 이동거리를 β라고 정의하면 Total Distance Gap = α − β α × 100 이다. Level Placing Algorithm의 경우 B&P 알고리 즘과 비교하여 빠른 시간 내에 경로는 찾는 경향을 보이 지만 B&P 알고리즘 보다 평균적으로 18% 내외의 좋지 않은 결과를 보이는 것을 확인할 수 있다.

4. 결 론

본 논문에서는 이형 부품 표면실장기에 대한 겐트리 경로 문제에 대해 수리모형을 제시하고 두 단계의 방법 을 통해 최적화 해법을 제안하였다. 정수혼합법 방법론 을 통하여 사이클당 장착할 컴포넌트 조합을 구하였고 B&P 알고리즘을 통하여 컴포넌트 조합에 따른 최단 거 리 경로를 구했다. 특히 B&P 알고리즘에서 열 생성 기 법과 Labeling algorithm을 통한 효율적인 풀이를 제안했 다. 문제를 해결해본 결과 컴포넌트의 종류, 노즐 종류, 장착점의 수가 많을수록 첫 번째 단계의 소요시간이 증 가하였고, 두 번째 단계에서는 전체 장착점 수에 대한 컴 포넌트 종류의 수가 적을수록 소요시간이 적게 걸리는 결과를 확인할 수 있었다. 즉 같은 수의 장착점에 대하여 계산할 때 컴포넌트 종류의 수에 따라 1단계 정수혼합법 방법론과 2단계 B&P 방법론의 소요시간이 반비례한다 는 경향을 보이는 것을 알 수 있다. 본 논문에서 제시한 B&P을 사용한 방법론은 컴포넌트와 노즐 할당, 장착 순 서를 고려한 이형 부품 표면실장기 문제에서 처음으로 제시되는 최적화 해법으로 휴리스틱 알고리즘을 이용하 여 해결하는 방법론의 비교 평가 대상이 될 수 있다는 것에 의미가 있다. 이 연구에서 겐트리의 속도는 겐트리 가 어떤 부품을 장착하고 이동하고 있는지 상관하지 않 고 일정하다. 하지만 이형 부품 표면실장기에서는 겐트 리가 어떠한 부품을 장착하고 이동하고 있는지에 따라 이동속도가 달라질 수 있다. 그렇기에 추후 연구과제로 이러한 속도차이를 고려한 이형 표면실장기 겐트리 경로 알고리즘을 제시한다.