[논문]타이어 정련 공정 스케줄링을 위한 유전자 알고리즘

안의국; 박상철

doi:10.7315/cadcam.2013.129

타이어 정련 공정 스케줄링을 위한 유전자 알고리즘
Genetic Algorithms for Tire Mixing Process Scheduling 원문보기

한국CAD/CAM학회논문집 = Transactions of the Society of CAD/CAM Engineers, v.18 no.2, 2013년, pp.129 - 137

Abstract ▼ AI-Helper

This paper proposed the scheduling method for tire mixing processes using the genetic algorithm. The characteristics of tire mixing process have the manufacturing routing, operation machine and operation time by compound types. Therefore, the production scheduling has to consider characteristics of the tire mixing process. For the reflection of the characteristics, we reviewed tire mixing processes. Also, this paper introduces the genetic algorithm using the crossover and elitist preserving selection strategy. Fitness is measured by the makespan. The proposed genetic algorithm has been implemented and tested with two examples. Experimental results showed that the proposed algorithm is superior to conventional heuristic algorithm.

주제어

AI 본문요약
AI-Helper

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

문제 정의

하지만 타이어 제조를 위한 일정계획 수립을 위한 구체적인 연구는 많이 부족했다. 본 연구는 정련 공정을 대상으로 생산계획 수립 방안을 제시했다. 이를 위해 A타이어 회사를 대상으로 타이어 정련 공정을 분석했다.
본 연구는 타이어 정련 공정의 스케줄링을 위해 유전자 알고리즘 기반의 스케줄링 방안을 제시했다. 이를 위해 RS와 PS로 유전자의 염색체를 표현했으며, 유전자의 선택 방식은 엘리트 선택법을 이용했다.

가설 설정

기계의 종류 별 특징은 다음과 같다.1) 최종 STEP이나 최종 STEP에서 한 단계 이전 STEP을 작업하는 기계(Machine type 1), 2) STEP 1단계의 작업은 수행하지 않는 기계(Machine type 2), 3) STEP 0은수행하지 않으며, 주로 최종 STEP을 수행하는 기계(Machine type 3), 4) 최종 STEP은 수행하지 않는 기계(Machine type 4)이다. Set-up time조건은 Comp’d를 기계에 할당할 때 같은 배치 사이즈 내의 set-up time은 30초이고, 기계에 새로운 Comp’d를 다시 배치하면 set-up time이 평균 10분 소요된다.

제안 방법

초기 집단의 크기는 8로 정의하였고, 초기 집단 결정시 랜덤 요소와 Comp’d별 작업 가능한 기계에서의 Comp’d 무게, 작업시간, 소요량 등의 요소와 랜덤 소요량을 모두 고려하는 방식을 채택했다. 초기 집단 결정을 위해 RS의 경우 Comp’d 의 STEP별 할당 가능한 기계 중 1) Comp’d 1배치의 무게가 가장 높은 기계에 배치, 2) 1배치의 무게가 가장 낮은 기계에 배치, 3) 작업 시간이 가장 낮은 기계에 배치, 4) 작업 시간이 가장 높은 기계에 배치, 5) CVt_ij 가 가장 낮은 기계에 배치CVt_ij가 가장 높은 기계에 배치, 7~8) 랜덤 배치하는 방안을 채택했다. 이때 CVt_ij 는 아래의 방식으로 구할 수 있다.
PS의 경우1)소요량이 높은 Comp’d 우선배치, 2)소요량이 낮은 Comp’d 우선배치 3) 소요량이 높은 Comp’d부터 순차적으로 우선배치소요량이 낮은 Comp’d부터 순차적으로 우선배치 5~8) 랜덤 배치하는 방안을 채택했다.
RS는 복수 점 교차 방식으로 교차를 수행했으며, PS는 복수 점 교차 이후 실재하는 유전자를 얻기 위해 Comp’d의 STEP내에서 우선 순위에 위배되지 않도록 변환했다.
RS는 염색체에 대해 무작위로 돌연변이 지점을 잡고, 해당 자리에서 작업 가능한 기계를 무작위로 결정하도록 했으며, PS는 염색체에 대해 무작위로 돌연변이 지점을 잡고, 해당 자리의 우선 순위와 같은 우선 순에 해당하는 자리의 값으로 교체하고, 돌연변이 수행 후 Comp’d의 STEP내에서 우선 순위에 위배되지 않도록 변환했다.
총 6개의 대해 Machine type 1, Machine type 2는 1대, Machine type 3, Machine type 4는 2대에 대해 10개의 Comp’d의 생산 STEP 별 작업 가능한 기계, 작업 시간 1배치의 무게를 정의했다. 그리고 소요량의 발생을 C1: 5,800 kg, C2: 4,800 kg, C3: 5,400 kg, C4: 5,100 kg, C5: 4,700 kg, C6:5,900 kg, C7: 6,200 kg, C8: 6,000 kg, C9: 4,600 kg, C10 5,000 kg을 기본 소요량으로 정의하고, 소요량을 증가시켜 가면서 실험을 수행했다. Table 5는 확장된 실험 조건에서의 실험 결과를 표로 보여준다.
또한 전략 2는 초기 해를 생성한 후 makespan을 측정한 이후 엘리트 보전 선택 방식으로 선택과 도태를 수행한다. 그리고, 각 RS에 대해 종료조건의 숫자가 될 때까지 교차를 반복하여 해당 RS에 대한 최저 makespan을 구한다. 그 이후 돌연 변이과정을 통해 새로운 세대를 생성하고, 종료 조건이 아니면 위의 과정을 반복한다.
그리고, 무게를 기반으로 Comp’d를 기계에 할당하는 타이어 정련 공정의 특징을 반영하기 위해 발생한 소요량을 분할하여 배치하는 것과 소요량대로 모두 배치하는 방안에 대해 Comp’d 소요량을 다르게 변화시켜 가면서 비교하는 실험을 수행했다.
이를 위해 A타이어 회사를 대상으로 타이어 정련 공정을 분석했다. 그리고, 분석한 내용을 기반으로 타이어 정련 공정을 단순화하여 모델을 만들고, 유전자 알고리즘을 이용한 생산 스케줄링 방안을 제시했다. 이때 제시한 알고리즘의 적합도를 측정은 makespan으로 했다.
또한 무게기반의 Comp’d의 특성을 반영하기 위해 Comp’d별로 소요량이 발생할 때 분할하여 배치하는 방안에 대해서도 실험을 수행했다.
이를 위해 RS와 PS로 유전자의 염색체를 표현했으며, 유전자의 선택 방식은 엘리트 선택법을 이용했다. 또한 적합도의 판별은 makespan으로 결정했다. 그리고 정련 공정의 특징을 반영해 실험 환경을 만들고, Nasr and Elsayed(1990)가 제안한 휴리스틱 알고리즘과 제안한 전략 1, 전략 2와 비교하여 제안한 방안이 더 나은 makespan을 구하는 것을 볼 수 있었다.
본 연구는 두 가지 방안의 유전자 알고리즘 구조를 제안했다. 전략 1은 초기 해를 생성한 후 makespan을 측정한 이후 엘리트 보전 선택 방식으로 선택과 도태를 수행한다.
기존의 초기 해 생성 방법은 무작위로 만들어진 해를 보정하여 연산하는 방식과 항상 제약 조건을 만족하는 해를 만들어 초기화하는 방식이 있다^[15]. 본 연구는 항상 제약 조건을 만족하는 초기 해를 생성하는 방식을 채택하였다. 이를 위해 Comp’d별로 작업 가능한 기계에서 작업이 가능하도록 하였고, 동일한 Comp’d의 종류 내의 STEP이 빠른 것이 더 높은 우선 순위를 같게 하였다.
본 연구는 정련 공정을 대상으로 생산계획 수립 방안을 제시했다. 이를 위해 A타이어 회사를 대상으로 타이어 정련 공정을 분석했다. 그리고, 분석한 내용을 기반으로 타이어 정련 공정을 단순화하여 모델을 만들고, 유전자 알고리즘을 이용한 생산 스케줄링 방안을 제시했다.
이를 위해 Comp’d별로 작업 가능한 기계에서 작업이 가능하도록 하였고, 동일한 Comp’d의 종류 내의 STEP이 빠른 것이 더 높은 우선 순위를 같게 하였다.

이론/모형

본 연구에서 개체를 선택하기 위해 선택한 방법은 엘리트 보존 선택방식이다. 이는 개체 중에서 가장 적합도가 높은 개체는 그대로 보존하여 다음세대에 남기고, 가장 열등한 개체는 도태시키는 방안이다^[13].
본 연구는 타이어 정련 공정의 스케줄링을 위해 유전자 알고리즘 기반의 스케줄링 방안을 제시했다. 이를 위해 RS와 PS로 유전자의 염색체를 표현했으며, 유전자의 선택 방식은 엘리트 선택법을 이용했다. 또한 적합도의 판별은 makespan으로 결정했다.
PS의 경우1)소요량이 높은 Comp’d 우선배치, 2)소요량이 낮은 Comp’d 우선배치 3) 소요량이 높은 Comp’d부터 순차적으로 우선배치소요량이 낮은 Comp’d부터 순차적으로 우선배치 5~8) 랜덤 배치하는 방안을 채택했다. 해 집단의 평가방식은 Makespan을 기준으로 했다.

성능/효과

그리고, 무게를 기반으로 Comp’d를 기계에 할당하는 타이어 정련 공정의 특징을 반영하기 위해 발생한 소요량을 분할하여 배치하는 것과 소요량대로 모두 배치하는 방안에 대해 Comp’d 소요량을 다르게 변화시켜 가면서 비교하는 실험을 수행했다. 그 결과 제안한 전략 1과 전략 2가 비슷한 makespan 결과를 내는 것을 알 수 있었으며, 소요량이 적을수록 분할하지 않는 것이 유리하며, 많아질수록 분할해 배치하는 것이 더 좋은 makespan 결과를 얻는 것을 알 수 있었다. 향후에는 makespan 이외에도 가동률, set-up time 등 다양한 요소를 고려해 적합도 평가를 수행하는 방안과 Comp’d의 분할 배치에 대한 정보를 염색체에 반영해 스케줄링 할 수 있는 유전자 알고리즘을 제안할 예정이다.
또한 적합도의 판별은 makespan으로 결정했다. 그리고 정련 공정의 특징을 반영해 실험 환경을 만들고, Nasr and Elsayed(1990)가 제안한 휴리스틱 알고리즘과 제안한 전략 1, 전략 2와 비교하여 제안한 방안이 더 나은 makespan을 구하는 것을 볼 수 있었다. 그리고, 무게를 기반으로 Comp’d를 기계에 할당하는 타이어 정련 공정의 특징을 반영하기 위해 발생한 소요량을 분할하여 배치하는 것과 소요량대로 모두 배치하는 방안에 대해 Comp’d 소요량을 다르게 변화시켜 가면서 비교하는 실험을 수행했다.
전략 1과 전략 2의 결과를 도출하는 데 필요한 시간을 비교한 결과 전략 1은 5초 내외로 일정한 시간이 필요한 반면 전략 2의 경우 소요량이 커질수록 Comp’d를 분할한 경우가 분할하지 않은 경우보다 더 많은 시간이 필요한 것을 확인할 수 있었다. 또한 소요량이 증가할수록 분할하는 것이 더 좋은 makespan을 가지는 것을 확인할 수 있었다. 또한 실험을 확장해 수행한 결과 역시 유사한 실험 결과를 얻을 수 있는 것을 알 수 있었다.
실험 1과 2의 결과를 보면 제안한 전략 1과 2가 기존에 제안된 휴리스틱 방안과 비교하여 더 좋은 makespan을 가지는 것을 확인할 수 있었다. 또한 전략 1과 전략 2를 통해 구한 makespan은 전략 2가 더 나은 경향이 있으나 비교적 유사하게 측정되는 것을 알 수 있었다. 전략 1과 전략 2의 결과를 도출하는 데 필요한 시간을 비교한 결과 전략 1은 5초 내외로 일정한 시간이 필요한 반면 전략 2의 경우 소요량이 커질수록 Comp’d를 분할한 경우가 분할하지 않은 경우보다 더 많은 시간이 필요한 것을 확인할 수 있었다.
Table 5는 확장된 실험 조건에서의 실험 결과를 표로 보여준다. 실험 1과 2의 결과를 보면 제안한 전략 1과 2가 기존에 제안된 휴리스틱 방안과 비교하여 더 좋은 makespan을 가지는 것을 확인할 수 있었다. 또한 전략 1과 전략 2를 통해 구한 makespan은 전략 2가 더 나은 경향이 있으나 비교적 유사하게 측정되는 것을 알 수 있었다.
실험을 위해 N.Nasr and E.A. Elsayed (1990)가 제안한 휴리스틱 알고리즘^[5] , 전략 1, 전략2를 고려해makespan과 결과 도출까지의 시간을 초기 소요량과 비교해 최대 4배까지 증가시켜가며 실험 결과결과를 얻었다. 또한 무게기반의 Comp’d의 특성을 반영하기 위해 Comp’d별로 소요량이 발생할 때 분할하여 배치하는 방안에 대해서도 실험을 수행했다.
전략 1과 전략 2의 결과를 도출하는 데 필요한 시간을 비교한 결과 전략 1은 5초 내외로 일정한 시간이 필요한 반면 전략 2의 경우 소요량이 커질수록 Comp’d를 분할한 경우가 분할하지 않은 경우보다 더 많은 시간이 필요한 것을 확인할 수 있었다.

후속연구

향후에는 makespan 이외에도 가동률, set-up time 등 다양한 요소를 고려해 적합도 평가를 수행하는 방안과 Comp’d의 분할 배치에 대한 정보를 염색체에 반영해 스케줄링 할 수 있는 유전자 알고리즘을 제안할 예정이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	정련공정이란 무엇인가?	이 중 정련공정은 천연고무와 합성 고무를 여러 가지 약품을 첨가해 밀 또는 믹서에 넣고 혼합하는데 이 공정에서 타이어의 재료로써 고무에 필요한 특성을 갖도록 하는 기초공정이자 타이어 완제품 상에 제품 품질에 영향을 많이 주는 공정이다[12]. 또한 원재료를 가져와 처음 작업하는 공정이기 때문에 정련공정에서 다음 공정에 원활히 제품을 공급하지 못하면 타이어 제조 전체의 흐름에 차질을 주기 때문에 후 공정이 필요로 하는 제품을 제때에 제공하는 것이 무엇보다 중요한 공정이다.
	타이어 제조 공정에서 하나의 공장에 큰 부지와 많은 설비의 투입이 이뤄지는 이유는 무엇인가?	타이어 제조 공정은 대부분의 자동차용 고무 부품을 만드는 공장처럼 Job-shop 배치 형태를 따르기 때문에, 하나의 공장에 큰 부지와 많은 설비의 투입이 이뤄진다. 또한, 이동하는 반제품의 이동 형태가 복잡하고 긴 동선을 가지는 특징이 있다[1].
	타이어 제조에 있어서 정련공정의 생산계획이 중요한 이유는 무엇인가?	이 중 정련공정은 천연고무와 합성 고무를 여러 가지 약품을 첨가해 밀 또는 믹서에 넣고 혼합하는데 이 공정에서 타이어의 재료로써 고무에 필요한 특성을 갖도록 하는 기초공정이자 타이어 완제품 상에 제품 품질에 영향을 많이 주는 공정이다[12]. 또한 원재료를 가져와 처음 작업하는 공정이기 때문에 정련공정에서 다음 공정에 원활히 제품을 공급하지 못하면 타이어 제조 전체의 흐름에 차질을 주기 때문에 후 공정이 필요로 하는 제품을 제때에 제공하는 것이 무엇보다 중요한 공정이다. 하지만 과다하게 생산할 경우 재고로 남아 자원의 낭비를 초래할 수 있다. 따라서 타이어 제조에 있어 정련공정의 생산계획을 수립은 중요하다.

참고문헌 (15)

Moon, D. H. and Chang, K. K., 2000, A Simulation Model for Supporting System Design of Tire Manufacturing System, Korean Simulation Association, Vol.9 No.2, pp. 27-38.
Carlier, J. and Pinson, E., 1989, An Algorithm for Solving the Job-shop Problem, Management Science, Vol. 35, No. 2, pp. 164-176.

상세보기
Joseph Adams, Egon Balas, and Daniel Zawack- Reviewed, 1988, The Shifting Bottleneck Procedure for Job Shop Scheduling, Management Science, Vol. 34, No. 3, pp. 391-401.

상세보기
Kenneth R. Baker, 1974, Introduction to Sequencing and Scheduling, John Wiley & Sons, Inc, pp. 178-210.
Nabil Nasr and Elsayed, E. A., 1990, Job Shop Scheduling with Alternative Machines, International Journal of Production Research, Vol. 28, No. 9, pp. 1595-1609.

상세보기
Park, J.-H., Choi, Hoeryron and Kim, Y. H., 1998, A Genetic Algorithm Approach to Job Shop Scheduling Considering Alternative Process Plans, Journal of the Korean Institute of Industrial Engineers, Vol. 24, No. 4 pp. 130-145.
Moon, I. K., Lee, S. H. and Bae, H. R., 2008, Genetic Algorithms for Job Shop Scheduling Problems with Alternative Routings, International Journal of Production Research, Vol. 46, No. 10, pp. 2695-2705.

상세보기
Hong Zhou, Yuncheng Feng, and Limin Han, 2001, The Hybrid Heuristic Genetic Algorithm for Job Shop Scheduling, Computers & Industrial Engineering,Vol. 40, No. 3, pp. 191-200.

상세보기
Park, S. J., Kim, J. W. and Kim, H. W., 1996, Heuristic Knowledge Representation of Production Scheduling: An Integrated Modeling Approach, Expert System With Applications, Vol. 10, No. 3, pp. 325-339.

상세보기
Chung, J. B. and Yoon, J. H. 2009, The Implementation of a Production Planning System in a Tire Manufacturing Company: Case Study, Entrue Journal of Information Technology, Vol. 8, No. 1.
http://www.eng.buffalo.edu/Courses/ce435/2001ZGu/ Firestone_Tires/FirestoneTiresReport.htm
Kim, H. W., Kim, T., Cho, J. G. and Moon, S. S., 2000, Tire Engineering, Goldenbell, pp. 64-65.
Lee, S. Y., 2010, The World of Artificial Intelligence, 21centries, pp. 400-410.
Jeong, Y. S., Yim, H. J. Jee, H. S. and Lee, K. K., 2008, Manufacturing Line Optimization for Discrete Event Simulation and Genetic Algorithm, Transactions of the Society of CAD/CAM Engineers, Vol. 13, No. 1, pp. 67-75.
Cheng, R. and Gen, M., 1997, Resource Constrained Project Scheduling Problem Using Genetic Algorithms, International Journal of Intelligent Automation and Soft Computing, Vol. 3, No. 3, pp. 273-286.

상세보기

저자의 다른 논문 :

LOADING...

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

연합인증