선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 더미 액티비티인 1과 n에 대한 액티비티 소요시간은 d1 = dn = 0 이며 필요한 자원 또한 0이다. RCPSP 문제는 각 액티비티들이 선행 제약조건과 자원제약조건을 만족시키면서 수행되어 모든 액티비티들이 완료되는데 걸리는 시간을 최소화 하는 것을 목표로 한다.
- 연구 초기에는 수학적 논리를 적용한 결정론적인 방법으로 해결하려 노력하였으나, Blazewicz [2]에 의해 RCPSP가 NP-hard 문제임이 알려진 이후에는 발견적 (Heuristics, 휴리스틱) 기법으로 해결하려는 노력이 많이 이루어져 왔다 [3]. 본 논문에서는 대표적인 메타 휴리스틱 기법 중에 하나인 유전알고리즘을 이용하여 RCPSP를 해결하기 위한 효율적인 유전 연산자 및 선택전략을 소개하고, 기존 알고리즘과 비교를 통해 우수성을 보여주고자 한다.
- 본 논문에서는 자원 제약이 있는 프로젝트 스케줄링 문제를 효율적으로 해결할 수 있는 새로운 진화 알고리즘을 제안하였다. 제안하는 알고리즘은 스키마 이론을 바탕으로 하여 부모의 공통 유전자 블록을 자손에게 전달할 수 있는 교차 연산자와 현실 세계의 스포츠 토너먼트 제도를 본 딴 실세계 토너먼트 선택전략을 적용하였다.
- 첫 번째는 무작위로 만들어진 해에 보정 (Repair) 연산을 하는 것이고, 두 번째는 항상 제약 조건을 만족하는 해를 만들어 내는 초기화 전략을 사용하는 것이다. 본 논문에서는 초기 해집단 생성시 단일 패스 전략을 사용하여 항상 유효한 해를 만들도록 하였다 [6]. 해 표현을 해석하여 일정 계획을 세울 때 염색체의 첫 번째 액티비티 부터 시작하여 오른쪽으로 하나씩 채워 나감으로써 프로젝트 스케줄링이 이루어진다.
- 이러한 문제점을 보완하기 위하여 본 논문에서는 John Holland가 GA의 탐색 능력을 설명할 때 거론한 스키마 이론 [4]에 기반한 효율적인 교차 연산자를 제안한다. [그림 2]는 본 논문에서 제안하는 ‘스키마 교차’에 대한 내용을 보여주고 있다.
- 다윈의 적자생존 법칙에 입각한 GA의 선택전략을 적용하려면 해집단에 대한 평가가 선행되어야만 한다. 해에 대한 평가는 염색체를 디코드하여 문제에서 최적화 하고자 하는 목적에 본 염색체가 얼마만큼의 값을 가지는지 계산하는 것이다. RCPSP 문제에서 평가는 염색체로부터 해석하여 구해진 프로젝트 완료 시간 값이 된다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.