초록 ▼

본 연구에서는 GA를 가장 어려운 조합 최적화 문제 중의 하나인job shop 스케쥴링에 적용하였다. Job shop 스케쥴링 문제는 다양한 응용 분야를 가지고있어서 여러 가지 최적화 방법이 많이 제안 되었으나, 문제 특성이 복잡하여 좋은 해를 구하는 것이 어렵다. 최근 유전 알고리즘을 사용하여 최적화를 푸는 방법이 널리 사용되고있으나, 기존의 GA를 사용한 기법들은 문제의 특성을 파악하지 않은 상태로 GA를 이용하였기에 성능이 떨어지는 결과를 낳았다. 본 연구에서는 문제 특성을 이용한 표현 방식과적절한 교차,

본 연구에서는 GA를 가장 어려운 조합 최적화 문제 중의 하나인job shop 스케쥴링에 적용하였다. Job shop 스케쥴링 문제는 다양한 응용 분야를 가지고있어서 여러 가지 최적화 방법이 많이 제안 되었으나, 문제 특성이 복잡하여 좋은 해를 구하는 것이 어렵다. 최근 유전 알고리즘을 사용하여 최적화를 푸는 방법이 널리 사용되고있으나, 기존의 GA를 사용한 기법들은 문제의 특성을 파악하지 않은 상태로 GA를 이용하였기에 성능이 떨어지는 결과를 낳았다. 본 연구에서는 문제 특성을 이용한 표현 방식과적절한 교차, 변이 연산자를 사용하여 빠른 계산 시간 내에 좋은 스케쥴을 찾을 수 있었다.특히 job shop 문제의 특성을 고려하여 두 가지의 표현 방식을 이용하여 새로운 교차 연산자인 ASCX와 변이 연산자를 제안하였다.제안된 알고리즘의 성능을 평가하기 위해서 많은 Job shop 스케쥴링 문제에 대해 다른 최적화 방법과 비교를 수행하였다. 제안된 GA 방법은 기존의 일반적인 GA 보다 우수한 성능을 가지고 있으며, PBX 방식 보다도 우수함을 보였다. 또한 범용적으로 널리 사용되고 있는 Simulated annealing기법과의 비교를 통하여, 상대적인 성능 평가를 수행하였다.이 실험 결과를 통하여 제안한 GA 접근 방식이 기존의 몇몇 GA 접근 방식보다 월등한 성능 향상을 이루었으며, operation research를 기반으로 한 전문 기법과의 성능 차를 상당히 줄였다. Job shop 스케쥴링 문제는 실제로 산업계에서 응용 가치가 높은 문제이기에, 이를 최적화 하는 알고리즘은 높은 응용성을 가질 것으로 기대된다. 앞으로 다양한 많은 문제에서 평가와 병행해서 GA 접근 방식의 성능 향상을 위한 연구가 필요하다. GA접근 방식의 성능 향상을 위한 3가지 방향으로의 연구가 진행 중이다. 하나는 GA 자체의찾기 기능 향상이고 다른 하나는 GA를 기존의 전문화된 기법과의 결합(hybrid)하는 것이다.마지막으로 job shop 문제의 특성, 특히 최적해 찾기의 어려운 정도를 평가하고자 하는 연구도 진행 중이다.

Abstract ▼

In this research, we used GA(Genetic Algorithms) for solvingthe JSSP(job shop scheduling problem), one of the most difficult problem in search area.Many previous researches suggested various optimization algorithms for JSSP becauseit can be applied to many profitable applications. As the proble

In this research, we used GA(Genetic Algorithms) for solvingthe JSSP(job shop scheduling problem), one of the most difficult problem in search area.Many previous researches suggested various optimization algorithms for JSSP becauseit can be applied to many profitable applications. As the problem is considered to behard, finding the good solution for JSSP is difficult. Recently many researchers haveused a GA as a tool for solving the optimization problem but using GA directly to JSSPusually fail to find good solution and proved to be inferior to deterministic algorithmsbecause it does not use the characteristics of JSSP. We used two representationmethods for represent the JSSP characteristics and used appropriate crossover andmutation operators for finding good solution in a short time. Especially we suggest anew crossover technique - ASCX(active schedule constructive crossover)- and showedthat our approach do a work well by simulation test.We did many comparisons with other optimization algorithm in various problem forshowing the performance of our algorithm. Suggested GA is superior to previous GAtechniques and shows that it outperforms the PBX method. We also compared thesuggested GA to SA(Simulated Annealing), a well known powerful search algorithm,and confirm that suggested GA works well in many JSSPs.We made a good algorithm for JSSP by using a new crossover and appropriaterepresentation of GA and increased the performance much. As the JSSP has manyindustrial applications, we expect our optimization algorithm can be used for many areas.We also expect that our method can be applied for other combinatorial optimizationproblem besides JSSP. There are three approaches for increasing the performance ofJSSP optimization. One is increasing the GA performance itself - increasing thesearching power of the GA. The second approach is hybridization of other specializedalgorithm. The third is measuring the difficulty of JSSP and applying that informationto GA.

목차 Contents

• 1. 서론...7
• 1.1 연구 배경...7
• 1.2 연구의 중요성 및 목적...8
• 2. 연구 방법 및 이론...10
• 2.1 Job shop scheduling problem(JSSP)...10
• 2.2 JSSP에 대한 GA 접근 방식...13
• 2.3 JSSP에 대한 새로운 GA 접근 방식...14
• 3. 결과...23
• 3.1 기존의 GA와 제안된 GA 사이의 성능 비교...23
• 3.2 SA와 제안된 GA의 성능 비교...27
• 4. 고찰...30
• 5. 결론...33
• 6. 인용문헌...34
• 7. 부록 : ASCX 알고리즘...37
• 8. 연구수행관련 논문발표 목록...38
• 9. 자체평가서...39