We consider scheduling of colored packets with transition costs which form a general metric space. We design a @math competitive algorithm. Our main result is a hardness result of @math 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 @math competitive algorithm and a nearly-matching hardness result. In proving our hardness results we use some interesting non-standard embedding.
@cite_17: We consider buffer management of unit packets with deadlines for a multi-port device with reconfiguration overhead. The goal is to maximize the throughput of the device, i.e., the number of packets delivered by their deadline. For a single port or with free reconfiguration, the problem reduces to the well-known packets scheduling problem, where the celebrated earliest-deadline-first (EDF) strategy is optimal 1-competitive. However, EDF is not 1-competitive when there is a reconfiguration overhead. We design an online algorithm that achieves a competitive ratio of 1 - o(1) when the ratio between the minimum laxity of the packets and the number of ports tends to infinity. This is one of the rare cases where one can design an almost 1-competitive algorithm. One ingredient of our analysis, which may be interesting on its own right, is a perturbation theorem on EDF for the classical packets scheduling problem. Specifically, we show that a small perturbation in the release and deadline times cannot significantly degrade the optimal throughput. This implies that EDF is robust in the sense that its throughput is close to the optimum even when the deadlines are not precisely known.
The closest model to our model is the colored packets with deadline problem @cite_17 . In that model we are given a sequence of incoming packets. Each packet is characterized by a color and a deadline (all packets have the same value). The goal is to find a schedule that maximizes the number of packets that were transmitted before the deadline, such that there is a transition time-slot between the transmission of packets of different colors. An algorithm with competitive ratio of @math and hardness result of @math are shown in @cite_17 , when @math is the number of colors and @math is the minimum of the difference between the expiration and the arrival time of packets.