NEW BOUNDS FOR OPTIMUM TRAFFIC ASSIGNMENT IN SATELLITE COMMUNICATION

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.