Job Shop 일정계획을 위한 semi active 스케쥴 기반 유전 알고리즘 (Semi-active Schedule based Genetic Algorithm for Job Shop Scheduling)

서지정보

· 발행기관 : 한국지식정보기술학회
· 수록지 정보 : 한국지식정보기술학회 논문지 / 7권 / 5호 / 1 ~ 10페이지
· 저자명 : 김준우, 하성호

초록

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 스케쥴에만 집중하여 최적해를 신속히 구할 수 있음을 볼 수 있었다.

영어초록

Job Shop scheduling problem is one of the most well-known NP-hard combinatorial optimization problems, and it is hard to obtain the optimal solution via numerical methods. Accordingly, probabilistic search methods such as genetic algorithm, simulated annealing and tabu search have been widely applied for solving Job Shop scheduling problems. In general, geneticalgorithms for Job Shop scheduling are designed to maintain a population consisted of active schedules, because the optimal schedules are included in the active ones. However, methods for generating active schedules such as Giffler and Thompson algorithm can be inefficient in that they are often computationally intensive. Instead, this paper proposes a semi active schedule based genetic algorithm called sa-GA. In sa-GA, a solution is represented as a natural permutation of operations, which is easily transformed into a semi active schedule. In addition, the genetic operations can be performed more quickly, and these aspects make sa-GA more efficient than the traditional active schedule based genetic algorithms. The experiment results show that sa-GA also concentrates on the active schedules in the population, and the optimal schedules can be obtained quickly.

참고자료

· 없음