Efficient algorithms for SS/TDMA scheduling

The authors present 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 the computational complexity of previously published algorithms is greatly reduced, simulation results evidence that the assignment duration is close to previously presented solutions