Efficient algorithms for SS/TDMA scheduling

Abstract

Efficient scheduling algorithms for the slot assignment problem in a satellite-switched time-division multiple-access (SS/TDMA) system are presented. This problem is translated into a modified open-shop 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. Although the computational complexity of previously published algorithms is drastically reduced, simulation results show that the results are close to previously presented solutions in terms of the assignment duration and the number of switching matrices.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>