An integer programming approach to the time slot assignment problem in satellite switched time-division multiple-access systems with intersatellite links

We consider the time slot assignment problem (TSAP) in a cluster of satellite-switched time-division multiple-access satellite system with intersatellite links. The problem is known to be NP-complete. In this paper, we consider TSAP as a graph coloring problem on a bipartite multigraph which is constructed from the traffic requirements. We give an integer programming model for TSAP and propose an algorithm based on the column generation technique. Computational results using randomly generated data are reported.