EFFICIENT ALGORITHMS FOR SS/TDMA SCHEDULING

This paper presents efficient scheduling algorithms for the slot assignment problem in a satellite-switched time-division multiple-access (SS/TDMA) system. This problem is translated into a modified openshop scheduling problem, allowing the use of known optimal algorithms. Their complexity is expressed as a function of the following parameters: the number of nonzero entries in the demand matrix, the number of uplinks and the number of downlinks. According to the values of these parameters, the algorithm with the lowest computational complexity can be adopted. While drastically reducing the computational complexity of previously published algorithms, simulation results evidence that the produced results in terms of the assignment duration and the number of switching matrices are close to previously presented solutions.