  We consider scheduling of colored packets with transition costs which form a
general metric space. We design a $1 - O(\sqrt{MST(G) / L})$ competitive
algorithm. Our main result is a hardness result of $1 - \Omega(\sqrt{MST(G) /
L})$ which matches the competitive ratio of the algorithm for each metric space
separately. In particular, we improve the hardness result of Azar at el. 2009
for uniform metric spaces.
  We also extend our result to weighted directed graphs which obey the
triangular inequality and show a $1 - O(\sqrt{TSP(G) / L})$ competitive
algorithm and a nearly-matching hardness result. In proving our hardness
results we use some interesting non-standard embedding.
