Scheduling in Multibeam Satellites with Interfering Zones

Abstract
The traffic scheduling problem is studied in a satellite-switched time-division multiple-access system with interfering beams. A two-step approach is investigated, 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 can be solved in polynomial time in most cases, while the second step is proved to be NP-complete, even for very simple interference patterns. Several suboptimal algorithms for this second step are suggested