In this paper we assume that a satellite has l receiving and transmitting antennas, and we are given a traffic matrix D to be transmitted by interconnecting pairs of receiving–transmitting antennas, through an on-board switch. We also assume that l is strictly smaller than the number of rows and columns of D, that no preemption of the communications is allowed, and that changing the configuration of the switch requires a negligible time. We ask for a set of switch configurations that minimizes the total time occurring for transmitting the entire traffic matrix. We present some new lower bounds on the optimum solution value and a new technique to combine bounds which obtains a dominating value. We then present five heuristics: the first two are obtained modifying algorithms from the literature; two others are obtained with standard techniques; the last algorithm is an implementation of a new and promising tabu search method which is called exploring tabu search. Extensive computational experiments compare the performances of the heuristics and that of the lower bound, on randomly generated instances.
