[논문]0-1 혼합정수계획법을 이용한 LCD 패널 절단 문제 최적화

김기동; 박현지; 심윤섭; 전태보

doi:10.5369/jsst.2017.26.4.274

0-1 혼합정수계획법을 이용한 LCD 패널 절단 문제 최적화
Optimization of LCD Panel Cutting Problem Using 0-1 Mixed Integer Programming 원문보기

Journal of sensor science and technology = 센서학회지, v.26 no.4, 2017년, pp.274 - 279

김기동 (강원대학교 시스템경영공학과) , 박현지 (강원대학교 시스템경영공학과) , 심윤섭 (쓰리뷰 개발팀) , 전태보 (강원대학교 시스템경영공학과)

Abstract ▼ AI-Helper

LCD(Liquid Crystal Display) panel cutting problem is a sort of two dimensional cutting stock problem. A cutting stock problem is problem that it minimizes the loss of the stock when a stock is cut into various parts. In the most research of the two dimensional cutting stock problem, it is supposed that the relative angle of a stock and parts is not important. Usually the angle is regarded as horizontal or perpendicular. In the manufacturing of polarizing film of LCD, the relative angle should be maintained at some specific angle because of the physical and/or chemical characteristics of raw material. We propose a mathematical model for solving this problem, a two-dimensional non-Guillotine cutting stock problem that is restricted by an arranged angle. Some example problems are solved by the C++ program using ILOG CPLEX classes. We could get the verification and validation of the suggested model based on the solutions.

주제어

AI 본문요약
AI-Helper

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

문제 정의

때문에 제조 공정 개선을 통한 원가 절감이 시급한 실정이며 LCD 및 LED 생산 중 가장 많은 비용을 차지하는 부품소재인 편광 필름의 원가를 원단의 손실을 최소화하는 목형 설계를 통해 낮추어야 한다. LCD 패널 절단용 목형 설계 문제는 자재의 사용면적을 최대화하면서 사각형 형상의 다양한 크기의 부품을 배치하는 최적화 문제에 대한 연구이다.
본 연구에서 다루고자 하는 문제는 현재 수요가 급증하는 LCD 및 LED 제조에 있어서 핵심 부품인 편광 필름 재단을 위한 목형 설계와 관련된 문제이다. 전 세계적으로 빠르게 성장하는 각종 디스플레이 산업에서 우리나라를 추격하는 국가들과의 경쟁에서 우위를 유지하기 위해서는 품질과 더불어 가격 경쟁력 또한 중요한 요소이다.
본 연구에서는 LCD패널 절단 최적화를 위한 수리 모형을 제시하였다. 실제 사례를 풀이함으로써 수리모형의 타당성을 증명하였고, Beasley 모형과의 복잡성 비교를 수행하여 본 연구에서 제시한 수리모형이 보다 범용적이고 복잡성은 동일함을 보였다.
근래의 NGCSP의 풀이는 대부분 자재와 평행한 부품의 각도를 유지하면서 휴리스틱 기법을 이용하여 부품의 배치 순서를 정한 후 이를 BL 알고리즘을 사용하여 자재에 배치한다. 본 연구에서는 NGCSP의 부품의 배치 각도와 배치 위치를 동시에 고려할 수 있는 보다 범용적인 모형을 제시하였다.
본 연구에서는 각 부품의 꼭지점의 좌표를 이용하여 부품의 배치 각도에 대한 제약을 고려한 개선된 수리 모형을 제시한다.

제안 방법

NGCSP에 관한 연구들은 대부분 휴리스틱 기법을 적용한 것으로 이에 대한 접근은 두 가지 절차로 나누어진다. 첫 번째 절차는 자재 안에 채워질 부품을 선정하고 각 부품 타입 별 개수와 투입 순서를 정한다. 배치할 부품의 선정과 투입 순서가 정해졌으면 두 번째 절차로 자재에 부품을 배치하는 작업을 수행한다.

대상 데이터

3장의 수리 모형을 ILOG CPLEX로 구현하여 해를 구하였고 사용된 컴퓨터 환경은 core i5 M520 2.4GHz, 4GB RAM이다. 계산 시간은 최대 3600초까지 허용하였다.
수리 모형의 타당성을 검증하기 위한 실험 예제로 LCD 패널 제조업체 'A'사의 실제 편광 필름 목형 설계에 사용되는 데이터를 사용하였다.
수리 모형의 타당성을 검증하기 위한 실험 예제로 LCD 패널 제조업체 'A'사의 실제 편광 필름 목형 설계에 사용되는 데이터를 사용하였다. 크기 1520 * 1425의 자재에 A 타입 (305.6 * 482.96), B 타입 (262.35 * 415.44)의 두 가지 타입의 부품을 각각 최소 1개 이상 투입되고 상한은 타입별로 미리 계산된 한 가지 타입만을 고려하여 배치하였을 때의 최대값인 A 타입 9개, B 타입 12개를 사용했다. 각각의 타입 별로 1개 이상 배치가 되어야 하기 때문에 허용 가능한 최대 각 타입 별 최대 배치 가능 개수는 8개와 11개를 적용한다.

데이터처리

본 연구에서 제시한 수리모형의 복잡성(Complexity)을 2장에서 소개했던 Beasley 모형의 복잡성과 비교한다. Beasley 모형의 간섭 배제 제약을 표현한 식(1)과 (2)의 절대값을 벗겨내면 다음과 같이 표현할 수 있다.

이론/모형

수리 모형에서 문제의 복잡성(complexity)이 증가하는 원인은 0-1 변수의 수이다. Beasley 모형과 본 연구에서 제시한 모형은 부품의 배치 여부를 표현하는 변수 z와 각 부품 간의 위치 관계를 나타내는 변수 t를 사용한다. 변수 z와 변수 t는 두 모형 모두에서 동일하게 존재하며 이는 Beasley 모형과 본 연구의 모형의 성능 차이가 거의 없음을 알 수 있다.

성능/효과

변수 z와 변수 t는 두 모형 모두에서 동일하게 존재하며 이는 Beasley 모형과 본 연구의 모형의 성능 차이가 거의 없음을 알 수 있다. 따라서 본 연구에서 제시한 모형은 각도 제약을 고려할 수 있는 범용적 모형임에도 불구하고 복잡성 측면에서도 뒤지지 않음을 알 수 있다.
본 연구에서는 LCD패널 절단 최적화를 위한 수리 모형을 제시하였다. 실제 사례를 풀이함으로써 수리모형의 타당성을 증명하였고, Beasley 모형과의 복잡성 비교를 수행하여 본 연구에서 제시한 수리모형이 보다 범용적이고 복잡성은 동일함을 보였다.

후속연구

본 연구에서는 대략적인 부품 별 상한을 계산하였지만 추후 연구 방향으로는 부품 별 배치가능 개수의 상한을 효과적으로 결정하는 연구가 수행되면 효율성 면에서 큰 개선을 기대할 수 있다. 또한 현재의 수리 모형에 다양한 현실적 제약들의 적용을 연구함으로써 각종 NGCSP가 적용되는 산업에서 효율성을 증대 시킬 수 있으며 사각형뿐만이 아닌 다각형의 배치를 고려한 연구도 중요한 추후 연구 분야 중 하나이다.
부품 별 배치 가능 개수는 하나의 의사결정 변수이며 이러한 의사결정 변수가 늘어남에 따라 계산량은 대폭 증가하게 된다. 본 연구에서는 대략적인 부품 별 상한을 계산하였지만 추후 연구 방향으로는 부품 별 배치가능 개수의 상한을 효과적으로 결정하는 연구가 수행되면 효율성 면에서 큰 개선을 기대할 수 있다. 또한 현재의 수리 모형에 다양한 현실적 제약들의 적용을 연구함으로써 각종 NGCSP가 적용되는 산업에서 효율성을 증대 시킬 수 있으며 사각형뿐만이 아닌 다각형의 배치를 고려한 연구도 중요한 추후 연구 분야 중 하나이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	자재절단 문제란 무엇인가?	자재절단 문제(Cutting Stock Problem)란 일정한 크기로 생산된 원자재를 여러 크기의 부품으로 자를 때 발생되는 손실의 양을 최소화하면서 원하는 부품의 생산을 최대화하는 문제이다[1]. 자재절단 문제는 사용하는 공간의 차원에 따라 1차원, 2차원, 3차원 문제로 분류된다.
	LCD 및 LED 원가 절감의 핵심은 무엇인가?	전 세계적으로 빠르게 성장하는 각종 디스플레이 산업에서 우리나라를 추격하는 국가들과의 경쟁에서 우위를 유지하기 위해서는 품질과 더불어 가격 경쟁력 또한 중요한 요소이다. 때문에 제조 공정 개선을 통한 원가 절감이 시급한 실정이며 LCD 및 LED 생산 중 가장 많은 비용을 차지하는 부품소재인 편광 필름의 원가를 원단의 손실을 최소화하는 목형 설계를 통해 낮추어야 한다. LCD 패널 절단용 목형 설계 문제는 자재의 사용면적을 최대화하면서 사각형 형상의 다양한 크기의 부품을 배치하는 최적화 문제에 대한 연구이다.
	휴리스틱 해법의 한계는 무엇인가?	이와 같은 근래의 NGCSP에 관한 휴리스틱 해법은 각 부품들의 배치해야 할 개수와 순서를 정한 후 이를 자재에 배치하는 방법을 사용하였다. 이러한 해법은 기존의 수리 모형에 적용하기에 적합하지 않고 동시에 배치할 부품의 개수와 위치를 고려하지 않는 순차적 방법이기 때문에 최적해를 보장할 수 없다. 또한 직각 배치만을 고려하였기 때문에 실제 다양한 배치 방법이 존재할 경우 적용하기 어렵다는 단점이 있다.

참고문헌 (22)

G. Wascher, H. Hausner, and H. Schumann, "An improved typology of cutting and packing problems", Eur J Oper Res., Vol. 183, pp.1109-1130, 2007.

상세보기
P. C. Gilmore, and R. E. Gomory, "A linear programming approach to the cutting stock problem-partII", Oper Res., Vol. 11, pp.863-888, 1963.

상세보기
P. C. Gilmore, and R. E. Gomory, "A linear programming approach to the cutting stock problem", Oper Res., Vol. 9, pp.849-859, 1961.

상세보기
M. Gradisar, and P. Trkman, "A combined approach to the solution to the general one-dimensional cutting stock problem", Comput. Oper Res., Vol. 32, pp.1793-1807, 2005.

상세보기
S. Umetani, M. Yagiura, and T. Ibaraki, "One-dimensional cutting stock problem to minimize the number of different patterns", Eur J Oper Res., Vol. 146, pp.388-402, 2003.

상세보기
P. C. Gilmore, and R. E. Gomory, "Multistage cutting stock problems of two and more dimensions", Oper Res., Vol. 13, pp.94-120, 1965.

상세보기
M. Hifi, "An improvement of Viswanathan and Bagchi's exact algorithm for constrained two-dimensional cutting stock", Comput. Oper Res., Vol. 24, pp.727-36, 1997.

상세보기
F. Vanderbeck, "A nested decomposition approach to a three-stage, two dimensional cutting-stock problem", Manag. Sci., Vol. 47, pp.864-79, 2001.

상세보기
E. K. Burke, G. Kendall, and G. Whitwell, "A new placement heuristic for the orthogonal stock cutting problem", Oper Res., Vol. 52, pp.655-71, 2004.

상세보기
Ben Messaoud S, Chu C, and M. Espinouse, "Characterization and modelling of guillotine constraints", Eur J Oper Res., Vol. 191, pp.112-126, 2008.

상세보기
J. E. Beasley, "An exact two-dimensional non-guillotine cutting tree search procedure", Oper Res., Vol. 33, pp.49- 64, 1985.

상세보기
M. Gradisar, J. Jesenko, and C. Resinovic, "Optimization of roll cutting in clothing industry", Comput. Oper Res., Vol. 24, pp.945-953, 1997.

상세보기
A. Abuabara, and R. Morabito, "Cutting optimization of structural tubes to build agricultural light aircrafts", Ann Oper Res., Vol. 169, pp.149-165, 2009.

상세보기
S. Koch, S. Konig, and G. Wscher, "Integer linear programming for a cutting problem in the wood-processing industry: a case study", Int Trans Oper Res., Vol. 16, pp.715-726, 2009.

상세보기
Z. Degraeve, and L. Schrage, "Optimal Integer Solutions to Industrial Cutting Stock Problems", INFORMS J Comput., Vol. 11, pp.406-419, 1999.

상세보기
R. D. Tsai, E. M. Malstrom, and H. D. Meeks., "A twodimensional palletizing procedure for warehouse loading operations", IIE Trans., Vol. 20, pp.418-425, 1988.

상세보기
T. W. Leung, C. H. Yung, and M. D. Troutt, "Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem", Comput. Ind Eng., Vol. 40, pp.201-214, 2001.

상세보기
Y. G. G, and M. K. Kang, "A fast algorithm for two-dimensional pallet loading problems of large size", Eur J Oper Res., Vol. 134, pp.193-202, 2001.

상세보기
A. Bortfeldt, and T. Winter, "A genetic algorithm for the two-dimensional knapsack problem with rectangular pieces", Int Trans Oper Res., Vol. 16, pp.685-713, 2009.

상세보기
J. F. Tsai, P. L. Hsieh, and Y. H. Huang, "An optimization algorithm for cutting stock problems in the TFT-LCD industry", Comput. Oper Res., Vol. 57, pp.913-919, 2009.
H. C. LU, and Y. H. Huang, "An efficient genetic algorithm with a corner space algorithm for a cutting stock problem in the TFT-LCD industry", Eur J Oper Res., Vol. 246, pp.51- 66, 2015.

상세보기
J. F. Goncalves, and M. G. C. Resende, "A hybrid heuristic for the constrained two-dimensional non-guillotine orthogonal cutting problem", Tech Rep., AT&T Labs Research, Florham Park, NJ, 2006.

저자의 다른 논문 :

표제어: 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

연합인증