In this paper we assume that a satellite has l receiving and transmitt
ing 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 nu
mber of rows and columns of D, that no preemption of the communication
s is allowed, and that changing the configuration of the switch requir
es a negligible time. We ask for a set of switch configurations that m
inimizes 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 valu
e. We then present five heuristics: the first two are obtained modifyi
ng algorithms from the Literature; two others are obtained with standa
rd techniques; the last algorithm is an implementation of a new and pr
omising tabu search method which is called exploring tabu search. Exte
nsive computational experiments compare the performances of the heuris
tics and that of the lower bound, on randomly generated instances. (C)
1998 Elsevier Science Ltd. All rights reserved.