혼합유전알고리즘을 이용한 flow Shop 일정계획문제에 관한 연구

국문 초록 (Abstract)

일정계획 문제를 포함한 공학설계에 있어서 최적해를 얻기 위한 방법중의 하나로 최적화방법이 많이 사용되어 왔다. 최적해를 효과적으로 얻기 위한 여러 가지 노력이 있어 왔으나, 아직까지 모든 문제에 효과적으로 적용할 수 있는 알고리즘은 개발되지 않고 있다. 일반적으로 사용되는 최적화 기법들은 각각의 장단점이 있겠지만, 이들 기존의 최적화기법들을 사용하는데 있어서 가장 큰 문제점으로는 얻어진 최적점이 국부 최적점일 가능성이 많다는 것이다. 따라서 설계자는 설계변수의 출발점, 탐색의 폭 및 중단조건 등을 바꾸어 가면서 최적화를 수행한 후, 이들 값들을 비교하여 최적점을 검증하는 과정을 걸쳐야만 하였다. 본 연구에서는 이러한 불편함을 없애고 탐색의 효율성을 높이기 위하여 insertion method로 초기해를 생성하고 이 초기해의 개선을 위해 최근 활발한 연구가 수행되고 있는 유전알고리즘을 혼용시키는 방법에 관하여 기술하였다. 이 방법은 일정계획과 같은 순서 문제의 국부탐색에 효율적인 insertion method와 국부적인 최적점에 빠질 가능성이 적은 유전알고리즘을 연결·수행하여 탐색시간을 줄이고 전체적인 최적점을 보다 효율적으로 얻을 수 있도록 하였다.
또한 본 연구에서 개발한 혼합 유전알고리즘의 효용성을 측정하고 이렇게 구현된 혼합 최적화방법의 유용성을 검증하기 위하여 기존의 전통적 flow shop 일정계획문제에 대한 휴리스틱 중 가장 우수한 NEH 휴리스틱 기법과 전통적 유전알고리즘을 비교대상으로 하여, 가공시간에 대한 많은 제 문제를 발생시켜 최대가공시간과 평균가공시간, 최대가공시간에 있어서 비교된 알고리즘의 우위 횟수 등을 총 작업소요시간(makespan)을 기준으로 그 효용성을 비교하였는데, 계산 결과에 의하면 혼합 유전알고리즘이 flow shop 일정계획 문제에 대해 더 효율적인 것으로 입증되었다. 이것은 실제 문제에 있었어도 혼합 유전알고리즘을 쉽게 적용시킬 수 있음을 뜻한다. 이밖에 혼합 유전알고리즘을 기초로 한 휴리스틱은 Np-hard 문제를 증명하는데 있어서 전체 흐름시간, 최대 지연 시간, 전체 지연 시간 등과 같은 다른 기준으로 flow shop 문제를 푸는데도 쉽게 확장시킬 수 있을 것이며 flow shop 보다 더 일반적이고 복잡한 job shop 일정계획 문제 등에도 적용 가능할 것이다.

다국어 초록 (Multilingual Abstract)

The optimal method is used to get optimal solution in engineering design including scheduling problems. While lots of efforts have been made to obtain optimal solution effectively, algorithm has not been yet developed, which can be applied to all problems.
Generally optimal methods have good points and bad points but the big problem in applying current optimal method is that there are lots of possibilities to get local optimal point. So designers have to optimalize changes the starting point of design variable, the depth of search and the conditions of stop and then they should verify optimal point.
This study is to get rid of the inconvenience and produce initial solution as insertion method for promoting effectiveness of search and describe the way that mixes genetic algorithm which has been studying to improve this initial solution.
This method is to connect efficient insertion method to search sequencing problems like scheduling problems locally and genetic algorithm which has a little chance to get local optimal point and then lessen searching time and obtain global optimal point move efficiently.
Also in order to survey the effectiveness of hybrid genetic algorithm developed in this study and verify the actualized hybrid optimal method, this these has compared the best NEH heuristic method of current traditional flow shop scheduling problems in heuristic with traditional genetic algorithm and caused lots of problems in processing time and made a comparison of the effectiveness of better frequency of algorithm in maximum processing time, and average processing time using a criterion of makespan. It is proved that hybird genetic algorithm is more effective in flow shop scheduling problems by the result.
This means that hybrid genetic algorithm can be applied to real problem more easily Heuristics based on hybrid genetic algorithm also can be expanded easily to solve How shop problems in proving NP-hard problems using a different criterion like total flow time, maximum tardiness and total tardiness and moreover, applied to job shop scheduling problems which are more general and complex than flow shop.

목차 (Table of Contents)

• 목차 = ⅲ
• Ⅰ. 서론 = 1
• 1. 연구목적 = 1
• 2. 연구 방법 및 범위 = 2
• Ⅱ. 유전알고리즘에 의한 최적 탐색법 = 5
• 1. 개념 = 5
• 2. 구성요소 = 7
• 3. 특성 = 9
• 4. 유전연산자 = 10
• 5. 다른 기법들과의 비교 = 17
• Ⅲ. 유전 알고리즘을 이용한 flow shop 일정계획 = 22
• 1. 개요 = 22
• 2. Two - Machine flow shop문제 = 23
• 3. 일반적인 m대의 기계 문제에 대한 휴리스틱 = 24
• 4. flow shop 일정계획 문제에 대한 접근법 = 28
• Ⅳ. flow shop 일정계획문제를 위한 혼합유전알고리즘 = 36
• 1. 혼합유전알고리즘의 필요성 = 36
• 2. 일정 계획 문제를 위한 혼합유전알고리즘 = 39
• 3. 수치적용 = 44
• 4. 비교분석 몇 실험 결과 = 45
• Ⅴ. 결론 = 49
• 참고문헌 = 50
• ABSTRACT = 54