  Given a set of messages to be transmitted in packages from a set of sending
stations to a set of receiving stations, we are required to schedule the
packages so as to achieve the minimum possible time from the moment the 1st
transmission initiates to the concluding of the last. Preempting packets in
order to reroute message remains, as part of some other packet to be
transmitted at a later time would be a great means to achieve our goal, if not
for the fact that each preemption will come with a reconfiguration cost that
will delay our entire effort. The problem has been extensively studied in the
past and various algorithms have been proposed to handle many variations of the
problem. In this paper we propose an improved algorithm that we call the
Split-Graph Algorithm (SGA). To establish its efficiency we compare it, to two
of the algorithms developed in the past. These two are the best presented in
bibliography so far, one in terms of approximation ratio and one in terms of
experimental results.
