[논문]병렬라인 검사공정의 작업배분을 위한 휴리스틱 알고리즘의 성능 개선

박승헌; 이석환

doi:10.12812/ksms.2012.14.1.167

문제 정의

본 연구의 목적은 기존 연구에서 개발한 휴리스틱 알고리즘에 새로운 방법을 추가하여 알고리즘의 성능을 개선하는 것이다. 검사공정의 작업배분을 위한 휴리스틱 알고리즘의 목적함수는 복수의 작업자에게 작업(시간)을 공평하게 배분하여 평활지수를 최소로 하는 것이다.
기존의 FE방법으로는 최적해가 존재함에도 불구하고 최적해를 찾지 못하는 경우가 있었다. 따라서 본 연구에서는 이를 보완하기 위해 FN(First Next)방법을 제시한다. FN방법은 작업들을 작업시간의 내림차순으로 정렬한 후 정렬된 작업의 맨 첫 작업 즉, 작업시간이 가장 큰 작업에 그 다음으로 작업시간이 큰 작업들을 배분하면서 작업배분의 초기해를 생성한다([그림 4] 참조).
본 연구는 검사공정에서 공평한 작업배분을 위한 휴리스틱 알고리즘의 성능을 개선하는 것이다. 2.
기존 연구에서는 검사공정에서 작업자에게 작업을 공평하게 배분하기 위해 휴리스틱 알고리즘을 개발하였다[5]. 본 연구의 목적은 기존 알고리즘의 성능을 개선하는 것이다. 알고리즘의 개선여부 즉, 작업이 공평하게 배분되었는지는 기존연구와 동일하게 평활지수(smooth index)로 측정한다.
첫 번째 실험은 기존 연구와 동일한 데이터를 사용하여 FE+FN 혼용 알고리즘이 최적배분의 해를 어느 정도 찾을 수 있는지 평가하는 것이다. 이 경우는 3.
그러나 본 연구에서는 작업시간의 분산과 평활지수 간에 특별한 경향이 발견되지 않았다. 본 연구에서는 작업의 개수를 증가시켜서 실험을 하였다. 작업의 개수가 증가하면 일인 작업자에게 배분되는 작업이 증가한다.
본 연구에서는 병렬라인 검사공정에서 복수의 작업자에게 작업을 배분하는 기존 휴리스틱 알고리즘(FE방법)의 성능을 개선하였다. 기존 알고리즘은 FE방법만으로 초기해를 생성하였으나 본 연구에서는 새로운 FN 방법을 고안하여 FE와 FN 방법을 혼용함으로써 알고리즘의 성능을 개선하였다.

제안 방법

본 연구의 휴리스틱 알고리즘은 C++언어로 구현하였다. FE+FN 방법 혼용 알고리즘이 최적배분의 해를 어느 정도 찾을 수 있는지 평가하기 위해 두 가지 실험을 수행하였다.
본 연구의 휴리스틱 알고리즘은 C++언어로 구현하였다. FE+FN 방법 혼용 알고리즘이 최적배분의 해를 어느 정도 찾을 수 있는지 평가하기 위해 두 가지 실험을 수행하였다.
1절에서 수행하였다. 두 번째 실험은 새로운 데이터로 작업개수를 증가시켜서 FE+FN 혼용 알고리즘이 평활 지수 0에 근사한 작업배분을 찾을 수 있는지 평가하는 것이다. 이 경우는 3.
첫번째 실험은 기존 연구의 데이터를 사용하여 FE+FN 혼용 알고리즘이 기존 알고리즘에 비해서 최적 배분의 해를 어느 정도 찾을 수 있는지 평가한다. <표 1>은 기존 알고리즘과 FE+FN 혼용 알고리즘에 따른 작업배분의 평활지수를 비교한 것이다.
두 번째 실험은 새로운 데이터를 이용한 실험이다. 이 실험은 작업의 개수가 많아질 경우 FE+FN 혼용 휴리스틱 알고리즘이 기존 알고리즘에 비해서 최적배분의 해를 어느 정도 찾을 수 있는지 평가한다. 실험 데이터는 최적해가 한 개 있는 경우, 여러 개 있는 경우, 최적 해가 없는 경우의 세 가지로 하고 작업개수는 18, 21, 24에 작업자 수는 3, 4, 6으로 하였다.
다음은 작업시간의 분산과 평활지수간의 관계를 확인하는 실험이다. 작업의 개수는 18, 21, 24개로 하였고 각 경우의 분산은 10, 20, 30, 40, 50으로 설정하였다. 작업자의 수는 앞의 실험과 동일하게 3, 4, 6명으로 하였다.
본 연구에서는 병렬라인 검사공정에서 복수의 작업자에게 작업을 배분하는 기존 휴리스틱 알고리즘(FE방법)의 성능을 개선하였다. 기존 알고리즘은 FE방법만으로 초기해를 생성하였으나 본 연구에서는 새로운 FN 방법을 고안하여 FE와 FN 방법을 혼용함으로써 알고리즘의 성능을 개선하였다. FE+FN 방법 혼용 휴리스틱 알고리즘의 성능은 실험을 통하여 확인하였으며 그 효과 및 특성은 다음과 같다.

이론/모형

[그림 5]는 본 연구에서 새롭게 제시한 FN방법을 추가하여 FE+FN방법을 혼용하는 알고리즘 전개과정이다. 음영 부분은 본 연구에서 새롭게 제시한 FN방법이다.

성능/효과

이 방법은 정렬된 작업의 첫 작업에 그 다음으로 큰 작업을 배분하므로 FN(First Next)방법이라고 한다. 본 연구에서 제시한 FN방법을 기존 연구의 FE방법과 혼용할 경우 FE방법의 단점을 보완할 수 있기 때문에 작업배분을 위한 휴리스틱 알고리즘의 성능은 크게 개선될 수 있다.
(3) 한 명의 작업자에게 가장 작업시간이 긴 작업 max(J_i) 을 배분한다.
음영부분은 평활지수가 가장 좋은 알고리즘을 표시한 것이다. <표 1>의 결과와 같이 총 26회의 실험에서 FE+FN 혼용 알고리즘은 기존의 알고리즘으로 찾을 수 없는 좋은 해를 2개 더 찾을 수 있었다. 한 개의 최적해가 존재하는 경우 작업개수 12개를 3명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 평활지수를 0으로 하는 최적해를 발견하였다.
한 개의 최적해가 존재하는 경우 작업개수 12개를 3명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 평활지수를 0으로 하는 최적해를 발견하였다. 최적해가 없는 경우 작업개수 15개를 4명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 기존 알고리즘의 평활지수를 6.16에서 1.41로 77.1% 향상시켰다. <표 2>와 <표 3>는 <표 1>에서 FE+FN 혼용 알고리즘이 기존 FE방법보다 더 나은 해를 찾아낸 작업배분 결과를 나타낸 것이다.
<표 3>은 최적해가 없는 경우 15개 작업을 4명의 작업자에게 할당한 결과를 나타낸 것이다. 이 결과는 FE방법에 FN방법을 혼용할 경우 더욱 좋은 해를 발견할 수 있다는 것을 보여준다.
<표 4>의 결과와 같이 총 27회의 실험에서 FE+FN 혼용 알고리즘은 기존의 알고리즘으로 찾을 수 없는 좋은 해를 9개 더 찾을 수 있었다. 한 개의 최적해가 존재하는 경우 18개 작업을 4명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 최적해를 발견하였다.
3.1절의 실험결과와 같이 FE+FN 혼용 알고리즘은 기존의 알고리즘에서 발견할 수 없는 해를 발견할 수있었다. 두 번째 실험은 새로운 데이터를 이용한 실험이다.
<표 4>의 결과와 같이 총 27회의 실험에서 FE+FN 혼용 알고리즘은 기존의 알고리즘으로 찾을 수 없는 좋은 해를 9개 더 찾을 수 있었다. 한 개의 최적해가 존재하는 경우 18개 작업을 4명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 최적해를 발견하였다.
여러 개의 최적해가 존재하는 경우 18개 작업을 3, 4명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 최적해를 발견하였다. 21개 작업을 3명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 최적해를 발견하였다. 최적해가 없는 경우 18개 작업을 3, 4명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 기존 알고리즘의 평활지수를 7.
여러 개의 최적해가 존재하는 경우 18개 작업을 3, 4명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 최적해를 발견하였다. 21개 작업을 3명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 최적해를 발견하였다.
21개 작업을 3명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 최적해를 발견하였다. 최적해가 없는 경우 18개 작업을 3, 4명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 기존 알고리즘의 평활지수를 7.62에서 3.16, 2.24에서 1.73으로 각각 58.5%, 22.8% 향상시켰다. 21개 작업을 6명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 기존 알고리즘의 평활지수를 3.
8% 향상시켰다. 21개 작업을 6명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 기존 알고리즘의 평활지수를 3.61에서 1.00으로 72.3% 향상시켰다. 작업개수 24개를 3, 6명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 기존 알고리즘의 평활지수를 3.
3% 향상시켰다. 작업개수 24개를 3, 6명의 작업자에게 할당하는 예에서 FE+FN 혼용 알고리즘은 기존 알고리즘의 평활지수를 3.16에서 1.00, 6.86에서 6.40으로 각각 68.4%, 6.7% 향상시켰다. 이 결과는 3.
7% 향상시켰다. 이 결과는 3.1절의 실험(기존 연구의 데이터를 사용)과 동일하게 FE과 FN방법을 혼용할 경우 더욱 좋은 해를 발견할 수 있다는 것을 보여주는 것이다.
첫째, 평활지수 0인 최적배분의 해가 한 개 이상인 경우 이 혼용 알고리즘은 최적배분의 해를 대부분 찾을 수 있어 우수한 성능을 확인하였다( 참조).
둘째, 평활지수 0인 최적배분의 해가 없는 경우 FE+FN 혼용 알고리즘은 FE방법 알고리즘의 평활지수를 평균 43.42% 개선한 해를 찾을 수 있었다( 참조).
다음으로 FE+FN 혼용 알고리즘의 특성은 다음과 같다. 첫째, 평활지수 0인 최적배분의 해가 존재하는 경우 작업의개수가 많아질수록 FE+FN 혼용 알고리즘은 최적배분 해를 발견하는 확률이 높아진다. 둘째, 작업의 개수가 많아질 경우 작업시간의 분산이 평활지수에 주는 영향은 감소한다.
첫째, 평활지수 0인 최적배분의 해가 존재하는 경우 작업의개수가 많아질수록 FE+FN 혼용 알고리즘은 최적배분 해를 발견하는 확률이 높아진다. 둘째, 작업의 개수가 많아질 경우 작업시간의 분산이 평활지수에 주는 영향은 감소한다.
본 연구의 FE+FN 혼용 알고리즘은 FE방법에서 찾을 수 없는 좋은 해를 찾을 수 있기 때문에 휴리스틱 알고리즘의 성능을 개선할 수 있었다. 이 알고리즘을 사용하여 작업배분을 할 경우 모든 작업자에게 공평한 작업배분이 가능하기 때문에 불공평한 작업배분으로 발생하는 문제를 해결할 수 있다.

핵심어	질문	논문에서 추출한 답변
	병렬라인 시스템의 장점은?	많은 제조업체들은 고객의 다양한 제품수요를 충족시키기 위해 병렬라인 시스템을 도입하고 있다. 병렬라인 시스템은 다양한 품목을 대량으로 생산할 수 있다. 이러한 병렬라인 시스템의 검사공정은 전기․전자 분야 등에 도입되고 있으며 그 효율을 높이기 위해서 하나로 통합하여 운영한다.
	기존 연구의 휴리스틱 알고리즘을 이용하여 최적해를 찾는 방법은?	기존 연구의 휴리스틱 알고리즘은 작업배분의 초기 해를 생성하고 그 초기해를 이용하여 최적해를 찾는다. 작업배분의 초기해 생성과정은 다음과 같다.
	FN(First Next)방법에 관해 설명하시오.	이 방법을 설명하면 다음과 같다. 먼저 작업들을 작업시간의 내림차순으로 정렬한다. 다음으로 정렬된 작업의 맨 첫 작업 즉, 작업시간이 가장 큰 작업에 그 다음으로 작업시간이 큰 작업부터 하나씩 배분한다. 이 방법은 첫 작업에 그 다음 작업을 배분하기 때문에 FN(First Next)방법이라고 한다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

[국내논문] 병렬라인 검사공정의 작업배분을 위한 휴리스틱 알고리즘의 성능 개선
Performance improvement of heuristic algorithm to assign job in parallel line inspection process 원문보기

Abstract ▼ AI-Helper

Keyword

AI 본문요약
AI-Helper

문제 정의

제안 방법

이론/모형

성능/효과

질의응답

참고문헌 (10)

이 논문을 인용한 문헌

저자의 다른 논문 :

활용도 분석정보

활용도 Top5 논문

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

[국내논문] 병렬라인 검사공정의 작업배분을 위한 휴리스틱 알고리즘의 성능 개선 Performance improvement of heuristic algorithm to assign job in parallel line inspection process 원문보기

Abstract ▼ AI-Helper

Keyword

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

이론/모형

성능/효과

질의응답

참고문헌 (10)

이 논문을 인용한 문헌

저자의 다른 논문 :

박승헌 (20) 이석환 (9)

활용도 분석정보

활용도 Top5 논문 더보기

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

[국내논문] 병렬라인 검사공정의 작업배분을 위한 휴리스틱 알고리즘의 성능 개선
Performance improvement of heuristic algorithm to assign job in parallel line inspection process 원문보기

AI 본문요약
AI-Helper

활용도 Top5 논문