New Bounds for Optimum Traffic Assignment in Satellite Communication

In this paper we assume that a satellite has l receivingand transmitting antennas, and we are given a traffic matrix D tobe transmittedby interconnecting pairs of receiving-transmitting antennas, through anon board switch. We also assume that l is strictly smaller thanthe number of rowsand columns of D, that no preemption of thecommunications is allowed, and that changing the configuration ofthe switch requires a negligible time. We ask for aset of switch configurations that minimizes the totaltime occurring for transmitting the entire traffic matrix.We present some new lower bounds on the optimum solution value anda new technique to combine bounds which obtains a dominating value.We then presentfive heuristics: the first two are obtained modifying algorithmsfrom the literature; two others are obtained with standard techniques;the last algorithm is an implementation of a newand promising tabu search method which is called Exploring Tabu Search.Extensive computational experimentscompare the performances of the heuristics and that of the lower bound,on randomly generated instances