Journal of the Korean Society for Aeronautical & Space Sciences (한국항공우주학회지)

The Korean Society for Aeronautical and Space Sciences (한국항공우주학회)
권호 표지
DOI QR코드

DOI QR Code

A Comparison of Scheduling Optimization Algorithm for the Efficient Satellite Mission Scheduling Operation

효율적인 위성 임무 스케줄링 운영을 위한 스케줄링 최적화 알고리즘 비교 연구

  • 백승우 (부산대학교 항공우주공학과 대학원) ;
  • 조겸래 (부산대학교 항공우주공학과, 기계기술연구원) ;
  • 이대우 (부산대학교 항공우주공학과, 기계기술연구원) ;
  • 김해동 (한국항공우주연구원 우주응용미래기술센터)
  • Received : 2009.11.21
  • Accepted : 2009.12.21
  • Published : 2010.01.01
Download PDF
⟨ Previous Next ⟩

Abstract

A comparison of two kinds of scheduling optimization algorithms is presented in this paper. As satellite control and operation techniques have been developed, satellite missions became more complicated and overall quantity of missions also increased. These changes require more specific consideration and a huge amount of computation for the satellite mission scheduling. Therefore, it is a good strategy to make a scheduling optimization algorithm for the efficient satellite mission scheduling operation. In this paper, two kinds of scheduling optimization algorithms are designed with tabu-search algorithm and genetic algorithm respectively. These algorithms are applied for the same mission scenario and the results of each algorithm are compared and analyzed.

본 논문에서는 위성 임무 스케줄링을 효율적으로 수행하기 위한 스케줄링 최적화 알고리즘을 타부탐색 알고리즘과 유전 알고리즘을 이용해 디자인하고, 시뮬레이션을 수행한 비교 결과를 기술하였다. 위성 임무 스케줄링은 위성에게 요구된 작업들과 그에 따른 제한사항 및 다양한 변수들을 종합적으로 고려하여 상호간의 시간, 조건 등의 충돌을 회피함과 동시에 위성의 자원을 최대한 활용하여 운용할 수 있는 최적의 작업시간표를 생성하는 것이다. 위성 임무 스케줄링은 동시에 많은 변수를 고려해야 하기 때문에 연산양이 많고, 매 스케줄링 시 마다 동일한 과정을 반복적으로 수행해야 하므로, 스케줄링 최적화 알고리즘과 같은 위성 운영 자동화, 자율화가 요구되는 분야이다. 다양하게 이용되고 있는 두 가지 스케줄링 기법을 위성 임무 스케줄링 최적화에 적용해 보았다.

Keywords

References

  1. 최수미, “우주분야 연구개발 및 산업동향”, 한국항공우주연구원, 항공우주산업기술동향 제 6권 1호, 2008. pp. 3-13.
  2. 김해동, 최해진, 김은규, “다목적 실용위성 1호의 임무계획 및 운영”, 한국항공우주학회지 제 29권 7호 pp. 118-126.
  3. 김해동, 최해진, 김은규, “다목적 실용위성 1호의 임무계획 및 자동 명령계획표 생성기 개발”, 한국항공우주학회지, 제 30권 1호, pp.139-146.
  4. Daryl G. Boden and Wiley J. Larson, Cost-Effective Space Mission Operation, McGraw-Hill, Inc. 1996.
  5. Seung-woo Baek, Kyeum-rae Cho, Dae-woo Lee, Peter M. Bainum and Hae-dong Kim, "Development of Scheduling Algorithm and GUI for the Autonomous Satellite Mission Operation", 60th International Astronautical Congress, Daejeon, Korea, Oct. 2009.
  6. Seung-woo Baek, Kyeum-rae Cho, Dae-woo Lee, Peter M. Bainum and Hae-dong Kim, "Heuristic Approach for Satellite Mission Scheduling", 19th AAS-AIAA Space Flgith Mechanics Meeting, Savannah, Georgia, U.S.A., Feb. 2009.
  7. Byung-Sun Lee and Jae-Hoon Kim, "Design and Implementation of the Mission Planning Functions for the KOMPSAT-2 Mission Control Element", Journal of Astronomy and Space Science, Vol. 20, No. 3, 2003, pp. 227-238. https://doi.org/10.5140/JASS.2003.20.3.227
  8. Kalyanmoy Deb, Multi-Objective Optimization using Evolutionary Algorithms, John&Sons, Ltd., 2001.
  9. Paula Moss, Bruce Baker, Deepak Khosla, and Alex Dow, "Multi-mission Prioritization Using Cost-based Mission Scheduling", 11th International Command and Control Research and Technology Symposium, Cambridge, UK, Sep. 2006.
  10. Oscar H. Ibarra and Chul E. Kim, "Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems", Journal of the ACM (JACM), Vol. 22, No. 4, 1975.
  11. Maya Hristakeva and Dipti Shrestha, "Different Approaches to Solve the 0/1 Knapsack Problem", 38th Midwest Instruction and Computing Symposium, Apr. 2005.
  12. Michel Gendreau, "An Introduction to Tabu Search", International Series in Operations Research and Management Science, Vol. 57. Springer New York, 2003.
  13. Glover, F., "Tabu Search - Part I", ORSA Journal on Computing 1, 190-206. 1989. https://doi.org/10.1287/ijoc.1.3.190
  14. Glover, F. (1990), "Tabu Search - Part II", ORSA Journal on Computing 2, 4-32. https://doi.org/10.1287/ijoc.2.1.4
  15. Wei-Chen Lin, Da-Yin Liao, "A Tabu Search Algorithm for Satellite Imaging Scheduling", Proceedings of IEEE International Conference on Systems, Man and Cybernetics, pp.1601-1606, 2004.
  16. Michel Vasquez, Jin-Kao Hao, "A "Logic-Constrained" Knapsack Formulation and a Tabu Algorithm for the Daily Photograph Scheduling of an Earth Observation Satellite", Computational Optimization and Applications, 2001.
  17. 진강규, 유전알고리즘과 그 응용, 교우사, 2004.
  18. 문병로, 쉽게 배우는 유전알고리즘, 한빛미디어, 2008.
  19. 백승우, 한순미, 조겸래, 이대우, 김해동, "유전알고리즘을 이용한 전술위성 임무계획 스케줄링", 한국군사과학기술학회, 종합학술대회 논문집, 2008.
  20. 한순미, 백승우, 조선영, 조겸래, 이대우, 김해동, "유전 알고리즘을 이용한 위성 임무 스케줄링 최적화", 한국항공우주학회지, Vol. 36, No. 12, 2008, pp. 1163-1170. https://doi.org/10.5139/JKSAS.2008.36.12.1163

Cited by

  1. Development of Image Collection Planning Optimization Using Heuristic Method vol.28, pp.4, 2012, https://doi.org/10.7780/kjrs.2012.28.4.9
  2. Optimization-Based Scheduling Method for Agile Earth-Observing Satellite Constellation vol.15, pp.11, 2018, https://doi.org/10.2514/1.I010620
  3. Schedule Optimization of Imaging Missions for Multiple Satellites and Ground Stations Using Genetic Algorithm vol.19, pp.1, 2018, https://doi.org/10.1007/s42405-018-0011-9
  4. A Mathematical Model for Optimal Communication Scheduling between Multiple Satellites and Multiple Ground Stations vol.41, pp.1, 2018, https://doi.org/10.11627/jkise.2018.41.1.039