[논문]이형 부품 표면실장기에 대한 겐트리 경로 문제의 최적 알고리즘

정재욱; 태현철

doi:10.11627/jkise.2020.43.4.067

이형 부품 표면실장기에 대한 겐트리 경로 문제의 최적 알고리즘
Optimization Algorithm of Gantry Route Problem for Odd-type Surface Mount Device 원문보기

Journal of Korean Society of Industrial and Systems Engineering = 한국산업경영시스템학회지, v.43 no.4, 2020년, pp.67 - 75

정재욱 (연세대학교 산업공학과) , 태현철 (한국생산기술연구원 스마트제조혁신연구부문)

Abstract ▼ AI-Helper

This paper proposes a methodology for gantry route optimization in order to maximize the productivity of a odd-type surface mount device (SMD). A odd-type SMD is a machine that uses a gantry to mount electronic components on the placement point of a printed circuit board (PCB). The gantry needs a nozzle to move its electronic components. There is a suitability between the nozzle and the electronic component, and the mounting speed varies depending on the suitability. When it is difficult for the nozzle to adsorb electronic components, nozzle exchange is performed, and nozzle exchange takes a certain amount of time. The gantry route optimization problem is divided into the mounting order on PCB and the allocation of nozzles and electronic components to the gantry. Nozzle and electronic component allocation minimized the time incurred by nozzle exchange and nozzle-to-electronic component compatibility by using an mixed integer programming method. Sequence of mounting points on PCB minimizes travel time by using the branch-and-price method. Experimental data was made by randomly picking the location of the mounting point on a PCB of 800mm in width and 800mm in length. The number of mounting points is divided into 25, 50, 75, and 100, and experiments are conducted according to the number of types of electronic components, number of nozzle types, and suitability between nozzles and electronic components, respectively. Because the experimental data are random, the calculation time is not constant, but it is confirmed that the gantry route is found within a reasonable time.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

Li et al.[11]eGeneric Algorithm을통해터렛형SMD의피더 배열을 연구하고 제시했다. Ashayeri et al.
본 논문에서는이형부품 data-checked="false">표면실장기에대한겐트리경로문제에대해수리모형을제시하고두단계의방법 을통해최적화해법을제안하였다. 정수혼합법 방법론을 통하여 사이클당 장착할 컴포넌트 조합을 구하였고 B&P 알고리즘을 통하여 컴포넌트조합에 따른 최단 거리경로를구했다.
노즐 및 컴포넌트 할당에 정수혼합법을 사용하고경로순서, PCB 장착순서에대해서휴리스틱알고리즘을사용하였다. 본논문에서는컴포넌트와노즐할당및경로순서, PCB 장착순서를개선하여멀티헤드SMD의PCB 조립 시간을 줄이는 것을 목적으로 하며 총4가지의의사결정요소를다룬다. data-checked="false">본연구에서는이를2단계모형으로분할하여구현하였으며컴포넌트배치를위한정수혼합법과컴포 넌트배치를통한B&P 배치알고리즘을제안한다.
본논문은하나의겐트리(Gantry)와다수의헤드(Head) 를 갖는 SMD의 최적화문제에 집중한다. PCB data-checked="false">위에는전자부품들이장착될빈공간들이존재하고해당공간 에는미리정의된유형의전자부품이장착되어야한다.

가설 설정

3. 최적해가실수라면분기한정법을통하여정수해를구한다.
사이클수최소화, 3. Z축이동 (HC)속도극대화, 4. 이동거리최소화가있다.
4. 최적해가정수라면과정을종료한다.
각각의 데이터는 랜덤 함수를 사용하여 구성하였다. PCB의크기는가로800mm, 세로800mm이며장착점의개수는(25, 50, 75, 100) 4가지 경우의 수를 가정하였고, 컴포넌트의종류는장착점의수12%에서25% 사이의수, 노즐의 종류는 컴포넌트 종류의 50%의 수로가정하였다. HC는최소값1, 최대값4인경우와최소값 1, 최대값8인경우로정의했다.
겐트리는4개의헤드를가지고있으며, 하나의 사이클로 최대 4개의 컴포넌트를 장착할 수 있다. 겐트 리가 SMD 구성요소(PCB 테이블, ANC, 카메라, data-checked="false">피데간이동시걸리는시간과피더에서컴포넌트를흡착하는시간 및카메라에서검사를위해사용하는시간은없는것으로 가정한다. HC는 컴포넌트와 노즐 간 조합에 따른 이동속도를명시한다.
하나의 겐트리가 여러 번의사이클을 통해 data-checked="false">PCB위의장착점을방문하기때문에동일한컴포넌트조합의사이 클은같은차량, 조합이 다른 경우는 다른 차량으로 가정하여 문제를해결한다.

제안 방법

Ayob and Kendall[2]eSMD 최적화에관한연구들을전반적으로정리, 비교, 분석하였다. data-checked="false">이논문eSMD를5가지유형으로분류하여각유형에대한설명과각유형에서 생기는최적화이슈를정리하였고각유형에서SMD 최적화 문제를 해결했었던 논문들을 정리, 요약했다.
[18]은유전알고리즘과그리디알고리즘을사용하여컴포넌트에 대한픽업순서를최적화했으며총조립시간관점에서각 컴포넌트배치순서솔루션의성능을평가하였다. Du and Li[5]eSMD의효율성을최적화하기위해유전알고리즘 과휴리스틱알고리즘을결합한새로운알고리즘을제시 하였으며장착시의총이동거리를평가하였다. Withelm et al.
본논문에서는컴포넌트와노즐할당및경로순서, PCB 장착순서를개선하여멀티헤드SMD의PCB 조립 시간을 줄이는 것을 목적으로 하며 총4가지의의사결정요소를다룬다. data-checked="false">본연구에서는이를2단계모형으로분할하여구현하였으며컴포넌트배치를위한정수혼합법과컴포 넌트배치를통한B&P 배치알고리즘을제안한다. data-checked="false">정수혼합법을통해할당및경로순서를정하고Branch-and- price(B&P) 배치 알고리즘을 통해장착점방문순서를 정한다.
data-checked="false">이논문eSMD를5가지유형으로분류하여각유형에대한설명과각유형에서 생기는최적화이슈를정리하였고각유형에서SMD 최적화 문제를 해결했었던 논문들을 정리, 요약했다. Chen et al.
단 노즐 교환의 경우 많은 시간이 소요된다. data-checked="false">헤드에노즐을끼운후피더로이동하여컴포넌트를흡착하게되며흡착이끝나게되면카메라로 이동하여흡착된컴포넌트검사를한다. 그 이후 PCB 로이동하여지정된장소에 컴포넌트를장착한다.
각각의 데이터는 랜덤 함수를 사용하여 구성하였다. PCB의크기는가로800mm, 세로800mm이며장착점의개수는(25, 50, 75, 100) 4가지 경우의 수를 가정하였고, 컴포넌트의종류는장착점의수12%에서25% 사이의수, 노즐의 종류는 컴포넌트 종류의 50%의 수로가정하였다.
data-checked="false">첫번째단계에서1번의사결정을정수혼합법으로해결함으로써1~3번의주요목표를최적화한다. 두번째단계에서이동거리를최소화하기위해첫번째 단계에서 얻은 정수혼합법의 결과를 바탕으로 한 B&P 알고리즘을구현한다.
기존논문에서는 2단계 PCB 장착순서 결정 문제를 해결할 때 점과 점사 이의거리를Euclidian 방식이아닌Chebyshev 방식으로 계산했다. 본 논문의 점과 점 사이의 거리는 Euclidian 방식이기때문에기존의코드를Euclidian 방식으로 변환하여 실험하였다. <Algorithm 1>에서해당알고리즘을확인할 수 있다.
이에 본 연구는 2단계 모형을 제시하여 사이클 완료시간총합을최소화한다. 문제 각각은 노즐-컴포넌트할당문제, PCB 장착순서문제로부르고, 의사결정은 다음과 같다.
이형SMD에서피더배치, 피더에서 컴포넌트를 픽업하는 순서, 노즐과컴포넌트할당, 컴포넌트장착순서, 경로순서등등전체과정을수리적으로풀기엔불가능 하기때문에본논문에서는몇가지제한사항을둔다. 노즐의종류는1개이상이며동일한종류의노즐은4개 이상있다.
정수혼합법 방법론을 통하여 사이클당 장착할 컴포넌트 조합을 구하였고 B&P 알고리즘을 통하여 컴포넌트조합에 따른 최단 거리경로를구했다. 특히B&P 알고리즘에서 열 생성기법과 Labeling algorithm을 통한 효율적인 풀이를 제안했다.
HC는최소값1, 최대값4인경우와최소값 1, 최대값8인경우로정의했다. 정수혼합법문제와B&P 알고리즘을풀기위해IBM사의소프트웨어CPLEX를활 용하였으며데이터생성코드와정수혼합법문제를해결 하는코드는Python으로제작하였고, B&P 알고리즘 코드는 Microsoft Visual C++로제작되었다. 제작된프로그램은 Intel Core i7-8700 CPU 3.
정수혼합법 방법론을 통하여 사이클당 장착할 컴포넌트 조합을 구하였고 B&P 알고리즘을 통하여 컴포넌트조합에 따른 최단 거리경로를구했다. 특히B&P 알고리즘에서 열 생성기법과 Labeling algorithm을 통한 효율적인 풀이를 제안했다. 문제를해결해본결과컴포넌트의종류, 노즐종류, 장착점의수가많을수록첫번째단계의소요시간이증 가하였고, 두 번째 단계에서는 전체장착점수에 대한 컴포넌트 종류의 수가 적을수록 소요시간이 적게 걸리는 결과를 확인할 수 있었다.

대상 데이터

data-checked="false">이형부품들은크기가커서헤드간간격이넓어야하기에겐트리가보유할 수있는헤드의수가제한되며이형SMD는1개혹은2개 의겐트리를갖고있으며각겐트리는6개이하의헤드를 보유하고있다. 본논문은4개의헤드를가진1개의겐트리를보유한이형SMD을타겟으로한다.

이론/모형

B&P 알고리즘의 성능을 비교하기 위해서 같은 문제상황의Level Placing Algorithm을사용한다[1]. Level Placing AlgorithmeGreedy 방법을기반으로한다. 기존논문에서는 2단계 PCB 장착순서 결정 문제를 해결할 때 점과 점사 이의거리를Euclidian 방식이아닌Chebyshev 방식으로 계산했다.
하지만 이형 부품표면 실장 기에서는겐트리가 어떠한 부품을 장착하고 이동하고 있는지에 따라 이동속도가 달라질 수 있다. data-checked="false">그렇기에추후연구과제로이러한속도차이를고려한이형표면실장기겐트리경로 알고리즘을제시한다.
Level Placing AlgorithmeGreedy 방법을기반으로한다. 기존논문에서는 2단계 PCB 장착순서 결정 문제를 해결할 때 점과 점사 이의거리를Euclidian 방식이아닌Chebyshev 방식으로 계산했다. 본 논문의 점과 점 사이의 거리는 Euclidian 방식이기때문에기존의코드를Euclidian 방식으로 변환하여 실험하였다.
[1] 은계층적방법을통해헤드에노즐및컴포넌트할당과PCB 장착순서를 해결하였고 그 방법을 제시하고 있다. 노즐 및 컴포넌트 할당에 정수혼합법을 사용하고경로순서, PCB 장착순서에대해서휴리스틱알고리즘을사용하였다. 본논문에서는컴포넌트와노즐할당및경로순서, PCB 장착순서를개선하여멀티헤드SMD의PCB 조립 시간을 줄이는 것을 목적으로 하며 총4가지의의사결정요소를다룬다.
노즐-컴포넌트할당문제는MIP모델을만들어CPLEX 를 활용하여해결한다. 정수혼합법모델eAshayeri et al.
하지만본연구에서는근접해를찾는것이아닌 최적해를 찾는다. 방문순서를 정하기 위해서 여러가지 방법이 있지만우리는기존의VRP 문제에서 많이 사용되는 B&P 알고리즘을사용한다. data-checked="false">B&P는선형문제가무수히많eColumn(열)을갖기때문에제한된열을통해 서선형문제의최적해를구할 수 있다.
^는제한된경로에추가하는새로운경로(column)이다. 부문제를해결하기위해아래설명할 Labeling algorithm을시용한다.

성능/효과

×이다. Level Placing Algorithm의경우B&P data-checked="false">알고리즘과비교하여빠른시간내에경로는찾는경향을보이 지만B&P 알고리즘보다평균적으로18% 내외의 좋지 않은 결과를 보이는 것을 확인할 수 있다.
문제를해결해본결과컴포넌트의종류, 노즐종류, 장착점의수가많을수록첫번째단계의소요시간이증 가하였고, 두 번째 단계에서는 전체장착점수에 대한 컴포넌트 종류의 수가 적을수록 소요시간이 적게 걸리는 결과를 확인할 수 있었다. data-checked="false">즉같은수의장착점에대하여계산할때컴포넌트종류의수에따라1단계정수혼합법 방법론과 2단계 B&P 방법론의 소요시간이 반비례한다는 경향을 보이는 것을 알 수 있다. 본논문에서제시한 B&P을사용한방법론은컴포넌트와노즐할당, 장착순서를 고려한 이형 부품 표면실장기 문제에서 data-checked="false">처음으로제시되는최적화해법으로휴리스틱알고리즘을이용하 여해결하는방법론의비교평가대상이될수있다는 것에의미가있다.
특히B&P 알고리즘에서 열 생성기법과 Labeling algorithm을 통한 효율적인 풀이를 제안했다. 문제를해결해본결과컴포넌트의종류, 노즐종류, 장착점의수가많을수록첫번째단계의소요시간이증 가하였고, 두 번째 단계에서는 전체장착점수에 대한 컴포넌트 종류의 수가 적을수록 소요시간이 적게 걸리는 결과를 확인할 수 있었다. data-checked="false">즉같은수의장착점에대하여계산할때컴포넌트종류의수에따라1단계정수혼합법 방법론과 2단계 B&P 방법론의 소요시간이 반비례한다는 경향을 보이는 것을 알 수 있다.

참고문헌 (22)

Ashayeri, J., Ma, N., and Sotirov, R., An aggregated optimization model for multi-head SMD placements, Computer & Industrial Engineering, 2011, Vol. 60, No. 1, pp. 99-105.

상세보기
Ayob, M. and Kendall, G., A survey of surface mount device placement machine optimization : Machine classification, European Journal of Operational Research, 2008, Vol. 186, No. 3, pp. 893-914.

상세보기
Bentzen, B., SMD Placement, in the SMT in FOCUS, http://www.Smtinfocus.com/PDF/SMD_placement.Pdf.
Chen, T., Luo, J., and Hu, Y., Component placement process optimization for multi-head surface mounting machine based on tabu search and improved shuffled frog-leaping algorithm, IEEE Intelligent Systems and Applications (ISA), 2011, Wuhan, China, pp. 1-4.
Du, X. and Li, Z., Placement process optimization of dual-gantry turret placement machine, IEEE/ASME International Conference on Advanced Intelligent Mechatronics, 2008, Xian, China, pp. 1266-1271.
Hardas, C.S., Doolen, T.L., and Jensen, D.H., Development of a genetic algorithm for component placement sequence optimization in printed circuit board assembly, Computers & Industrial Engineering, 2008, Vol. 55, No. 1, pp. 165-182.

상세보기
Jeevan et al., Optimization of PCB component placement using genetic algorithms, Journal of Electronics Manufacturing, 2002, Vol. 11, No. 1, pp. 69-79.

상세보기
Jiang, J., Chen, X., Zang, M., Wang, Z., and Tan, Z., Optimization of the surface mount technology based on the max-min ant system, 2nd International Conference on Future Computer and Communication(ICFCC), 2010, Wuha, China, pp. 45-47.
Kim, J.Y., Pick up and delivery vehicle routing problem under time window using single hub, Journal of Society of Korea Industrial and Systems Engineering, 2019, Vol. 42, No. 4, pp. 16-22.

원문보기 상세보기
Lee, S.H., Lee, B.H., and Park, T.H., A hierarchical method to improve the productivity of a multi-head surface mounting machines, Intelligent Automation and Soft Computing, 2000, Vol. 6, No. 4, pp. 291-301.

상세보기
Li, S.Y., Hu, C.F., and Tian, F.H., Enhancing optimal feeder assignment of the multi-head surface mounting machine using genetic algorithms, Applied Soft Computing, 2008, Vol. 8, No. 1, pp. 522-529.

상세보기
Lin, C.-J. and Huang, M.-L., Modified artificial bee colony algorithm for scheduling optimization for printed circuit board production, Journal of Manufacturing Systems, 2017, Vol. 44, No. 1, pp. 1-11.

상세보기
Loh, T.S., Bukkapatnam, S., Medeiros, D., and Kwon, H., A genetic algorithm for sequential part assignment for PCB assembly, Computer and Industrial Engineering, 2001, Vol. 40, No. 4, pp. 293-307.

상세보기
Magyar, G., Johnsson, M., and Nevalainen, O., On solving single machine optimization problems in electronics assembly, Journal of Electronics Manufacturing, 1999, Vol. 9, No. 4, pp. 249-267.

상세보기
McGinnis et al., Automated process planning for printed circuit card assembly, IIE Transactions, 1992, Vol. 24, No. 4, pp. 18-30.

상세보기
Moyer, L.K. and Gupta, S.M., An efficient assembly sequencing heuristic for printed circuit board configurations, Journal of Electronics Manufacturing, 1997, Vol. 7, No. 2, pp. 143-160.

상세보기
Son, D.H. and Kim, H.J., Heuristic for Rich Vehicle Routing Problem : A Case of a Korean Mixed Feed Company, Journal of Society of Korea Industrial and Systems Engineering, 2019, Vol. 42, No. 1, pp. 8-20.
Sun, D.S., Lee, T.E., and Kim, K.H., Component allocation and feeder arrangement for a dual-gantry multi-head surface mounting placement tool, International Journal of Production Economics, 2005, Vol. 95, No. 2, pp. 245-264.

상세보기
Tirpak, T.M., Design-to-manufacturing information management for electronics assembly, International Journal of Flexible Manufacturing Systems, 2000, Vol. 12, pp. 189-205.

상세보기
Torabi, S.A., Hamedi, M., and Ashayeri, J., A new optimization approach for nozzle selection and component allocation in multi-head beam-type SMD placement machines, Journal of Manufacturing Systems, 2013, Vol. 32, No. 4, pp. 700-714.

상세보기
Wilhelm, W.E., Choudhry, N.D., and Damodaran, P., A model to optimize placement operations on dual-head placement machines, Discrete Optimization, 2007, Vol. 4, No. 2, pp. 232-256

상세보기
Zhu, G.Y. and Zhang, W.B., An improved Shuffled Frog-leaping Algorithm to optimize component pick-andplace sequencing optimization problem, Expert Systems with Applications, 2014, Vol. 41, No. 15, pp. 6818-6829.

상세보기

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증