Job Shop 일정계획을 위한 semi active 스케쥴 기반 유전 알고리즘
Semi-active Schedule based Genetic Algorithm for Job Shop Scheduling
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
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 스케쥴에만 집중하여 최적해를 신속히 구할 수 있음을 볼 수 있었다.
Abstract
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.
참고문헌 (23)
- 이승정, "생산 시스템 효율성 향상을 위한 적응형 일정계획 플랫폼 개발", 한국산업정보학회논문지, 16(2), pp.73~83 (2011), 한국산업정보학회
- 배상윤, "Job Shop 일정계획의 성능 향상을 위한 할당규칙의 정보", 산업경영시스템학회지, 29(4), pp.107~112 (2006), 한국산업경영시스템학회
- Cheng, R., "A Tutorial Survey of Job-shop Scheduling Problems using Genetic Algorithms - I. Representation", Computers and Industrial Engineering, 30(4), pp.983~997 (1996)
- Qing-dao-er-ji, "An Improved Genetic Algorithm for Job Shop Scheduling Problem", Proceedings of the 2010 International Conference on Computational Intelligence and Security (2010)
- 정종백, "A Development of Hybrid Genetic Algorithms for Classical Job Shop Scheduling", 대한산업공학회, 2000, ~
- 박병주, "A Hybrid Genetic Algorithm for Job Shop Scheduling", 한국경영과학회지, 26(2) (2001)
- 김여근, "Meta Heuristic" (1997), 영지문화사
- Holland, J. H., "Genetic Algorithm", Scientific American, 266, pp.44~50 (1992)
- Li, Y., "A Genetic Algorithm for Job-Shop Scheduling", Journal of Software, 5(3) (2010)
- 박병주, "유전알고리즘에 기반한 Job Shop 일정계획 기법", 경영과학, 20(1), pp.51~64 (2003), 한국경영과학회
- Yamada, T., "A Genetic Algorithm Applicable to Large-scale Job-Shop Problems", Parallel Problem Solving from Nature, 2, pp.281~290 (1992)
- Giffler, B., "Algorithms for Solving Production-Scheduling Problems", Operations Research, 8(4), pp.487~503 (1960)
- Lee, H.P., "A Modified Giffler and Thompson Genetic Algorithm on the Job Shop Scheduling Problem", MATEMATIKA, 22(2), pp.91~107 (2006)
- Poon, P.W., "Genetic Algorithm Crossover Operators for Ordering Applications", Computers and Operations Research, 22(1), pp.135~147 (1995)
- Cheng, R., "A Tutorial Survey of Job-shop Scheduling Problems using Genetic Algorithms, Part II: Hybrid Genetic Search Strategies", Computers and Industrial Engineering, 36(2), pp.343~364 (1999)
- Abdelmaguid, T.F., "Representations in Genetic Algorithm for the Job Shop Scheduling Problem: A Computational Study", Journal of Software Engineering and Applications, 3(12), pp.155~1162 (2010)
- Lestan, Z., "Solving the Job-shop Scheduling Problem with a Simple Genetic Algorithm", International Journal of Simulation Modelling, 8(4), pp.197~205 (2009)
- Chen, Y., "The Improved Genetic Algorithm for the Complex Job-shop Scheduling", Proceedings of the 2010 IEEE 17th International Conference on Industrial Engineering and Engineering Management, pp.609~614 (2010)
- Zhang, G., "An Effective Genetic Algorithm for the Flexible Job-shop Scheduling Problem", Expert Systems with Applications, 38(4), pp.3563~3573 (2011)
- Nakano, R., "Conventional Genetic Algorithms for Job Shop Problems", Proceedings of the 4th International Conference on Genetic Algorithms, pp.474~479 (1991)
- Bierwirth, C., "A Generalized Permutation Approach to Job Shop Scheduling with Genetic Algorithms", OR-Spektrum, 17(213), pp.87~92 (1995)
- 이건명, "A Genetic Algorithm for General Machine Scheduling Problems", KES, pp.60~66 (1998)
- 이혜리, "서열순서화 문제와 Job Shop 문제에 대한 선행관계유지 유전 연산자의 비교", 한국지능시스템학회 논문지, 14(5), pp.563~570 (2004), 한국지능시스템학회