Scheduling in switching networks with set-up delays

We consider the (preemptive bipartite scheduling problem PBS) (Crescenzi et al.,"On approximating a scheduling problem," Journal of Combinatorial Optimization, vol. 5, pp. 287-297, 2001) arising in switching communication systems, where each input and output port can be involved in at most one communication at the same time. Given a set of communication tasks to be communicated from the transmitters to the receivers of such a system, we aim to find a schedule minimizing the overall transmission time. To achieve this, we allow the preemption of communication tasks. However, in practice preemption comes with a cost, d, and this renders the problem NP-hard (Gopal et al., "An optimal switching algorithm for multibeam satellite systems with variable bandwidth beams," IEEE Trans. Commun., vol.30, pp. 2475-2481, 1982). In this paper, we present a 2 - 1/d+1 approximation algorithm, which is the first one for the PBS problem with approximation ratio strictly less than two. Furthermore, we propose a simple optimal polynomial time algorithm for a subclass of instances of the PBS problem.