발간년도 : [2012]
| 논문정보 |
|
| 논문명(한글) |
[7권 5호] Job Shop 일정계획을 위한 semi active 스케쥴 기반 유전 알고리즘 |
|
| 논문투고자 |
김준우, 하성호 |
|
| 논문내용 |
Job Shop 일정계획 문제는 가장 잘 알려진 NP-hard 조합 최적화 문제 중의 하나로, 대수적인 방법으로 최적해를 구하는 것이 곤란하다. 이에 따라 유전 알고리즘이나 시뮬레이티드 어닐링, 타부 서치 등과 같은 확률적 탐색 기법들이 job shop 일정계획 문제 풀이에 많이 적용되었다. Job Shop 일정계획 문제 풀이를 위한 유전 알고리즘들은 일반적으로 active 스케쥴에 해당하는 해들로 구성된 세대를 유지하도록 설계되는데, 이는 최적해가 active 스케쥴에 포함되기 때문이다. 하지만 Giffler and Thompson 알고리즘과 같은 active 스케쥴 생성 방법은 종종 많은 계산을 요구한다는 점에서 효율적이지 못할 수 있다. 대신, 본 논문에서는 semi active 스케쥴에 기반한 유전 알고리즘인 sa-GA를 제안한다. sa-GA에서 해는 자연스러운 공정들의 나열로 나타내어지고, 이는 semi active 스케쥴로 손쉽게 전환된다. 또한, 보다 빠른 유전 연산이 가능하여 종래의 active 스케쥴 기반 GT/GA 알고리즘에 비해 효율적이다. 실험 결과, sa-GA 역시 해 집단에서 active 스케쥴에만 집중하여 최적해를 신속히 구할 수 있음을 볼 수 있었다. |
|
| 첨부논문 |
|
|
|
|
|
자료실 > 논문지 
