통신위성 일정계획 문제의 다항시간 알고리즘

다국어 초록 (Multilingual Abstract)

This paper deals with the time slot assignment problem (TSAP) that a satellite switches to traffic between n ground stations using on-board switching modes in SS/TDMA time-division technology. For this problem, there is only in used the mathematical approach as linear programming (LP) because there has been unknown the polynomial time algorithm to solve the optimal solution thus this problem classified by NP-hard. In this paper we suggest the heuristic algorithm with O (n²) time complexity to solve the optimal solution for this problem. Firstly, the proposed algorithm sets the lower bound (LB) that is a maximum sum of traffic of rows or columns to makespan in n × n d<SUB>ij</SUB>∈D traffic matrix for n ground stations, and transforms the D matrix to D<SUB>LB</SUB>  traffic matrix that all rows and columns sum have LB. Secondly, we select the maximum traffic of row and column in D<SUB>LB</SUB> , then decides the duration of kth switch mode to minimum traffic from selected values. The proposed algorithm can be get the optimal solution for all of experimental data.

참고문헌 (Reference)

1 이상운, "동종처리기계의 총 작업소요시간 최소화 알고리즘" 한국정보기술학회 12 (12): 123-130, 2014

2 M. Edvall, "Publicity Campaign" Tomlab Optimization Inc

3 G. Maral, "Performance of Fully Variable Demand Assignment SS/TDMA Satellite Systems" 5 (5): 279-290, 1987

4 J. P. Jue, "Optical networks" Kluwer Academic Publishers 99-122, 2001

5 T. Gonzalez, "Open-Shop Scheduling to Minimize Finish Time" 23 (23): 665-679, 1976

6 S. Martello, "Jenö Egerváry: From the Origins of the Hungarian Algorithm to Satellite Communication" 18 (18): 47-57, 2010

7 K. L. Yeung, "Efficient Time Slot Assignment Algorithms for TDM Hierarchical and Nonhierarchical Switching Systems" 49 (49): 351-359, 2001

8 D. L. Adamy, "EW 102: A Second Course in Electronic Warfare, Chapter 7: Communication Satellite Links" Horizon House Publications, Inc 2004

9 C. Guéret, "Applications of Optimization with Xpress-MP: 12.5 Scheduling of Telecommunications via Satellite" Dash Optimization Ltd. 185-190, 2005

10 X. Wan, "An Optimal Algorithm for Time-slot Assignment in SS/TDMA Satellite Systems" 1-6, 2013

11 T. H. Lee, "An Integer Programming Approach to the Time Slot Assignment Problem in SS/TDMA Systems with Intersatellite Links" 135 (135): 57-66, 2001

12 T. Inukai, "An Efficient SS/TDMA Time Slot Assignment Algorithm" COM-27 (COM-27): 1449-1455, 1979

13 D. Werra, "A Note on SS/TDMA Satellite Communication" 135 : 69-77, 1990

14 G. Rote, "A Heuristic for Decomposing Traffic Matrics in TDMA Satellite Communication" 38 (38): 281-307, 1993