Welcome to Journal of Beijing Institute of Technology
Advance Search
Volume 25Issue 3
.
Turn off MathJax
Article Contents
Article Navigation> JOURNAL OF BEIJING INSTITUTE OF TECHNOLOGY> 2016> 25(3): 382-391
LIN Peng, KUANG Lin-ling, CHEN Xiang, YAN Jian, LU Jian-hua, WANG Xiao-juan. Generalized multiple time windows model based parallel machine scheduling for TDRSS[J]. JOURNAL OF BEIJING INSTITUTE OF TECHNOLOGY, 2016, 25(3): 382-391. doi: 10.15918/j.jbit1004-0579.201625.0311
Citation: LIN Peng, KUANG Lin-ling, CHEN Xiang, YAN Jian, LU Jian-hua, WANG Xiao-juan. Generalized multiple time windows model based parallel machine scheduling for TDRSS[J].JOURNAL OF BEIJING INSTITUTE OF TECHNOLOGY, 2016, 25(3): 382-391.doi:10.15918/j.jbit1004-0579.201625.0311
shu

Generalized multiple time windows model based parallel machine scheduling for TDRSS

doi:10.15918/j.jbit1004-0579.201625.0311
  • 1.

    Department of Electronic Engineering, Tsinghua University, Beijing 100084, China;China Electronic Equipment of System Engineering Institute, Beijing 100141, China

  • 2.

    Tsinghua Space Center, Tsinghua University, Beijing 100084, China

  • 3.

    Department of Electronic Engineering, Tsinghua University, Beijing 100084, China;Tsinghua Space Center, Tsinghua University, Beijing 100084, China

  • 4.

    China Electronic Equipment of System Engineering Institute, Beijing 100141, China

  • Received Date:2014-10-25
    Abstract
  • The scheduling efficiency of the tracking and data relay satellite system (TDRSS) is strictly limited by the scheduling degrees of freedom (DoF), including time DoF defined by jobs' flexible time windows and spatial DoF brought by multiple servable tracking and data relay satellites (TDRSs). In this paper, a generalized multiple time windows (GMTW) model is proposed to fully exploit the time and spatial DoF. Then, the improvements of service capability and job-completion probability based on the GMTW are theoretically proved. Further, an asymmetric path-relinking (APR) based heuristic job scheduling framework is presented to maximize the usage of DoF provided by the GMTW. Simulation results show that by using our proposal 11% improvement of average job-completion probability can be obtained. Meanwhile, the computing time of the time-to-target can be shorten to 1/9 of the GRASP.
    • FullText(HTML)
  • loading
    • References (15)
  • [1]
    Rojanasoonthon S, Bard J F. A GRASP for parallel machine scheduling with time windows [J]. Informs Journal on Computing, 2005, 17(1): 32-51.
    [2]
    Fang Y S, Chen Y W, Gu Z X. CSP model of the relay satellite scheduling [J]. Journal of National University of Defence Technology, 2005, 27(1): 6-10. (in Chinese)
    [3]
    Fang Y S, Chen Y W. Constraint programming model of tdrss single access link scheduling problem[C]//International Conference on Machine Learn-ing and Cybernetics, Dalian, China, 2006.
    [4]
    Zhang Y, Sun Z J, Li J. Study of TDRS dynamic scheduling problem [J]. Journal of System Simulation, 2011, 23(7): 1464-1468. (in Chinese)
    [5]
    Bard J F, Rojanasoonthon S. A branch-and-price algorithm for parallel machine scheduling with time windows and job priorities [J]. Naval Research Logistics, 2006, 53(1): 24-44.
    [6]
    Rojanasoonthon S, Bard J F, Reddy S D. Algo-rithms for parallel machine scheduling: a case study of the tracking and date delay satellite system [J]. Journal of the Operational Research Society, 2003, 54(1): 806-821.
    [7]
    Abramson N. The aloha system: another alternative for computer communications[C]//Proceedings of the Fall 1970 AFIPS Computer Conference, New York, USA, 1970.
    [8]
    Jewett J, Shrago J, Yomtov B. Designing optimal voice networks for businesses, government, and telephone companies[R]. California: Telephony Publishing Corp., 1980.
    [9]
    Kershenbaum A. Telecommunications network de-sign algorithms[R]. New York: McGraw-Hill, 1993.
    [10]
    Zeng G P. On convergence of the extended erlang-B model [J]. Mathematical and Computing Modelling, 2010, 52(1): 128-133.
    [11]
    Lin P, Kuang L L, Chen X, et al. Adaptive subsequence adjustment with evolutionary asymmetric path-relinking for TDRSS scheduling [J]. Journal of Systems Engineering and Electronics, 2014, 25(5): 800-810.
    [12]
    Feo T A, Resende M G C. Greedy randomized adaptive search procedures [J]. Journal of Global Optimization, 1995, 6(1): 109-133.
    [13]
    Rojanasoonthon S. Parallel machine scheduling with time windows[D]. Austin, United States: University of Texas, 2003.
    [14]
    Aiex R M, Resende M G C, Ribeiro C C. Probability distribution of solution time in GRASP: an experimental investigation [J]. Journal of Heuris-tics, 2002, 8(3): 343-373.
    [15]
    Aiex R M, Resende M G C, Ribeiro C C. TTT plots: a perl program to create time-to-target plots [J]. Optimization Letters, 2007, 1(4): 355-366.
    • Relative Articles
  • Supplements (0)
  • Cited By
  • 加载中

Catalog

    通讯作者:陈斌, bchen63@163.com
    • 1.

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索
    Get Citation
    PDF
    XML

    Article Metrics

    Article views (972) PDF downloads(866) Cited by()
    Proportional views
    Related

    Address:5 Zhongguancun South Street, Haidian District, Beijing

    Tel:86-10-68914374

    Email:blgywb@bit.edu.cn

    Copy Right © Journal of Beijing Institute of Technology

    Supported by:Beijing Renhe Information Technology Co. Ltd

    /

      Return
      Return
        Baidu
        map