Two NP-hard problems related to satellite communications

This paper presents two NP-hard problems related to satellite communications. The first consists of scheduling data packets through satellite repeaters, under resource constraints, to minimize trnsmission time. It is well solved using a list scheduling algorithm. The second is to minimize the amount of equipment required at earth stations for transmitting a given set of bursts. A simulated annealing procedure solves it quasi-optimally. Software programs implementing these methods are used in the day-to-day operation of the EUTELSAT system. The present approach could be applied to similar problems encountered in shop planning and in facility location.