Scheduling in SS/TDMA systems with intersatellite links

An approach is presented for the optimal time slot assignment problem of a general satellite-switched time-division-multiple-access (SS/TDMA) satellite system interconnected through intersatellite links. An arbitrary number of satellites in the network, arbitrary interconnection through the intersatellite links, and arbitrary ISL propagation delay are considered. In addition, each satellite may cover an arbitrary number of disjoint zones. An analog of the scheduling problem is represented in terms of a modified open-shop scheduling problem consisting of jobs to be processed on processors. Using this analogy, a modified algorithm first given for the classical open-shop scheduling problem is investigated. Since the problem is NP-complete, the shortest processing time heuristic is introduced, and its performance bounds obtained