Scheduling in Multibeam Satellites with Interfering Zones

In this paper we study the traffic scheduling problem in an SS/TDMA system with interfering beams. We investigate a twostep approach, the first step being the assignment of orthogonal polarization to reduce the interference, and the second step being the scheduling of traffic, taking into account the "resultant" interference. The first step we show can be solved in polynomial time in most cases, while the second step we prove to be NP-complete, even for very simple interference patterns. We suggest several suboptimal algorithms for this second step and, by experimental trials on randomly generated traffic patterns, show that on the average they produce close to optimal solutions.