[논문]Job Shop 일정계획을 위한 병렬 유전 알고리즘

박병주; 김현수

문제 정의

본 연구에서는 JSSP를 보다 효과적으로 해결하기 위해 유전 알고리즘에 기반한 일정계획 기법을 제시한다. 이 기법에서는 새로운 유전 연산자, 초기 모집단 구성방법을 사용한다.
본 연구에서는 JSSP를 위해 유전 알고리즘을 기반으로 한 일정계획 기법을 제안하였다. 제안한 일정계획 기법에서 표현은 공정의 순서를 job의 번호로 코드화 하여 항상 해가 실행 가능하도록 하였고, 이를 G&T 알고리즘과 연결하여 초기 모집단을 구성하였다.
본 연구에서는 섬모델 PGA를 제안한다. 이 섬모델 PGA에서 부 집단들의 연결은 정적 연결구조를 가지고, 이종(異種) 섬모델 PGA로 구성된다.

가설 설정

job과 기계들에 대한 주요 제약은 하나의 기계는 같은 시점에 단 하나의 job만을 처리할 수 있고, 어떤 job이 기계에서 처리되면 중간에 정지시킬 수 없다는 것이다. 또한 기계에 도착되는 job의 가공시간은 미리 알려져 있다고 가정한다.

제안 방법

두 부 집단이 50 세대 진행되면 동시에 일정 개체 수를 이주하도록 하였다. 4S-PGA에서는 4개로 분리된 초 기부 집단을 active', active, non-delay, random 스케쥴로 구성하여 각각의 부 집단에 SGA에서의 유전연산자를 적용하고, 2S-PGA와 같이 50세대 진행 후 이주하도록 하였다. 이주개체 선별과 대체 방법은 이주시기에 각 부 집단의 개체를 정한 개수만큼 임의대로 선별해서 서로 교환하는 방법과 각 부 집단에서 정해진 순위 안에 드는 개체를 복사하여 연결되어 있는 다른 부 집단의 나쁜 개체를 교체하는 방법 중 좋은 결과를 산출한 후자의 이주 방법을 사용한다.
FT 문제에 SGA, PGA를 기반으로 한 일정계획 기법을 적용시켰다. 두 기법 모두 FT6 문제에서는 55로 최적해를 얻을 수 있었으며 FT10, FT20 문제에서는 각각 930, 1173으로 최적해와근접해를 구해낼 수 있었다.
SGA에서 사용한 연산자와 선택방법을 가지고 이종(異種) 섬모델 PGA도 제시하였다. 섬 모델 PGA에서 섬의 수는 단순히 집단 크기를 증가시키는 것보다 더 큰 효과를 얻을 수 있다.
교차율이 0.6, 0.7, 0.8일 경우, 선택확률이 0.7, 0.75, 0.8일 경우, 엘리티즘의 크기가 10, 20, 30일 경우에 대해 실험하였다. 돌연변이율은 0.
순서관계를 유지하면서 조금씩 개선시켜 나갈 수 있는 연산자가 필요하다. 그래서 순서 관계를 유지하고 이를 유전시킬 수 있는 교차 연산자를 개발하였다.
그리고 SGA는 집단 크기 200, 세대수 1000으로 하고, PGA는 2&PGA일 경우 집단 크기 100, 세대수 1000, 이주크기 10, 4S-PGA일 경우 집단크기 50, 세대수 1000, 이주크기 5로 하였다. 이전 연구자들이 한번의 실행에서 150, 000개에서 300, 000개의 염색체를 평가하고 있어, 200, 000개로 이전 연구자들과 비교 횟수를 맞추기 위해 이런 집단 크기와 세대수로 정하였다.
그리고 각 부 집단에 SGA에서의 유전 연산자와 선택방법을 적용한다. 두 부 집단이 50 세대 진행되면 동시에 일정 개체 수를 이주하도록 하였다. 4S-PGA에서는 4개로 분리된 초 기부 집단을 active', active, non-delay, random 스케쥴로 구성하여 각각의 부 집단에 SGA에서의 유전연산자를 적용하고, 2S-PGA와 같이 50세대 진행 후 이주하도록 하였다.
이 기법에서는 새로운 유전 연산자, 초기 모집단 구성방법을 사용한다. 또한 이기 법을 확장하여 병렬 유전 알고리즘을 기반으로 한 일정계획 기법을 제시한다.
일정계획 기법의 수행도를 평가하기 위해 먼저 가장 유명한 세 개의 벤치마크 문제 FT6X6, FT10X10와 FT20X5를 테스트하였다. 이들 FT 문제들은 제안되는 거의 모든 job shop 일정계획 기법들이 벤치마크 문제로 사용하고 있다.
본 연구에서는 JSSP를 위해 유전 알고리즘을 기반으로 한 일정계획 기법을 제안하였다. 제안한 일정계획 기법에서 표현은 공정의 순서를 job의 번호로 코드화 하여 항상 해가 실행 가능하도록 하였고, 이를 G&T 알고리즘과 연결하여 초기 모집단을 구성하였다. 그리고 교차 연산자와 돌연변이 연산자는 스케쥴에서 일시적인 관계를 보다 좋게 유전시키도록 하여 초기의 좋은 스케쥴이 계속 진화될 수 있도록 하였다.

대상 데이터

FT 문제는 제안되는 거의 모든 job shop 일정계획 기법들이 벤치마크 문제로 사용하고 있고, YN 문제는 가장 큰 규모의 벤치마크 문제라서 선택하였다. 실험에 사용한 컴퓨터는 팬티엄 !! 350, 메모리 64M의 기종을 사용하였다.

데이터처리

제시한 알고리즘에 적용할 교차율, 선택확률, 엘리티즘 크기는 FT10 문제에 하나의 초기 모집단을 구성하고, 파라미터에 따라 100번 실행하여 가장 좋은 값과 평균값을 얻어내는 값으로 하였다. 교차율이 0.

이론/모형

G&T 알고리즘으로 active, active; non-delay 스케쥴을 산출하여, 이 스케쥴들로 초기 모집단을 구성한다. active와 non-delay 스케쥴은 G&T 알고리즘을 이용하여 생성하고, active, 스케쥴은 단계 3에서 G집합을 구성하는 방법을 변형한 G&T 알고리즘을 사용한다. 그 알고리즘은 다음과 같다.
이로 인해 해를 찾는데 걸리는 시간은 길어지고 좋은 해를 찾을 가능성이 줄어든다. 본 연구에서는 값이 좋은 개체로 구성된 초기모집단을 생성시키기 위해 G&T 알고리즘을 사용한다. 모집단 구성에서 중요한 것은 다양성이라 할 수 있는데, G&T 알고리즘은 job shop 일정계획 문제에서 다양한 active 스케쥴을 가장 쉽게 산출할 수 있는 알고리즘이다.
돌연변이 연산자는 염색체에 변화를 주어 집단내의 다양성을 유지하기 위하여 사용한다. 본 연구에서는 이웃 탐색 기법에 근거한 돌연변이 연산자를 사용한다.<그림 2>는 돌연변이 연산의 예를 보여준다.
선택은 Brindle[l]이 제시한 경쟁선택을 사용한다. 경쟁선택은 집단으로부터 두 개의 개체들을 임의대로 선택한 다음, 난수「을 0과 1사이에서 발생시켜 만약 r<k이면 두 개의 개체 중 더 적합도가 높은 개체를 부모로 선택한다.
염색체의 생성은 Giffler & Thompson (G&T) 알고리즘[8]을 이용한다. G&T 알고리즘은 단계 4의 G 집합 내에 속해 있는 공정들을 하나씩 선택하는 과정을 전체 공정의 수만큼 수행하여스케쥴하게 되는데, 이때 하나씩 선택되어지는 공정을 포함하는 job의 번호를 선택 순서대로 전체 공정 수만큼 연결하여 기입함으로써 염색체가 생성된다.
제안알고리즘을 두 개의 유명한 벤치마크 문제, FT(Fisher & Thompson) 문제[12]와 YN 문제[15]에 적용한다. FT 문제는 제안되는 거의 모든 job shop 일정계획 기법들이 벤치마크 문제로 사용하고 있고, YN 문제는 가장 큰 규모의 벤치마크 문제라서 선택하였다.
한다. 표현은 공정 중심(operation-based) 표현 방법을 사용한다. 이는 job 번호를 공정의 수만큼 반복시키는 순열형태로 표현한다.

성능/효과

파라미터는 FT문제와 같이 하였다. 3개의 문제에서 제시한 일정계획 기법이 GA/GT 보다 우수한 것을 볼 수 있다. 그리고 PGA가 SGA 보다 우수함을 볼 수 있다.
제안한 일정계획 기법에서 표현은 공정의 순서를 job의 번호로 코드화 하여 항상 해가 실행 가능하도록 하였고, 이를 G&T 알고리즘과 연결하여 초기 모집단을 구성하였다. 그리고 교차 연산자와 돌연변이 연산자는 스케쥴에서 일시적인 관계를 보다 좋게 유전시키도록 하여 초기의 좋은 스케쥴이 계속 진화될 수 있도록 하였다. 이 기법을 표준 벤치마크 JSSP에 적용하여 좋은 결과들을 산출할 수 있었다.
FT 문제에 SGA, PGA를 기반으로 한 일정계획 기법을 적용시켰다. 두 기법 모두 FT6 문제에서는 55로 최적해를 얻을 수 있었으며 FT10, FT20 문제에서는 각각 930, 1173으로 최적해와근접해를 구해낼 수 있었다.<표 3>은 세 개의 FT 문제에서 이전의 연구에 의해 얻어진 최고의 결과들이다.
섬 모델 PGA에서 섬의 수는 단순히 집단 크기를 증가시키는 것보다 더 큰 효과를 얻을 수 있다. 본 연구에서 제시한 PGA를 기반으로 한 일정계획 기법은 벤치마크 문제에서 SGA을 기반으로 한 기법과의 비교를 통해 평균 해와 해의 개선을 확인할 수 있었다. 이는 조기 수렴의 문제를완화시켜 결과들을 개선하고, 더 적은 평가로도 SGA와 같은 수준의 결과를 얻을 수 있음을 보여주는 것이라 할 수 있다.
실험의 결과는 각 문제마다 새로운 초기 모집단으로 50번씩 수행하여 가장 좋은 해로 하였다. 그리고 SGA는 집단 크기 200, 세대수 1000으로 하고, PGA는 2&PGA일 경우 집단 크기 100, 세대수 1000, 이주크기 10, 4S-PGA일 경우 집단크기 50, 세대수 1000, 이주크기 5로 하였다.
그리고 교차 연산자와 돌연변이 연산자는 스케쥴에서 일시적인 관계를 보다 좋게 유전시키도록 하여 초기의 좋은 스케쥴이 계속 진화될 수 있도록 하였다. 이 기법을 표준 벤치마크 JSSP에 적용하여 좋은 결과들을 산출할 수 있었다. 이는 초기 모집단의 생성과 유전 연산자의 성공적인 통합을 의미하는 것으로 제시된 일정계획 기법의 효율성을 보여준다.

후속연구

이는 조기 수렴의 문제를완화시켜 결과들을 개선하고, 더 적은 평가로도 SGA와 같은 수준의 결과를 얻을 수 있음을 보여주는 것이라 할 수 있다. PGA를 기반으로 한 기법의 수행도는 이주 세대, 이주 크기, 이주 방법 등의 개선으로 인해 더 높아질 것으로 기대된다.
제안된 교차연산자는 먼저 임의구간을 산출한 뒤 그 구간 내 유전인자들을 부모 2에 삽입구간 시작위치 바로 앞이다. 만약 첫 번째 부모에서 임의 구한다.

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

연합인증

Job Shop 일정계획을 위한 병렬 유전 알고리즘
A Parallel Genetic Algorithms for lob Shop Scheduling Problems 원문보기

Abstract ▼ AI-Helper

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

후속연구

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

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

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

선택된 텍스트

연합인증

Job Shop 일정계획을 위한 병렬 유전 알고리즘 A Parallel Genetic Algorithms for lob Shop Scheduling Problems 원문보기

Abstract ▼ AI-Helper

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

문제 정의

가설 설정

제안 방법

대상 데이터

데이터처리

이론/모형

성능/효과

후속연구

이 논문을 인용한 문헌

저자의 다른 논문 :

박병주 (18) 김현수 (55)

관련 콘텐츠

원문 보기

원문 URL 링크

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

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

선택된 텍스트

Job Shop 일정계획을 위한 병렬 유전 알고리즘
A Parallel Genetic Algorithms for lob Shop Scheduling Problems 원문보기

AI 본문요약
AI-Helper