Task scheduling scheme for civil aviation information exchange
PAN Yu1,2,SONG Xueyan1,2,SUN Jizhou1,2
1. School of Computer Science and Technology, Tianjin University, Tianjin 300072, China;
2. Tianjin Key Laboratory of Cognitive Computation and Applications (Tianjin University), Tianjin 300072, China
In order to support the distributed transmission of a lot of tasks on the data exchange platform for civil aviation information, it needs to establish the efficient task scheduling algorithms and models. Based on the infrastructure and needs of the platform, after analyzing the existing task scheduling models and scheduling algorithms, a new task scheduling model was proposed to fulfill the data exchange on this platform. This model mapped the point-to-multipoint data transmission network to a Steiner tree problem with delay and bandwidth constraints, and an improved Genetic Algorithm (GA) was also proposed to solve the constrained Steiner tree problem. The results of comparative experiment with the maximum bandwidth allocation algorithm prove the validity and feasibility of the proposed model.
潘宇 宋雪雁 孙济洲. 民航信息交换任务调度方案[J]. 计算机应用, 2014, 34(5): 1507-1510.
PAN Yu SONG Xueyan SUN Jizhou. Task scheduling scheme for civil aviation information exchange. Journal of Computer Applications, 2014, 34(5): 1507-1510.
YANG J. How China faces significant changes in international AIS field [J]. China Civil Aviation, 2006, 71(11): 39-40. (杨京.中国如何面对国际AIS领域的重大变革[J].中国民用航空, 2006, 71(11): 39-40.)
[2]
BRUNK B K, POROSNICU E. A tour of the AIXM concept [C]// Proceedings of the 2004 ESRI International Users Conference. San Diego: [s.n.], 2004: 2190.
[3]
LI Y, WANG J. Research of flight procedure data sharing and exchanging technology XML-based [D]. Tianjin: Civil Aviation University of China, 2011. (李亚娟,王洁宁.基于XML的飞行程序数据共享与交换技术研究[D].天津:中国民航大学,2011.)
[4]
LIU Y, LIAN D. Design of task scheduling model of data exchange platform [J]. Journal of Chinese Computer Systems, 2013, 34(7): 1543-1546. (刘应明,廉东本.数据交换平台的任务调度模型设计[J].小型微型计算机系统, 2013, 34(7): 1543-1546.)
[5]
FENG J, QI D, QIAN Z. Job scheduling solution based on data exchange and synchronization [J]. Journal of Computer Applications, 2009, 29(11):3165-3170. (冯家耀,齐德昱,钱正平.基于数据交换与同步的作业调度方案[J].计算机应用,2009,29(11):3165-3170.)
[6]
LENSTRA J K, RINNOOY KAN A H G. An introduction to multiprocessor scheduling [J]. Qüestiió, 1981, 5(1): 49-57.
[7]
HOU E S H, ANSARI N, REN H. A genetic algorithm for multiprocessor scheduling [J]. IEEE Transactions on Parallel and Distributed Systems, 1994, 5 (2): 113-120.
[8]
TAURA K, CHIEN A A. A heuristic algorithm for mapping communicating tasks on heterogeneous resources [C]// HCW '00: Proceedings of the 9th Heterogeneous Computing Workshop. Washington, DC: IEEE Computer Society, 2000: 102-115.
[9]
WINTER P, ZACHARIASEN M. Euclidean Steiner minimum trees: an improved exact algorithm [J]. Networks, 1997, 30(3): 149-166.
[10]
GANLEY J L. Computing optimal rectilinear Steiner trees: a survey and experimental evaluation [J]. Discrete APPI Mathematics, 1999, 90(1/2/3): 161-171.
[11]
KARP R M. Reducibility among combinatorial problems [M]// Complexity of Computer Computations. New York: Plenum Press, 1972: 85-103.
[12]
MELZAK Z A. On the problem of Steiner [J]. Canadian Mathematical Bulletin, 1961, 4(2): 143-148.
[13]
PRFER H. Neuer beweis eines satzes über permutationen [J]. Archiv der Mathematik und Physik, 1918, 27: 142-144.
[14]
LUAN W. Multi-objective GA for the Steiner tree problem [D]. Shenyang: Northeastern University, 2008. (栾威.基于多目标遗传算法求解Steiner树问题[D].沈阳:东北大学,2008.)