Scheduling in Switching Networks with Set-Up Delays

Foto Afrati (), Timos Aslanidis, Evripidis Bampis and Ioannis Milis
Additional contact information
Foto Afrati: NTUA
Timos Aslanidis: NTUA
Evripidis Bampis: Université d’Evry Val d’Essonne
Ioannis Milis: Athens University of Business and Economics

Journal of Combinatorial Optimization, 2005, vol. 9, issue 1, No 4, 49-57

Abstract: Abstract 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 - \frac{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.

Keywords: switching networks; scheduling; set-up delays; approximation algorithms (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-005-5483-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:9:y:2005:i:1:d:10.1007_s10878-005-5483-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-005-5483-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().