[논문]단일모델 단측 조립라인 균형문제의 주경로 군집화 알고리즘

이상운

doi:10.9708/jksci.2014.19.5.089

단일모델 단측 조립라인 균형문제의 주경로 군집화 알고리즘
A Single-model Single-sided Assembly Line Balancing Problem Using Main-path Clustering Algorithm 원문보기

韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.19 no.5, 2014년, pp.89 - 98

초록
AI-Helper

본 논문은 NP-난제 문제로 알려진 단일모델 단방향 조립라인 균형문제에 대해 휴리스틱 알고리즘을 제안하였다. 조립라인 균형문제는 주로 메타휴리스틱 방법들을 적용하고 있는 추세이다. 제안된 알고리즘은 최종제품이 생산될 때까지 가장 많은 공정으로 조립되는 경로를 주경로로 설정하고, 주경로를 따라가면서 각 작업자에게 순환시간 조건을 만족하는 작업량을 배정하는 군집화 알고리즘을 제안하였다. 제안된 알고리즘은 최소의 작업자수를 결정하고, 순환시간도 단축시키는 결과를 얻었다. 9개의 다양한 실험 데이터에 제안된 주경로 군집화 휴리스틱 알고리즘을 적용한 결과 메타휴리스틱 방법들에 비해 보다 좋은 성능을 갖고 있음을 보였다.

Abstract ▼ AI-Helper

This paper suggests heuristic algorithm for single-model simple assembly line balancing problem that is a kind of NP-hard problem. This problem primarily can be solved metaheuristic method. This heuristic algorithm set the main-path that has a most number of operations from start to end-product. Then the clustering algorithm can be assigns operations to each workstation within cycle time follow main-path. This algorithm decides minimum number of workstations and can be reduces the cycle time. This algorithm can be better performance then metaheuristic methods.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문은 NP-난제로 알려진 단일모델 단방향 조립라인 균형문제에 대해 휴리스틱 알고리즘을 제안하였다. 제안된 알고리즘은 단순히 최종제품이 생산될 때까지 가장 많은 공정으로 조립되는 경로를 주경로로 설정하고, 주경로를 따라가면서각 작업자에게 작업량을 배정하는 군집화 알고리즘을 제안하 였다.

제안 방법

본 장에서는 계획된 완제품을 생산하는데 소요되는 총 작업소요시간 W와 한 작업대 (workstation, S i ,i = 1,2, ⋯,m)에서 머무르는 시간인 순환시간 (cycle time) c가 주어졌을 때, 최소 작업대 수 즉, 최소로 필요한 작업자 수 m∗ 와 한 명의 작업자가 작업하는 시간을 c보다 작은 Tmax 를 찾는 휴리스틱 알고리즘을 제안한다.
본 논문은 NP-난제로 알려진 단일모델 단방향 조립라인 균형문제에 대해 휴리스틱 알고리즘을 제안하였다. 제안된 알고리즘은 단순히 최종제품이 생산될 때까지 가장 많은 공정으로 조립되는 경로를 주경로로 설정하고, 주경로를 따라가면서각 작업자에게 작업량을 배정하는 군집화 알고리즘을 제안하 였다.
제안된 알고리즘은 주 경로 개념을 도입하여 단순히 주경로 상의 작업을 우선하여 부경로 상의 작업들을 추가하면서 c 를 충족하도록 작업들을 분할하였다. 이와 같은 단순한 휴리 스틱 규칙을 적용하였음에도 불구하고, 9개의 다양한 실험 데이터에 제안된 주경로 군집화 휴리스틱 알고리즘을 적용한 결과 메타휴리스틱 방법들에 비해 보다 좋은 성능을 갖고 있음을 보였다.

이론/모형

최좌측 레벨부터 최우측레벨까지 작업 공정수가 가장 많은 경로를 주 경로 (main path), 나머지 공정 경로들을 부 경로 (sub path)라 하자. 여기서 제안된 방법은 주경로 군집화 알고리즘 (main-path clustering algorithm, MPCA)으로 다음과 같이 수행된다.
제안된 주경로 군집 알고리즘은 휴리스틱 방법으로 다음과같은 특징을 갖고 있다.

성능/효과

(3) 각 작업자의 순환시간 편차가 최소가 되도록 하여 유휴 시간 (idle time)을 최소화 시킬 뿐 아니라 작업자 간 가능한 작업시간의 균형 (최소 편차)을 맞출 수 있다.
또한 MPCA는 9개 데이터 모두에서 m을 최소의 작업자수로 결정하여 최대의 생산성을 얻도록 하였으며, Gunter 데이터에 대해서는 기존의 TS에 비해 작업자 수를 1명 감소시킬 수 있었다. SI 와 LE 를 비교하면 Gunter, Warneke와 Motorcycle 데이터에서 MPCA가 메타휴리스틱 방법에 비해 좋은 결과를 나타내었으며, 나머지 6개 데이터에 대해서는 동일한 결과를 얻었다.
각 문제에서 주어진 순환시간 c와 모델로부터 얻은 Tmax 를 비교한 결과, Tmax = c인 Grzechca를 제외한 8개 데이터 에서 Tmax < c로 순환시간을 감소시킬 수 있었다.
결론적으로, 제안된 알고리즘은 단일모델 단측 조립라인 균형문제가 NP-난제가 아닌 다항시간 알고리즘이 존재하는 P-문제가 될 수 있음을 보였다.
< c로 순환시간을 감소시킬 수 있었다. 또한 MPCA는 9개 데이터 모두에서 m을 최소의 작업자수로 결정하여 최대의 생산성을 얻도록 하였으며, Gunter 데이터에 대해서는 기존의 TS에 비해 작업자 수를 1명 감소시킬 수 있었다. SI 와 LE 를 비교하면 Gunter, Warneke와 Motorcycle 데이터에서 MPCA가 메타휴리스틱 방법에 비해 좋은 결과를 나타내었으며, 나머지 6개 데이터에 대해서는 동일한 결과를 얻었다.
본 그림으로부터 제안된 MPCA는 휴리스틱 알고리즘임에도 불구하고, 메타 휴리스틱 알고리즘들에 비해 성능을 향상시킨 결과를 얻었음을 알 수 있다.
본 논문에서는 조립라인 균형문제를 최종 완제품이 생산될 때까지의 공정 개수가 최대인 경로를 주경로 (main path)로 설정하고, 주경로를 따라가면서 각 작업대에 균형된 작업량을 배정하는 휴리스틱 알고리즘을 제안하고, 제안된 휴리스틱 알고리즘이 메타휴리스틱 방법에 비해 보다 좋은 결과를 얻을 수 있음을 보인다.
제안된 알고리즘은 주 경로 개념을 도입하여 단순히 주경로 상의 작업을 우선하여 부경로 상의 작업들을 추가하면서 c 를 충족하도록 작업들을 분할하였다. 이와 같은 단순한 휴리 스틱 규칙을 적용하였음에도 불구하고, 9개의 다양한 실험 데이터에 제안된 주경로 군집화 휴리스틱 알고리즘을 적용한 결과 메타휴리스틱 방법들에 비해 보다 좋은 성능을 갖고 있음을 보였다.

질의응답

핵심어	질문	논문에서 추출한 답변
	유제조분야의 조립라인 균형 문제는 언제부터 제기되었는가?	유제조분야의 조립라인 균형 (assembly line balancing, ALB) 문제는 1900년대 초부터 제기 되어온 문제로, 특정 제품을 제조하는데 있어 효율적이고 높은 생산성을 갖도록 작업 자들에게 작업량을 배정하는 방법이다[1]. 조립라인은 선형 으로 배치된 작업대들 (workstations)로 구성되어 있으며, 부품 (자재)은 첫 번째 작업대에 투입된 이후 컨베이어 벨트 조립라인을 통해 다음 작업대로 계속적으로 이동되면서 조립 되어 최종적으로 완제품이 생산된다.
	유제조분야의 조립라인 균형 문제란 무엇인가?	유제조분야의 조립라인 균형 (assembly line balancing, ALB) 문제는 1900년대 초부터 제기 되어온 문제로, 특정 제품을 제조하는데 있어 효율적이고 높은 생산성을 갖도록 작업 자들에게 작업량을 배정하는 방법이다[1]. 조립라인은 선형 으로 배치된 작업대들 (workstations)로 구성되어 있으며, 부품 (자재)은 첫 번째 작업대에 투입된 이후 컨베이어 벨트 조립라인을 통해 다음 작업대로 계속적으로 이동되면서 조립 되어 최종적으로 완제품이 생산된다.
	유제조분야의 조립라인은 무엇으로 구성되어 있는가?	유제조분야의 조립라인 균형 (assembly line balancing, ALB) 문제는 1900년대 초부터 제기 되어온 문제로, 특정 제품을 제조하는데 있어 효율적이고 높은 생산성을 갖도록 작업 자들에게 작업량을 배정하는 방법이다[1]. 조립라인은 선형 으로 배치된 작업대들 (workstations)로 구성되어 있으며, 부품 (자재)은 첫 번째 작업대에 투입된 이후 컨베이어 벨트 조립라인을 통해 다음 작업대로 계속적으로 이동되면서 조립 되어 최종적으로 완제품이 생산된다. 일단 제품이 작업대에 도착하면 작업자가 할당된 부품들에 대한 작업을 수행하고, 수행된 제품은 다음 공정 (operation)으로 이동된다.

참고문헌 (20)

S. Suwannarongsi and D. Puangdownreong, "Optimal Assembly Line Balancing Using Tabu Search with Partial Random Permutation Technique," International Journal of Management Science and Engineering Management, Vol. 3, No. 1, pp. 3-18, Jan, 2008.
R. Sury, "Aspects of Assembly Line Balancing," International Journal of Production Research, Vol. 9, No. 4, pp. 501-512, Feb, 1971.

상세보기
I. Baybars, "A Survey of Exact Algorithms for the Simple Assembly Line Balancing Problem," Management Science, Vol. 32, No. 8, pp. 900-932, Aug, 1986.
A. Gutjahr and G. Nemhauser, "An Algorithm for the Balancing Problem," Management Science, Vol. 11, No. 2, pp. 308-315, Nov, 1964.

상세보기
W. Helgeson and D. Birnie, "Assembly Line Balancing using the Ranked Positional Weighting Technique," Journal of Industrial Engineering, Vol. 12, pp. 394-397, 1961.
J. Rubinovitz and G. Levitin, "Genetic Algorithm for Assembly Line Balancing," International Journal of Production Economics, Vol. 41, No. 1-3, pp. 343-354, Oct, 1995.

상세보기
P. McMullen and G. Frazier, "Using Simulated Annealing to solve a Multi-objective Assembly Line Balancing Problem with Parallel Work Stations," International Journal of Production Research, Vol. 36, No. 10, pp. 2717-2741, Oct, 1998.

상세보기
E. Murat, K. Ozgur, and U. Fusun, "An Agent based Supply Chain System with Neural Network Controlled Processes," Lecture Notes in Computer Science, Vol. 3314, pp. 837-846, 2004.
P. McMullen and P. Tarasewich, "Multiobjective Assembly Line Balancing via a Modified Ant-colony Optimization Technique," International Journal of Production Research, Vol. 44, No. 1, pp. 27-42, Jan, 2006.

상세보기
W. Grzechca, "Assembly Line Balancing Problem Single and Two-Sided Structures, Automation and Control-Theory and Practice," ISBN 978-953-307-039-1, Intech China, Aug. 2011.
E. E. Porsteinsson, G. Baldursson, and H. Ingimundardottir, "Assembly Line Balancing," Haskoli Islands, pp. 1-17, https://notendur.hi.is/eth31/AGGRV02.pdf, 2011.
K. E. Chong, M. K. Omar, and N. A. Bakar, "Solving Assembly Line Balancing Problem using Genetic Algorithm with Heuristics-Treated Initial Population," Proceedings of the World Congress on Engineering 2008, Vol. II, London, U.K., pp. 1273-1277, Jul, 2008.
M. F. Yegul, K. Agpak, and M. Yavuz, "A New Algorithm for U-shaped Two-sided Assembly Line Balancing," Transactions of Canadian Society for Mechanical Engineering, Vol. 34, No. 2, pp. 225-241, May, 2010.
N. Kriengkorakot and N. Pianthong, "The Assembly Line Balancing Problem: Review Articles," KKU Engineering Journal, Vol. 34, No. 2, pp. 133-140, Apr. 2007.
C. Becker and A. Scholl, "A Survey on Problems and Methods in Generalized Assembly Line Balancing," European Journal of Operational Research, Vol. 168, No. 3, pp. 694-715, Feb, 2006.

상세보기
S. Suwannarongsi and D. Puangdownreong, "Metaheuristic Approach to Assembly Line Balancing," WSEAS Transactions on Systems, Vol. 8, No. 2, pp. 200-209, Feb, 2009.
W. Grazechca, "Assembly Line Balancing Problem Single and Two-sided Structures," Automation and Control-Theory and Practice," ISBN 978-953-307-039-1, Intech China, Aug, 2011.
A. Scholl, "Data of Assembly Line Balancing Problems," Technische Universitat Darmstadt, Institut fur Betriebswirtschaftslehre Hochschulstrasse 1, D-64289 Darmstadt, Germany, Sep, 1997.
A. Scholl, "Balancing and Sequencing of Assembly Lines," Physica, Heidelberg, 1999.
Kawasaki Motor Enterprise (Thailand) Ltd., "Data Sheet of the Motorcycle Assembly Line," 119/10 GK Land Industrial Estate, Rayong, Thailand, 2003.

저자의 다른 논문 :

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

연합인증